Herhangi bir harita yalnızca dört renk kullanılarak renklendirilebilir mi? Tarihi 1852’ye kadar uzanan, matematiğin en ünlü problemlerinden birinin ardındaki soru budur. 1976’dan beri cevabın “evet” olduğunu biliyoruz; fakat aslında rengi nasıl buluyorsunuz? Şimdi, Kopenhag Üniversitesi ve DTU’dan iki profesör, uluslararası meslektaşlarıyla birlikte, on yıl süren bir saplantının ardından en uygun algoritmayı buldu. Cevap yeni temel matematiksel anlayışlar sağlıyor.
Çalışma şu adreste yayınlanıyor: arXiv ön baskı sunucusu.
174 yıldır dünyanın her yerindeki matematikçiler dört renk problemiyle boğuşuyorlar: Herhangi bir haritanın her zaman en fazla dört renk kullanılarak renklendirilebileceği ve iki komşu bölgenin aynı rengi paylaşmayacağı gerçekten doğru olabilir mi?
Bunun mümkün olduğu, 1852’de İngiliz matematikçi Francis Guthrie tarafından, İngiltere’nin ilçelerinin haritasını çizerken yalnızca dört renge ihtiyaç duyduğunu fark ettikten sonra tahmin edildi. Ancak zorluk, haritanın nasıl göründüğüne bakılmaksızın, varsayımının her zaman geçerli olduğunu kanıtlamaktı. Bu, o zamandan beri dünya çapında matematikçileri meşgul eden ünlü dört renk problemidir.
İlk kanıt 1879’da sunuldu ve bir hatanın keşfedilmesi 11 yıl sürdü. Nihayet 1976’da tam bir kanıt bulundu, yani artık dört renkli bir teoremimiz vardı, ancak kanıt tartışmalıydı çünkü diğer matematikçilerin doğrulamayı zor bulduğu bilgisayar hesaplamalarına büyük ölçüde dayanıyordu. 1997’de yeni ve daha erişilebilir bir kanıt tanıtıldı. Ayrıca dört renklendirme de bulabiliyordu ancak büyük haritalara uygulandığında algoritmik olarak yavaştı.
Şimdi, aralarında iki Danimarkalı profesörün de bulunduğu uluslararası bir matematikçi ekibi, 30 yıl içinde ilk büyük atılımı gerçekleştirdi: Herhangi bir haritayı verimli bir şekilde dört renkli hale getirmek için en uygun algoritmayı buldular.
Çalışmanın arkasındaki araştırmacılardan biri olan Kopenhag Üniversitesi Bilgisayar Bilimleri Bölümü’nden profesör Mikkel Thorup, “Önceki kanıtlar, bir haritayı dört renk kullanarak renklendirmenin her zaman mümkün olduğunu gösterdi. Ancak haritadaki her bir bölgenin renklerini bulma konusunda aslında pek iyi değiller. Yeni algoritma etkili ve çok daha hızlı bir renklendirme yöntemi sağlıyor” diyor.
Araştırma makalesinin ilk kısmı teorik bilgisayar bilimi alanında dünyanın önde gelen konferanslarından biri olan FOCS’26’da sunuldu ve burada En İyi Makale Ödülü’nü aldı.
1000 matematikçi hastalığa yakalandı
Thorup ve aralarında Carsten Thomassen, Ken-ichi Kawarabayashi ve Bojan Mohar’ın da bulunduğu araştırma arkadaşları yaklaşık 10 yıldır dört renk problemi üzerinde çalışıyorlar. Thorup buna “dört renk hastalığı” diyor:
“Hastalık, bu kadar basit bir ifade için basit bir kanıt olması gerektiğine inanmaktır. Sanırım en az 1000 matematikçi dört renk hastalığına yakalanmış, aylarca bunu çalıştırmaya çalışmış ama hiçbir zaman tam anlamıyla başarılı olamamış. Bu, insanların 1852’den beri muzdarip olduğu bir hastalık.”
Ama neden biri böyle bir şey üzerinde yıllarını harcasın diye merak edebilirsiniz.
“Çünkü matematikçiler biraz deli. Matematikçilerin üzerinde çalıştığı soruların çoğu çok inek sorulardan oluşuyor. Bu tür problemlere takıntılı hale geliyoruz çünkü insan zekasını zorluyor. Ve eğer cevabı bulursak, muhtemelen diğer matematiksel bulmacaların cevaplarını da bulacağız” diyor Thorup.
Yeni matematiksel anlayış üzerine inşa edilmiştir
Yeni algoritmanın öncekilerden çok daha verimli olmasının nedeni, araştırma ekibi tarafından keşfedilen tamamen yeni bir matematiksel anlayışa dayanmasıdır.
Matematik dilinde harita gibi bir yüzeye düzlemsel grafik denir. Araştırmacılar, grafiklerin daha önce inanıldığından çok daha fazla indirgenebilir konfigürasyon içerdiğini keşfettiler. Bunlar, matematikçilere bir renklendirme üzerinde çalışırken başlayabilecekleri bir yer sağlayan grafiğin küçük bölümleridir.
DTU’dan profesör ve ortak yazar Thomassen, “İndirilebilir konfigürasyonları, dört renklendirmeye başlamak için tutabileceğiniz tutamaçlar olarak düşünün. Grafiklerin yalnızca bir tutamaç içermediğini, şaşırtıcı sayıda tutamaç içerdiğini gösterdik. Bunu daha önce kimse bilmiyordu” diyor.
Araştırmacılar artık bir grafiğin birçok yerinde “tutamaçları” bulabildikleri için, önceden yalnızca tek bir tane bulabildikleri için, renklendirme sürecine birçok farklı yerden başlayabilirler ve bu nedenle çok büyük haritaları bile çok daha hızlı bir şekilde renklendirebilirler.
Thomassen, “Matematikçilerin ikinci dereceden zaman dediği şeyden doğrusal zamana geçtik. Bu, eğer bir harita 10 kat daha fazla bölge içeriyorsa hesaplamanın yalnızca 10 kat daha yavaş olacağı anlamına geliyor. Önceki algoritmayla yaklaşık 100 kat daha yavaş olurdu” diye açıklıyor.
Yüzme halkaları ve Emmental peyniri ile de alakalı
Yeni buluşla araştırmacılar, haritaları renklendirmenin daha hızlı bir yolunu bulmaktan daha fazlasını yaptılar. Grafiklerin yapısına ilişkin yeni anlayışları, klasik dört renk probleminin ötesine geçiyor ve çok daha karmaşık grafik ve yüzey türlerini incelemek için yeni olanaklar sunuyor.
Thorup şöyle diyor: “İlginç olan şey, çok fazla tutamaç olduğu için bu fikrin düz bir haritanın yanı sıra başka türdeki yüzeylere de uygulanabilmesi. Örneğin yüzme yüzüğü veya bir parça Emmental peyniri gibi delikli yüzeyler. Bu nedenle sonucun dört renk teoreminin çok ötesinde bir öneme sahip olabileceğine inanıyoruz.”





