Dört Renk Problemi Nedir? Harita Boyamak İçin Kaç Renk Gerekir?

Arkadaşlarınız ile Paylaşın
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Dört renk problemi denince akla kıyafet giyerken renk uyumuna dikkat etmek ya da yeni alınacak koltuk takımının halıya uyumlu olması problemi gelebilir. Bunlar gerçekten de günlük hayatta karşımıza çıkabilecek problemlerdir. Fakat, dört renk problemi maalesef bunlara çözüm aramıyor. Dört renk problemi, başka bir günlük hayattan probleme çözüm arıyor. Problemi kabaca anlatmak gerekirse; dört renk problemi, herhangi bir haritayı boyayabilmek için en az kaç renk gerekir sorusuna cevap aramaktadır.

Problemi yukarıdaki gibi sorduğunuzda bir cevabını almanız muhtemeldir. O yüzden, dört renk problemine biraz daha yakından bakalım. Asıl soru şu; Bir haritanın renklendirilmesinde, birbirine komşu iki bölgenin farklı renkte olması koşulu ile en az kaç renk kullanmak gerekir?

Bu soruya da eğer matematikçi değilseniz şöyle cevap verebilirsiniz; “Eee, mesela satranç tahtası gibi bir harita olsun, bu harita 2 renkle gayet de boyanmış.” demek ki en az iki renk yeterlidir. Satranç tahtası da bir haritadır evet doğru iki renk ile boyanmıştır. Problem ise şudur: en karmaşık haritada bile, yani satranç tahtası gibi olmayan daha karışık bir haritada, Her zaman emin olabileceğimiz bir alt sınır var mıdır?

Sorunun cevabını hemen verelim. Evet vardır. Harita ne kadar karışık olursa olsun, harita en az 4 renk kullanarak boyanabilir.

Dört Renk Problemi Nasıl Ortaya Çıktı?

Peki, bu problem ilk kimin aklına geldi ve gelişimi nasıl oldu?

  • Bu problemi ilk olarak 1852 yılında Francis Guthire sezinledi.
  • Daha sonra problemi kardeşine mektupla sordu.
  • Soruya cevap bulamayan Francis’in kardeşi, Frederick problemi hocası olan ve ünlü matematikçi De Morgan’a sordu.
  • De Morgan bu problemle uğraştı. Önce bu problemin ispatını iki önermeye ayırdı. Birinci önermeyi ispatladı. Fakat ikinci önermeyi ispatlayamadı.
  • Daha sonra bu problem biraz unutuldu. Fakat 1878 yılında Yine ünlü bir matematikçi olan Arthur Cayley, problemi Londra Matematik Cemiyeti’ne sundu. Böylece problem ünlü bir problem haline geldi.
  • Problemin sunuluşunun üzerinden bir sene geçmeden Kempe, geliştirdiği bir yöntemi sundu. Problemi tam olarak çözememişti fakat dört renk problemi ile uğraşan matematikçiler bu yöntemle problemi çözmeye çalıştılar. Kempe’nin yöntemi, problemi durumlara bölmekti. Fakat yine tek tek incelenemeyecek kadar çok durum vardı.

Bilgisayar İcat Oldu Mertlik Bozuldu

  • Matematikçiler, uzun yıllar Kempe’nin izinden gittiler. Fakat dört renk problemine bir çözüm bulamadılar. Ta ki bilgisayarlar olaya el atana kadar.
  • 1970 yılında Kempe’nin indirgediği olasılıkları incelemek, Appel ve Haken isimli matematikçilere göre o zamanki bilgisayarların hızına göre 12 sene 2 aydan biraz fazla sürecekti.
  • Nihayet 1976 yılında Appel ve Haken, bu durumların sayısını biraz azaltmayı başararak 1936’ya indirdiler ve bir yandan da bilgisayarların hızı artınca bu iş için 1200 saat bilgisayar kullanmak yetti.
  • 1996 yılında ise Neil Robertson, Daniel Sandersi Paul Seymour ve Robin Thomas incelenmesi gereken durumu 633’e indirmişlerdir.
  • Böylece problem çözülmüş oldu ve artık dört renk problemi, dört renk teoremi olarak adlandırılmayı hak etti.

Dört Renk Teoremi

1976 yılından beri herhangi bir harita en az dört farklı renkle boyanacağını biliyoruz. Her ne kadar matematikçiler açısından teoremin ispatı şık olmasa da bilgi kesin. Matematikçiler, tüm olasılıkları göstererek ispat yapmayı çok sevmezler ve kullanışlı bulmazlar. O yüzden bu teoremin bilgisayar kullanılarak bu şekilde yapılması bir çığır açtı diyebiliriz. Tabi hala bu teoremin daha şık ispatını bir yerlerde matematikçiler arıyor olabilir.

Peki, 2 veya 3 renk kullanarak boyanan haritalar yok mudur? Tabi ki vardır. Yazının başında da belirttiğim gibi, satranç tahtası gibi bir harita iki farklı renkle boyanabilir. Dört renk teoreminin ispatı aranırken şu sonuçlar da kendiliğinden çıktı:

  1. Haritanın iki renkle boyanabilmesi için; haritanın tüm köşelerinde iki sınır çizgisi bulunmalıdır.
  2. Haritanın üç renkle boyanabilmesi için; her ülkenin çift sayıda komşusu olmasıdır.

Kaynaklar

  1. Dört Renk Problemi- Ali Doğanaksoy, Ayşe Berkman, Ebru Keyman
  2. THE FOUR COLOUR THEOREM

Yazar: admin

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

This site uses Akismet to reduce spam. Learn how your comment data is processed.