Dört Renk Problemi
İlkokulda hepimiz defterimize Türkiye haritasını çizmiş ve renklendirmişizdir. Peki aynı haritayı birbirine komşu şehirler farklı renkte olacak şekilde boyamak için en az kaç renge ihtiyaç duyarız?
Çizim: Mert Oskeroğlu
Bu haritayı veya daha karmaşık bir haritayı, birbirine komşu şehirler farklı renkte olacak şekilde boyamak için her zaman dört renk yeterlidir. Eğer dört rengin bu işlem için yeterli olmadığını düşünüyorsanız, bir harita çizip renklendirmeyi deneyebilirsiniz. Ancak renklendirmeyi yaparken sınırları sadece tek bir noktada kesişen şehirlerin birbirine komşu sayılmadığını unutmayın.
Gelelim bu problemin ortaya çıkış hikâyesine.
Bir haritanın renklendirilmesi için dört farklı rengin yeterli olduğunu söyleyen ilk kişi Francis Guthrie’ydi. Guthrie, bu durumu 1852 yılında ülkesinin yani İngiltere’nin haritasını boyarken fark etti. Ardından bunun başka haritalar için de geçerli olup olmadığını anlamak için farklı haritalar boyamaya başladı. Yaptığı tüm çalışmalar, Guthrie’yi bir haritayı birbirine komşu bölgeler farklı renkte olacak şekilde boyayabilmek için dört farklı rengin yeterli olduğu varsayımına ulaştırdı. Fakat bu varsayımın matematiksel ispatını bulamayan Guthrie, kardeşi Frederick Guthrie’ye bir mektup yazarak ispatın nasıl yapılabileceğini sordu. Çünkü Frederick Guthrie o sıralarda ünlü matematikçi Augustus De Morgan’ın öğrencisiydi. Cevabı bulmakta zorlanan Frederick Guthrie, soruyu hocasıyla paylaştı.
Augustus De Morgan, sorunun çözülebilmesi için;
- Renklendirilebilmeleri için en az dört renk gerektiren haritalar vardır.
- Renklendirilebilmesi için beşinci renk gerektiren harita çizilemez.
önermelerinin doğruluğunu göstermeye çalıştı. Birinci önermenin doğru olduğunu kolayca gösterdi. Çünkü aşağıdaki gibi diğer üç bölge ile komşu olan bir bölgenin bulunduğu haritaları boyayabilmek için en az dört renge ihtiyaç duyulacağı gayet açıktı.
Düzlemde hepsi birbirine komşu olan en fazla dört bölge vardır.
Augustus De Morgan, ikinci önermenin de doğruluğunu ispatlamak için uğraştı. Bir haritada hepsi birbirine komşu olan beş bölgenin yer alamayacağını gösterdi. Ancak birbirine komşu beş bölgenin bulunmaması, haritanın boyanması için beş renk gerektirmesine engel bir durum olmayabilirdi. Örneğin aşağıdaki haritada birbirine komşu dört bölge bulunmasa da haritanın renklendirilmesi için en az dört renk gerekir. Ancak Augustus De Morgan beş renk için böyle bir durumun örneğini bulamadı.
Çizim: Mert Oskeroğlu
Soruya tam olarak çözüm bulamayan Augustus De Morgan, beğendiği bu soruyu meslektaşlarıyla paylaştı ve böylece dört renk problemi ünlenmiş oldu.
Problemin basitçe ifade edilebilmesi ve herkes tarafından kolayca anlaşılması, birçok matematikçiyi bu problemin ispatı için çalışmalar yapmaya teşvik etti. Fakat her ne kadar tüm haritalar sadece dört farklı renk ile boyanabilse de problemin matematiksel ispatı, problemin ortaya çıkışından tam 124 yıl sonra yapılabildi.
1976 yılında Illinois Üniversitesinden Kenneth Appel ve Wolfgang Haken adlı matematikçiler, bilgisayar yardımıyla, çizge kuramı teorisini kullanarak dört renk problemini ispatladılar. Fakat bunu yapmak hiç de kolay olmadı. Bu ispat için bilgisayarın yaklaşık 10 milyar mantıksal kararı gözden geçirmesi ve 1.200 saatlik bir hesap yapması gerekti.
Kaynaklar:
