Dört Renk Teoremi

Bu haritada kaç renk var? 

Aslında ipucunu sorunun içine renklerle yerleştirdim. Dört renk var: Sarı, Kırmızı, Mavi ve Yeşil. Fakat haritanın tek özelliği bu değil. Hiçbir komşu iki ülke aynı renkte değil. Olsaydı birbirine karışırdı.  Demek ki Dünya ülkelerini birbirinden ayırmak için en az dört renk kullanmamız gerekiyor. Ben daha da ileri giderek şöyle bir iddia da bulunacağım. 4’ten fazla renge ihtiyacımız yok.

Dünyayı renklendirmek için dörtten fazla renk gerekmez! Daha da ileriye gideceğim ve diyeceğim ki… Sadece dünyayı değil, herhangi bir haritayı renklendirmek için dörtten fazla renk gerekmez. Düzlemsel olmak kaydıyla hangi haritayı boyarsanız boyayın, sadece dört renk yeterli. Sadece dört rengi kullanarak, bribrinine bitişik bölgelerin aynı renkte olmamasını sağlayabilirsiniz. İlla Dünya ve ülkeleri haritası olması gerekmiyor. ABD’nin eyaletleri haritasını açın. Dört renk seçin ve boyamaya başlayın.  Hiçbir renk birbirine dokunmayacak, göreceksiniz. İngiltere’nin ilçelerini, “county”lerini boyamak için dört renk seçin. Yeterli olacak, göreceksiniz. Hiçbir renk birbirine dokunmadan boyayabileceksiniz. Aslına bakarsanız tam da bu haritayı boyarken keşfedilmiş bu fikir. Ta 1850’li yıllarda bir botanikçi ve matematikçi olan Francis Guthrie bu haritayı boyarken fark etmiş dört rengin yeterli olduğunu… Kardeşiyle birlikte dönemin meşhur matematikçisi De Morgan’a mektup yazmışlar. Bugün bir öğrencim henüz bilmediğim bir konu hakkında ona bir neden vermemi istedi. Bir şekil herhangi bir şekilde bölünmüşse ve bölmeler farklı renkteyse, dört renk yeterli ama daha fazlası gerekmez.Bu dört rengin istendiği durum aşağıdadır. Beş ve daha fazlası için sorgu icad edilemez…

Herhangi bir şekil diyor bakın. Yani harita olmak zorunda bile değil. Tamamen uydurma haritalar için bile 4 renk yeterlidir. İşte o gün bugündür matematik dünyasında buna “dört renkli harita teoremi” ya da kısaca “dört renk teoremi” adı veriliyor.  Veriliyor da ispatı konusunda koca koca profesörler bile zorlanıyor. Az önce bunu bir matematikçinin keşfettiğini söylemiştim. O önce abisine, abisi de De Morgan’a gönderiyor. Koskoca De Morgan bu. Yasaları filan var okumuşsunuzdur okulda. Onlar ispatlayamıyor mesela… Ama yine de böyle bir gerçekliği onlar da fark ediyor.  125 yıl boyunca bir çok matematikçi, bir çok profesör bunu kanıtlamaya çalışıyor. Ama başaramıyor. Biz bu videoda sizinle birlikte bunu anlamakla kalmayacağız aynı zamanda nasıl çözüldüğünü de öğreneceğiz. Hazır mısınız?

Küçük bir oyunla başlayalım. Ülkemizin şehirleriyle oynayalım bu oyunu. Bu haritayı 4 değil de sadece 3 renkle boyamaya çalışalım.  İzmir’den başlayalım. Yeşil olsun. Komşusu Aydın’ı Sarı renkli yapalım. Diğer komşusu Manisa da mavi olsun. Sıra geldi İzmir’in dördüncü komşusuna.  Dördüncü bir renge ihtiyacım var mı? Hayır yok. Bitişik olmaması kaydıyla daha önce kullandığım bir rengi tekrar kullanabilirim. Bu durumda Balıkesir de tıpkı Aydın gibi sarı renkli olabilir.  Oyunun mantığını anlayabildik değil mi? Şu ana kadar sadece 3 renk yeterli oldu ve bir müddet daha yeterli olmaya devam edebilir. Çanakkale’yi yine mavi yapabilirim. Edirne’ye sarı, Tekirdağ’a yeşil diyerek devam edebilirim. Haritanın bu kısımları o kadar da karmaşık değil. Ama karmaşık olan yerleri de var. Mesela Konya’ya bir bakın. Konya’yı ve komşularını da aynı mantıkla boyamaya başlayabiliriz. Yeşil, sarı, mavi diye gidebiliriz…. Ta ki Karaman’a gelinceye kadar.  Burada artık Sarı kullanamayız. Antalya’dan dolayı. Mavi de kullanamayız. Mersin’den dolayı.  E yeşili zaten kullanamıyoruz, Konya’dan dolayı.  Ne yapacağız şimdi?  Karaman’ın nesi meşhur? Koyunu ve bu videodan sonra kırmızısı… Evet, artık dördüncü bir renge ihtiyacımız oldu ve onu da burada kullandık. Haritanın gerisi için bu dört renk yeterli olacak. Dileyenler boyamaya devam edebilir. İyi de bunu matematiksel olarak nasıl ispat edebiliriz? Haritalar yapısı gereği fazla karmaşık. Herhangi bir problemi çözerken sadeleştirme yoluna gitmek lazım. Bu haritayı nasıl sadeleştirebiliriz? Bakın burada kentleri noktalara indirgedim. Aralarındaki komşuluk ilişkilerini sınrılarla değil de dümdüz çizgilerle göstereyim şimdi de… Konya’dan Ankara’ya bir çizgi çekelim. Bu iki nokta birbirine komşu anlamına geliyor. Diğer komşularla da bu ilişkiyi yine çizgilerle gösterelim. Böyle bir şekil çıktı ortaya. Aslına bakarsanız matematikteki “graph theory”i yani çizge teorisini kullanmış olduk. Haritadaki alan ve ilişkileri, noktalar ve çizgilerle ifade ederek… Bir başka deyişle haritayı, bir network’e yani bir ağa dönüştürdük. Her harita, böyle bir ağa dönüştürelebilir. Ama her ağ bir haritaya dönüştürülemez. Bunu unutmayın. İleride tekrar kullanacağız bu bilgiyi. Konya’nın 9 komuşusuyla olan ilişkisini sadeleştirdik. Sadece nokta ve düz çizgilerle.  Bakmayın burada Mersin’e giden çizgi, Karaman’ın üstünden geçiyor ama teknik olarak doğru, çünkü bu iki kent birbirine komşu. Fakat diğer kentlerin de kendi komşuluk ilişkileri var. Mesela Ankara’nın 7 komşusuyla ilişkisi şu şekilde gösterilebilir.  Niğde’nin de 6 komşusu var. Her kent Konya kadar komşuya sahip değil. Görüyorsunuz Mersin’de 5’e düştük. Ve nihayet Karaman’ın sadece 3 komşusu var.  Peki bunların hepsinin eşit olduğu bir harita çizilebilir mi? Mesela burada gördüğünüz sayıların hepsi 5 olsa. Her şehrin 5 şehre komşu olduğu bir harita çizilebilir mi? Ne eksik ne fazla. Hepsi 5 olacak. İşte size bir challenge! 1 dakika süreniz var böyle bir harita ya da graf çizebilmek için.

Evet, çözenler çözemeyenlere göstersin, çünkü bunu yapabilmek mümkün. Sol alt köşeden başlayalım.  – 5 başka noktaya komşu olması gerekiyor. 1, 2, 3, 4, 5. İşte oldu. – Sağ alt köşedeki noktadan da 5 noktaya komşuluk ilişkisi kuralım. Bu da tamam. – Üsttekinde zaten bazı bağlantılar kurulmuştu. Bunları 5’e tamamlayalım. – Ve bu şekilde tüm noktaları birleştirdiğimizde her noktası 5 komşulu bir ağ oluşturduk. Ama bu bir ağ. Harita değil.  Hartasını oluşturmak kolay. Etrafını böyle sınırlarla kapatırsak ağı haritaya dönüştürmüş oluruz. Diyeceksiniz ki, böyle harita mı olur dümdüz çizgilerle. Olur tabi neden olmasın. ABD’nin eyaletleri haritasında bir çok sınır böyle. Dünyanın bazı ülkelerini sınırları bile cetvelle çizilmişçesine dümdüz olabiliyor. Ama hadi sizi kırmayalım… Bu çizgileri biraz daha yuvarlatarak organik bir haritaya benzetmeye çalışalım.  Böyle bir harita mümkün. Bunun mümkün olduğunu  – matematikteki graf teorisini kullanıp ağ ilişkisiyle ortaya koymuş olduk. Sorumuz neydi? – Her şehrin 5 şehre komşu olduğu bir harita çizilebilir mi? – Cevabımız: Evet. Çizilebilir.  Peki soruda neden 5 tane diyoruz? 6 tane olamaz mı? Hayır, olamaz. İsterseniz deneyin. Ortaya şuna benzer bir şekil çıkar. Çizgiler birbirini kesmek zorunda kaldığı için bu ağ, bir haritaya dönüştürülemez. Ne demiştik? Her harita ağa dönüştürülebilir, ama her ağ haritaya dönüştürülemez. İşte o yüzden her şehrin 6 şehre komşu olduğu bir harita çizilemez. Şehir dediğime bakmayın, ülke, alan, bölge için de geçerli bu söylediklerim. Demek ki 5 sayısı bir sınır. Tıpkı ışık hızı gibi. Geçilemiyor. Madem öyle o zaman şöyle diyebilir miyiz? Her şehrin 5 şehre komşu olduğu bir haritada dört renk yeterlidir. Gördüğünüz gibi diyebiliriz. Ta 1850’lerde bunu fark edenler olmuş. Adına da daha önce söylediğimiz gibi… Dört renkli harita teoremi demişler. Bu konuda en az bunun kadar ilginç olan diğer şeyse fark edildikten sonra bunun ispat edilememesi. 125 yıl boyunca nasıl ispat edemezsin? Gözünün önünde duruyor.  Peki biz düşünelim biraz da… “Herhangi bir haritayı” dediğimize göre iki yoldan ilerleyebiliriz. Birinci yol: olası tüm haritaları çizip, her birinin dört renkle boyanabileceğini, beşinciye hiç ihtiyaç olmadığını gösterebiliriz. Ya da ikinci yol: öyle bir harita buluruz ki, beş tane renk kullanmak zorunlu olur. İyi de ikinic yola zaten birinciden geçmeden gidilemiyor. Yani bir şekilde ilk yolu denemek gerekiyor. Konya ve komşuları haritasını nasıl ağa çevirmiştik? Benzer bir yöntemle olası tüm ağları çıkarmamız gerekiyor. Tek başına bir bölge olabilir mi? Olur tabi. Düşünün haritaları. Adalar böyle. Kıbrıs’ın ağ gösterimi bu şekilde yapılabilir. Eminim böyle bölgeler de vardır. Sadece birbirine komşu iki alan. Başka ne vardır? Üçlü bir ağ yapısı olabilir. Aynı mantıkla…  …nereye varacağımı… …tahmin… …edebilirsiniz. 5’e kadar geldik.  6’ya çıkabilir miyiz? Sınırımız 5’ti hatırlarsanız. Bundan sonra… …daha önceki temel ağ yapılarının kombinasyonlarını kullanabiliriz. Ne gibi kombinasyonlar yapılabilir göstereyim… Mesela şunlar yapılabilir. Ya da bunlar yapılabilir. Bir de bunları ekleyebiliriz. Ben böyle güzel güzel anlatıyorum ama tahmin edebileceğiniz gibi tüm bu olasılıkları ben hesaplamadım. Appel ve Haken adında iki matematikçinin yazdığı bir kitaptan aldım. Evet bu kitabı onlar yazdı, ama tüm bu olasılıkları yine tek başlarına hesaplayamadılar.  Dedim ya 125 yıl boyunca ne matematkçiler, ne profesörler geldi geçti ama hiç biri bu teoremi kanıtlayamadı diye. 

İşte bu kitapta nihayet kanıtı yazıldı. Kitabın adı: Every Planar Map is Four Colorable.  Her düzlemsel harita dört renklenebilir. Ta 1850’lerde keşfedilen bu durum, ilk kez 1879’da kanıtlanmaya çalışıldı. Ancak 23 Temmuz 1976’da bu kitabın yayınlanmasına kadar hiç kimse tarafından kanıtlanamadı.  Ha bu kitapta yapılan kanıtlama yöntemi de biraz tartışmalı… …çünkü dipnotunda da göreceğiniz gibi yazarlar Illinois Üniversitesi’ndeki bilgisayarları kullandıkları için teşekkür ediyorlar. Yani bilgisayar desteğiyle hesaplamışlar. Bilgisayar yardımıyla kanıtlanan ilk matematik teoremi bu! Sene 1976. O zamanki bilgisayarların gücü, bugünkü kol saatleri kadar bile değil. Yine de makine ve insan kafa kafaya vermiş ve kaç ağ yapısı ortaya çıkarmış biliyor musunuz? 1936. Evet, birbirinden farklı 1936 konfigürasyon yaparak teoremi kanıtlamışlar. Bir kanıt mı bu? Evet. Ama pek şık değil.  Eğer daha şık bir kanıt yapabilirseniz matematik tarihine geçebilirsiniz.  O zamana kadar şundan emin olabiliriz. Bu haritada dört renk var. Herhangi bir haritayı renklendirmek için bu kadarı yeterli. Bu bilgi ne işimize yarayacak? Daha önce konuştuğumuz gibi ona da siz karar verin.