Dört Renkli Harita Problemi Sonunda Nasıl Çözüldü?

1852’de Güney Afrikalı bir matematikçi, sonsuz tartışmayı tetikleyen, arkasında ters çevrilmiş yayınların izini bırakan ve matematiğin ilkelerini esneten bir çözümle sonuçlanan, görünüşte basit bir soru sordu.

Bu kadar çok sorun yaratan renk muamması: Bir haritayı komşu eyaletlerin veya belirlenmiş diğer bölgelerin aynı renk tonuna sahip olmaması için renklendirmek için gereken en az sayıda renk nedir? İşte nasıl çalıştığı. Aşağıdaki bitişik ABD haritasına göz atın.

Biraz çıplak kemik görünüyor. Haritacılar, haritaları daha canlı hale getirmek ve sınırlarını net bir şekilde vurgulamak için bölgeleri şu şekilde renklendirme eğilimindedir:

Doğal olarak, komşu devletlerin aynı renge sahip olmasını istemiyoruz çünkü bu, sınırları daha karmaşık hale getirir. Bu kısıtlama altında, yukarıdaki haritayı doldurmak için dört renk kullandık. Bunu sadece üç kişiyle yapabilir miydik? Diğer haritalar beş veya altı gerektirebilir mi?

Haritanın gerçek coğrafyaya karşılık gelmesi gerekmez; düz bir yüzeyin farklı bölgelere bölünmesi uygundur. Soru, verilen herhangi Böyle bir haritada, bitişik iki bölge aynı renge sahip olmayacak şekilde her bölgeyi doldurmak için gereken minimum renk sayısı nedir? Bazı temel kurallar: her bölge bitişik olmalıdır, bu nedenle teknik olarak Michigan düzeni ihlal ediyor çünkü Michigan Gölü eyaleti bağlantısız iki parçaya ayırıyor. İki bölgenin bitişik olarak sayılması için, bazı bitişik sınırları paylaşmaları gerekir; tek bir noktaya (veya ayrık noktalar grubuna) dokunmak uygun değildir. Örneğin, Utah ve New Mexico ünlü olarak yalnızca bir köşeye dokun ve bu nedenle amaçlarımız için komşu saymayın.

Belirlenen kurallarla, şaşırtıcı cevapları olan bazı sorular burada. Diyelim ki birkaç bin bölge içeren karmaşık bir harita içeren büyük bir poster bastırdım. Haritanın iki renkle boyanıp boyanamayacağını belirlemeniz ne kadar sürer? Üç renk mi? Dört renk mi? mutlaka gerek yok bulmak bir renklendirme, sadece her bir renk sayısı için bir renklendirme olup olmadığına karar verin. Merakla, bu üç görev neredeyse aynı görünse de, her birinin tamamlanması için radikal olarak farklı süreler gerekiyor. En iyi bilinen yöntemleri kullanarak:

• İki rengin yeterli olup olmadığına karar vermek yaklaşık bir saat sürer. Bunu yapmak için herhangi bir bölgeyi seçin ve bunun için bir renk seçin, mesela kırmızı. Bu, bölgenin tüm komşularını diğer renge, örneğin maviye zorlar. Sırayla, tüm onların komşular kırmızı olur ve harita boyunca yayılır. Sonunda ya komşu bölgelerin aynı rengi paylaştığı bir çatışmayla karşılaşırsınız ki bu durumda “iki renk” olmaz ya da renkler tüm haritaya sorunsuz bir şekilde yayılır ve bu durumda geçerli bir renklendirme bulursunuz. Renklendirme başına 1 saniye hızında 3.000 bölgeyle yapılan bir zarfın arkası hesaplaması, iyi harcanan 50 dakika sağlar.
• Haritanın sadece iki renkle doldurulamayacağını varsayalım. Üç rengin yeterli olup olmadığına karar vermek daha uzun sürer. Öğleden sonra seni geçerdi. İşe yarayan birini ararken, siz öfkeyle sonsuz konfigürasyonları karalarken haftalar takvimden soyulur. Devam etmek için devam eden görevi çocuklarınıza, onların da çocuklarına devretmeniz gerekir. Bu haritanın üç rengini bulmaktan başka hiçbir şeye adanmamış nesiller boyu, güneş kaçınılmaz olarak Dünya’yı milyarlarca yıl içinde yutacağından ve bizi bir cevaba çok az yaklaştırarak bu aptalca çabaya bir son verdiğinden, iş yükünü azaltmayacaktır. Rastgele bir haritanın üç renge sahip olup olmadığını belirlemek zordur. Burada “sert”, bir sınıfa girdiğini gösteren teknik bir terimdir. hesaplama problemleri denilen zaman alan zorluklarla ünlüdür. NP-tam problemler. Bu sınıftaki problemler için, olası her çözümü az çok kaba kuvvetle aramaktan daha hızlı yöntemler bilmiyoruz. Bu arama alanı, sorunun boyutu arttıkça katlanarak büyür. Yalnızca birkaç bölge içeren küçük bir harita için, çalışan bir tane bulana kadar (veya olmadığı sonucuna varıncaya kadar) mümkün olan her üç rengi ayrıntılı bir şekilde inceleyebiliriz. Ancak binlerce bölge içeren haritalara üç renk atamanın yollarının sayısı o kadar astronomik ki, ayrıntılı aramayı umutsuz kılıyor.
• Ve dört renk? Bu yaklaşık bir saniye veya “evet” demeniz gereken süreyi alır çünkü Her harita dört renk ile renklendirilebilir. Bu rezil ve uzun süredir tartışılan dört renk teoremidir.

Francis Guthrie, dört renk teoremini ilk olarak 1852’de İngiltere’nin ilçelerinin düzgün bir şekilde doldurmak için yalnızca dört renge ihtiyaç duyduğunu fark ettiğinde tahmin etti. Bu kuralın herhangi bir haritaya genellenebileceğinden şüpheleniyordu, ancak herhangi bir anaokulu öğrencisi soruyu anlasa da, ne kendisi ne de meslektaşları bunu kanıtlayamadı. Her bölgenin birbirine komşu olduğu aşağıdaki şemada gösterildiği gibi, üç rengin her zaman onu hackleyemeyeceği açıktı.

Ama kimse beş renk gerektiren bir harita bulamadı. Ünlü matematikçi Augustus De Morgan bu soruna kafayı takmış ve takıntı haline gelmiş ve şu sonuca varmıştır: yeni aksiyomGuthrie’nin varsayımını çözmek için matematiğin temellerine eklenmesi gereken -matematikte kanıt olmadan doğru olduğu varsayılan, daha karmaşık ifadelerin türetilebildiği bir ifadedir.

Hararetli hayal kırıklığı, görünüşte 1879’da, dört rengin her zaman yeterli olduğuna dair bir kanıtın ortaya çıkmasıyla sona erdi. Bu, bir yıl sonra ikinci bir bağımsız kanıtla vurgulandı. Sorun çözüldükten ve ödüller dağıtıldıktan sonra büyülenmiş matematikçiler normal araştırma programlarına geri döndüler. Bazıları hariç. İlk ispatın yayınlanmasından on bir yıl sonra, ikisi birden ispatlar bozuldu ve kaygan dört-renk teoremi statüsünü dört-renk varsayımına geri döndürdü. Orijinal kanıtta bir boşluk olduğunu ortaya çıkaran Percy Heawood, bunu kanıtlayarak biraz ilerleme kaydetti. beş renkler her zaman herhangi bir haritayı doldurmak için yeterlidir. Bu, matematik dünyasını oldukça utanç verici bir konumda bıraktı. Bu kadar basit görünen bir problemin iki cevabı vardı -dört ya da beş- ama kimse hangisinin olduğunu bilmiyordu. Neredeyse bir asır daha bu şekilde duracaktı.

Hiç kimse beş renk gerektiren bir harita bulamadı, ancak birinin olasılığını tamamen ortadan kaldırmak zor kaldı. Sonsuz sayıda harita olduğu için, her birini tek tek kontrol etmek asla mümkün değildir. Çözüme yönelik kilit bir teknik, sorunu sonlu bir dizi vakaya indirgemeyi içeriyordu. abilir tek tek kontrol edilmelidir. Sonsuzdan sonluya sıçrama çok büyük görünüyor, ancak kontrol edilmesi gereken canavarca vaka sayısı, herhangi bir kişinin manuel olarak işleyebileceğinden çok daha fazlaydı. Böylece matematikçiler Kenneth Appel ve Wolfgang Haken cüretkar bir fikre döndüler: bunun yerine bunları işlemek için bir bilgisayar programlayın. 1976’da, yıllarca süren ince ayardan ve bin saatin üzerinde bilgisayar süresinden sonra, algoritmaları her vakayı kapsamlı bir şekilde kontrol etmeyi bitirdi ve dört renk teoremi kuruldu. İspatında bilgisayar kullanan ilk büyük teoremdi.

Matematik dünyası eşit ölçüde kutlama ve dehşetle alev alev yanıyordu. Appel ve Haken’in meslektaşlarından biri olan Bill Tutte, “Kraken’ı Vur” diğerleri ise bilgisayarların insan yaratıcılığına tecavüz ettiği düşüncesini hor görüyordu. İlişki aynı zamanda matematik camiasında felsefi bir sorun teşkil etti. İnsanlar tarafından doğrulanamayan bir kanıt mı? hiç bir kanıt olarak say? Birçoğu, ondan önceki iddia edilen her iki kanıt gibi, çalışmanın sonunda geri çekilmesini bekliyordu. bu New York Times eşit reddetti dört renk teoreminin ispatları nedeniyle ilk önce duyuruyu rapor etmek”zaten hepsi yalan”

Sonraki on yıllarda bilgisayar destekli kanıtı çürütmek için yapılan birden çok girişim başarısız oldu. Matematikçiler o zamandan beri kanıtı büyük ölçüde basitleştirdiler ve bilgisayar kodunu doğruladılar, ancak bugüne kadar, bilgisayarların yardımı olmadan teoremin hiçbir kanıtı bilinmiyor. Dört renk teoremi artık geniş çapta bir gerçek olarak kabul ediliyor, ancak hala üzerinde bir özlem var. Sistematik olarak bir yığın konfigürasyonu analiz eden bir bilgisayar programı tam olarak açıklamaz. Neden her harita dört renkle doldurulabilir. Matematikçiler artık bilgisayarları keşif ortakları olarak kabul etseler de, bugün hala bu renkli bulmacanın daha aydınlatıcı bir kanıtını arıyorlar.

Bu bir görüş ve analiz yazısıdır ve yazar veya yazarlar tarafından ifade edilen görüşler mutlaka o kişiye ait değildir. Bilimsel amerikalı.