Dört renk teoremi: Bir harita sorusu ve bilgisayarla ispat tartışması

Bir dünya haritası boyadığınızı düşünün. Tek kuralınız var: Ortak sınırı olan iki ülke aynı renkte olmamalı. Kaç farklı renk kalem yeterlidir? Deneyerek görürsünüz ki çoğu haritada dört renk işinizi görür. Peki bu her harita için doğru mu? Yoksa bir gün beşinci renge ihtiyaç duyulan tuhaf bir harita çıkar mı?

Bu soru 1852’de soruldu. Cevabı, yani her haritanın dört renkle boyanabileceği, ancak 1976’da kanıtlandı. Üstelik ispatın önemli bir kısmını insanlar değil, bir bilgisayar yaptı. Bu yazıda sorunun tarihini, basit durumların neden çözülebildiğini, bilgisayarın neden gerektiğini ve bu ispatın matematikçiler arasında başlattığı tartışmayı anlatacağız.

Soru nereden çıktı?

1852’de Londra’da öğrenci olan Francis Guthrie, İngiltere’nin idari bölgelerini gösteren bir haritayı boyarken dört rengin yettiğini fark etti ve bunun her harita için geçerli olup olmadığını merak etti. Soru, kardeşi aracılığıyla matematikçi Augustus De Morgan’a ulaştı. De Morgan 23 Ekim 1852’de İrlandalı matematikçi William Rowan Hamilton’a yazdığı bir mektupta soruyu aktardı ve cevabı bilmediğini belirtti.

Sorunun kuralını netleştirelim:

• Ülkeler tek parça olmalı. Ana topraklarından ayrı bir parçası olan ülkeler bu soruya dahil değildir.
• İki ülke yalnızca bir noktada değiyorsa komşu sayılmaz. Bir pastanın dilimleri gibi tek noktada buluşan bölgeler aynı renkte olabilir. Komşuluk, bir sınır çizgisini paylaşmak demektir.

Neden en az dört renk gerekir?

Önce dört rengin bazen gerekli olduğunu görelim. Kendi örneğimizi kuralım: Ortada bir A ülkesi, onu tamamen çevreleyen üç ülke olsun: B, C ve D. Çevredeki üç ülke de hem A’ya hem de birbirine komşu olsun.

• A, B, C ve D’nin her biri diğer üçüne komşudur.
• Birbirine komşu dört ülkeye üç renk verirsek, güvercin yuvası ilkesi gereği ikisi aynı renkte olur. Oysa bu ikisi komşudur.

O hâlde bu haritaya en az dört renk gerekir. Soru, beşin hiçbir zaman gerekmeyeceğidir.

Bir ipucu da şudur: Beş ülkenin her birinin diğer dördüne komşu olduğu bir düzlem haritası çizmeye çalışırsanız başaramazsınız. Bu kanıtlanmış bir gerçektir. Ama dört renk teoremi bundan daha fazlasını ister. Beşinci renk, doğrudan beşli bir komşuluk olmadan, uzun bir zincirleme etkiyle de gerekebilirdi. Zorluk buradadır.

Haritadan grafa

Matematikçiler bu soruyu graf diliyle ifade eder. Her ülkeyi bir nokta (köşe), iki komşu ülke arasındaki sınırı da bu noktaları birleştiren bir çizgi (kenar) ile gösteririz. Düzleme çizilen haritalardan gelen graflar, kenarları kesişmeden düzleme çizilebilen düzlemsel graflardır. Soru şuna dönüşür: Her düzlemsel grafın köşeleri, bir kenarla bağlı iki köşe aynı renkte olmayacak şekilde dört renkle boyanabilir mi?

Graf kuramının başlangıç sorularından birini Euler ve Königsberg köprüleri yazımızda anlatıyoruz. Aşağıdaki akıl yürütmede Euler’in bir formülü de işimize yarayacak.

Hep bir “az komşulu” ülke vardır

Düzlemsel graflarda köşe sayısı V, kenar sayısı E ve bölge sayısı F ise Euler formülü V − E + F = 2 der. Bu formülden, en az üç köşeli bir düzlemsel grafın kenar sayısının E ≤ 3V − 6 eşitsizliğini sağladığı çıkar.

Bir köşenin derecesi, ona bağlı kenar sayısıdır. Bütün derecelerin toplamı 2E’dir, çünkü her kenar iki köşeye bağlıdır. O hâlde:

• Derecelerin toplamı = 2E ≤ 6V − 12
• Ortalama derece = 2E ÷ V ≤ 6 − 12/V < 6

Ortalama 6’dan küçükse, derecesi en fazla 5 olan en az bir köşe vardır. Örneğin 10 ülkeli bir düzlem haritasında en fazla 3 × 10 − 6 = 24 komşuluk olabilir. Derecelerin toplamı en fazla 48’dir ve ortalama en fazla 4,8’dir.

Bu gözlem, bütün ispat girişimlerinin temel taşıdır. Fikir şu: Az komşulu bir ülkeyi haritadan geçici olarak çıkar, kalan daha küçük haritayı boya, sonra çıkardığın ülkeyi geri koy ve ona bir renk bul. Komşu sayısı 3 ise ya da daha azsa bu kolaydır: Dört renkten en az biri boştadır. Zorluk, 4 ve 5 komşulu durumlardadır.

Kempe’nin ispatı ve Heawood’un keşfi

1879’da Alfred Kempe bir ispat yayımladı. Kullandığı fikir bugün Kempe zinciri olarak bilinir. Bir ülkenin çevresindeki komşular dört rengin hepsini kullanıyorsa, örneğin yalnızca kırmızı ve mavi ülkelerden oluşan bağlantılı bir bölgenin renklerini kendi içinde değiştirebiliriz. Kırmızılar mavi, maviler kırmızı olur. Harita yine kurallara uyar ve bir renk boşa çıkabilir.

Kempe’nin ispatı on bir yıl boyunca kabul gördü. 1890’da Percy Heawood, beş komşulu durumda Kempe’nin akıl yürütmesinin her zaman işlemediğini gösteren bir örnek buldu. Ancak Heawood aynı fikirlerle daha zayıf bir sonucu, her haritanın beş renkle boyanabileceğini kanıtlamayı başardı. Artık cevap ya 4 ya da 5’ti ve soru neredeyse bir yüzyıl daha açık kaldı.

1976: Bilgisayar sahneye çıkıyor

20. yüzyılda matematikçiler Kempe’nin fikrini iki kavramla genişletti:

• Kaçınılmaz küme: Her haritada bulunmak zorunda olan küçük bölge düzenlemelerinin bir listesi. “Hep 5 veya daha az komşulu bir ülke vardır” gözlemi, bu tür bir listenin çok basit bir örneğidir.
• İndirgenebilir düzenleme: Bir haritada bulunduğunda, haritanın geri kalanının dört renkle boyanabilmesinin bütün haritanın boyanabilmesini garanti ettiği düzenleme.

Eğer bütün elemanları indirgenebilir olan bir kaçınılmaz küme bulunursa, teorem kanıtlanmış olur. Çünkü en küçük boyanamayan harita bu düzenlemelerden birini içermek zorunda kalır ve daha küçük bir boyanamayan haritaya indirgenebilir. Bu bir çelişkidir.

Sorun, böyle bir kümenin çok büyük olmasıydı. Illinois Üniversitesi’nden Kenneth Appel ve Wolfgang Haken, Heinrich Heesch’in öncü fikirlerini de kullanarak sürümüne göre sayısı bin beş yüz ile bin dokuz yüz arasında değişen düzenlemelerden oluşan bir kaçınılmaz küme kurdular. Her düzenlemenin indirgenebilir olduğunu bir bilgisayar programıyla tek tek denetlediler. Dönemin bir IBM bilgisayarında bu kontroller yaklaşık 1200 saat sürdü. İspat 1976’da duyuruldu ve 1977’de yayımlandı.

Tartışma: Bu bir ispat mı?

İspat büyük ilgi gördü, ama aynı zamanda rahatsızlık da yarattı. Eleştirilerin özü şuydu:

• Denetlenebilirlik: Geleneksel bir ispatı yeterince sabırlı bir matematikçi satır satır okuyabilir. Bu ispatın bilgisayar bölümünü hiçbir insan elle kontrol edemezdi.
• Güvenilirlik: Programda, derleyicide ya da donanımda bir hata olmadığından nasıl emin olacaktık?
• Anlama: Bazı matematikçiler, bir ispatın yalnızca bir şeyin doğru olduğunu değil, neden doğru olduğunu da göstermesi gerektiğini savundu. Binlerce durumun tek tek kontrolü bu “neden” duygusunu vermiyordu.
• Elle kontrol edilen bölüm: İspatın insanlar tarafından yazılan kısmı da çok uzun ve karmaşıktı. 1980’lerin başında bu bölümün bir kısmını denetleyen bir araştırmacı önemli bir hata buldu. Appel ve Haken hatayı sonraki yayınlarında giderdiler, ama olay ispatın ne kadar zor denetlendiğini gösterdi.

Savunanlar ise şunu hatırlattı: Uzun insan ispatlarında da hata olabilir. Kempe’nin ispatı on bir yıl boyunca yanlış olduğu fark edilmeden kabul görmüştü. Bir programın mantığı ve çıktıları, bağımsız ekiplerce farklı programlarla yeniden kontrol edilebilir. İspatın ne olduğunu ve neden önemli olduğunu ispat nedir yazımızda daha geniş ele alıyoruz.

Daha sade bir ispat ve biçimsel doğrulama

1990’ların ortasında Neil Robertson, Daniel Sanders, Paul Seymour ve Robin Thomas aynı stratejiyle yeni bir ispat verdi. Kaçınılmaz kümeleri 633 düzenlemeden oluşuyordu. Kullandıkları yeniden dağıtım kuralı sayısı yüzlerden 32’ye inmişti. Bilgisayar kontrolü de artık saatler değil, günümüz bilgisayarlarında dakikalar mertebesinde sürüyordu. Yine de bilgisayar olmadan yapılamıyordu.

2005’te Georges Gonthier ve çalışma arkadaşları, dört renk teoreminin tamamını Coq adlı bir ispat doğrulayıcı programda biçimsel olarak kanıtladı. Bu tür programlar her mantıksal adımı, çok küçük ve güvenilir bir çekirdek kural kümesine göre denetler. Böylece yalnızca hesaplar değil, hesapların neden teoremi kanıtladığına dair akıl yürütme de makine tarafından kontrol edilmiş oldu. Bu çalışma, tartışmanın ağırlığını “bilgisayara güvenebilir miyiz?” sorusundan “hangi parçaya, ne ölçüde güveniyoruz?” sorusuna kaydırdı.

Bugün nerede karşımıza çıkar?

• Planlama problemleri: Sınav takvimi hazırlarken ortak öğrencisi olan iki dersi aynı saate koymamak, bir graf boyama problemidir. Burada graflar genellikle düzlemsel değildir ve dört renk yetmeyebilir.
• Frekans atama: Birbirine yakın vericilere farklı frekans vermek de benzer bir boyama sorusudur.
• Bilgisayar bilimi: Bir grafın belirli sayıda renkle boyanıp boyanamayacağına karar vermek, genel durumda çok zor hesaplama problemleri arasındadır.
• Bilgisayarla ispat: Dört renk teoremi, bugün yaygınlaşan bilgisayar destekli ve biçimsel ispatların öncüsü kabul edilir. Hesaplamanın sınırları hakkında Turing makinesi yazımıza göz atabilirsiniz.

Kapanış

Dört renk teoremi, bir çocuğun boyama kitabından çıkmış gibi görünen bir sorunun matematiğin en derin tartışmalarından birini başlatabileceğini gösterdi. Cevap artık kesin: Dört renk yeter. Ama “bir ispatı kim, nasıl denetler?” sorusu, bilgisayarlar ve yapay zekâ matematiğe daha çok girdikçe güncelliğini koruyor.