Dört renk teoremi açıklaması

1852'de İngiltere'nin kontluklarını gösteren bir haritayı boyayan genç bir matematikçi, komşu kontlukları birbirinden ayırmak için dört rengin yeterli göründüğünü fark etti. Bu, olası her harita için doğru olabilir miydi? Soru matematiğin en ünlü problemlerinden biri hâline geldi, on bir yıl ayakta kalan ünlü bir yanlış kanıta yol açtı ve sonunda 1976'da, matematikçilerin kanıt olarak kabul ettikleri şeyi değiştiren bir biçimde çözüldü.

Hiçbir iki komşu aynı rengi paylaşmayacak şekilde dört renkle boyanmış, düzensiz biçimli ülkelerden oluşan bir harita
Hiçbir iki komşu aynı rengi paylaşmayacak şekilde dört renkle boyanmış, düzensiz biçimli ülkelerden oluşan bir harita

Soru

Augustus De Morgan'ın eski bir öğrencisi olan Francis Guthrie, herhangi bir haritanın, sınır paylaşan ülkeler farklı renkler alacak şekilde dört renkle boyanıp boyanamayacağını sordu. İki kural soruyu kesinleştirir. Ülkeler bağlantılı olmalı, yani her biri tek parça olmalıdır; yalnızca tek bir noktada buluşan ülkeler ise komşu sayılmaz. Üç rengin her zaman yetmediği açıktır, çünkü hepsi birbirine değen üç ülkeden oluşan bir halkayla çevrili bir ülke dördüncü bir renk gerektirir. Soru, beşinci bir renge hiç gerek olup olmadığıdır.

Çizge olarak haritalar

Her ülkede bir nokta işaretleyin ve ülkeleri sınır paylaşan her iki nokta arasına bir çizgi çekin. Sonuç bir çizgedir ve harita düz bir yaprak üzerinde durduğu için çizgiler kesişmeden çizilebilir: çizge düzlemseldir. Haritayı boyamak, bu çizgenin köşelerini her kenarın uçları farklı renkte olacak şekilde boyamaktır. İşe yarayan en küçük renk sayısına kromatik sayı denir ve dört renk teoremi hiçbir düzlemsel çizgenin kromatik sayısının dördü aşmadığını belirtir.

Kempe'nin başarısız kanıtı

1879'da avukat ve matematikçi Alfred Kempe bir kanıt yayımladı. Bugün Kempe zincirleri olarak adlandırılan zekice fikri, gereken yerde bir rengi serbest bırakmak için bağlantılı bir ülke zinciri boyunca iki rengi takas etmektir. Kanıt, Percy Heawood 1890'da bir boşluk bulana kadar on bir yıl boyunca kabul gördü. Heawood'un onarımı daha zayıf bir sonucu kanıtladı: beş renk her zaman yeterlidir. Kempe zincirleri ayakta kaldı ve nihai kanıtta bir araç oldu.

Beş neden kolay

Her düzlemsel çizgenin en fazla beş komşusu olan bir köşesi vardır; bu, n köşeli bir düzlemsel çizgeyi en fazla 3n − 6 kenarla sınırlayan Euler formülünden çıkar. Böyle bir köşeyi çıkarın, haritanın geri kalanını aynı akıl yürütmeyle boyayın ve köşeyi geri koyun. Komşuları beşten az renk kullanıyorsa biri boştadır. Beşinin hepsini kullanıyorlarsa bir Kempe zinciri takası her zaman birini serbest bırakır. Dört renkte aynı takas başarısız olabilir ve Kempe'nin gözden kaçırdığı boşluk tam olarak budur.

Bilgisayar kanıtı

1976'da Illinois Üniversitesi'nden Kenneth Appel ve Wolfgang Haken teoremi kanıtladı. Her haritanın kaçınılmaz bir kümedeki 1.936 konfigürasyondan en az birini içerdiğini ve her konfigürasyonun indirgenebilir olduğunu gösterdiler: beş renk gerektiren en küçük bir harita onu içeremezdi. İndirgenebilirliği kontrol etmek bilgisayarlarda bin saatten fazla sürdü; bu, elle doğrulanamayacak kadar fazlaydı. Birçok matematikçi hiçbir insanın baştan sona okuyamayacağı bir kanıttan rahatsız oldu ve bilgisayar destekli kanıtlar üzerine tartışma başladı.

Wolfgang Haken, 1976’da Kenneth Appel ile Illinois Üniversitesi’nde dört renk teoremini kanıtladı.
Wolfgang Haken, 1976’da Kenneth Appel ile Illinois Üniversitesi’nde dört renk teoremini kanıtladı.

Daha basit kanıtlar ve tam doğrulama

1996'da Neil Robertson, Daniel Sanders, Paul Seymour ve Robin Thomas, 633 konfigürasyonlu, hâlâ bilgisayarla kontrol edilen ama doğrulanması daha kolay, daha sistematik bir kanıt yayımladı. 2005'te Georges Gonthier ve Benjamin Werner kanıtın tamamını Coq ispat asistanında biçimselleştirdi; böylece küçük, güvenilir bir program her mantıksal adımı kontrol eder. Bugün dört renk teoremi, matematikteki en kapsamlı biçimde doğrulanmış sonuçlardan biridir.

Boyama algoritmaları

Belirli bir haritanın dört renkli bir boyamasını bulmak pratikte hızlıdır, ancak genel bir çizge için en az renk sayısını bulmak zordur: üç rengin yetip yetmediğine karar vermek NP-tamdır. Pratik yöntemler arasında azalan derece sırasına göre açgözlü boyama, sıradaki olarak en kısıtlı köşeyi boyayan DSATUR ve seçenekleri deneyip tıkandığında onları geri alan geri izleme araması bulunur. Çizge boyama, sınavları çakışma olmadan planlamaya, komşu vericiler birbirini bozmasın diye radyo frekansları atamaya ve derleyicilerde yazmaç tahsis etmeye yarar.

Keşfedin

4 ile 120 arasında ülke içeren haritalar oluşturmak, onları dört renkle elle boyamak ve çakışmaların kırmızıyla belirişini izlemek için dört renk harita boyayıcısını açın. Haritayı açgözlü boyamanın, DSATUR'un ya da geri izlemenin adım adım çözmesine izin verin, komşu ülkelerin çizgesini gösterin ve haritanın gerçekte gerektirdiği en az renk sayısını kontrol edin.

Sık sorulan sorular

Teorem harita yapımcılarına yardımcı olur mu?

Pek değil. Gerçek haritalar netlik için genellikle daha fazla renkle boyanır ve teoremin kapsamadığı okyanusları, gölleri ve birkaç parçadan oluşan ülkeleri içerir. Teoremin önemi matematikseldir: çizge kuramının gelişimini hızlandırdı ve neyin kanıt sayılacağı sorusunu gündeme getirdi.

Kempe zinciri nedir?

İki renk alın, diyelim kırmızı ve mavi, bir de kırmızıya boyanmış bir ülke. Onun Kempe zinciri, ondan yalnızca kırmızı ve mavi komşular üzerinden adım atarak ulaşabileceğiniz tüm kırmızı ve mavi ülkelerin kümesidir. Zincirin tamamında kırmızı ile maviyi takas etmek boyamayı geçerli tutar ve zincirin yanındaki bir ülke için bir rengi serbest bırakabilir.

Birkaç parçadan oluşan ülkeler teoremi neden bozar?

Bir ülke, hepsinin aynı renkte olması gereken ayrı bölgelerden oluşabiliyorsa komşuluk çizgesi artık düzlemsel değildir ve Heawood'un imparatorluk probleminde incelediği gibi, ülke başına iki parça için 12'ye kadar herhangi bir sayıda renk gerektiren haritalar kurulabilir.

Boyayıcı haritaları neden noktalardan oluşturuyor?

Her ülke, karenin rastgele bir noktaya diğer tüm noktalardan daha yakın olan bölgesidir; buna Voronoi diyagramı denir. Bu, dışbükey ülkelerden oluşan gerçekçi görünümlü haritalar verir ve iki ülke tam olarak bölgeleri bir sınır parçasını paylaştığında komşudur; uygulama bunu kesin olarak hesaplar.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Dört renk harita boyayıcısını açın