Dört Renk Teoremi

Dört renk varsayımı ilk olarak 200 yıl kadar önce ortaya atıldı ve sonunda 1976'da kesin olarak kanıtlandı. Eski fikirlerin, matematiğin farklı alanlarındaki yeni keşifler ve tekniklerle bir araya gelerek bir soruna yeni yaklaşımlar sağlamasının olağanüstü bir örneğidir. Ayrıca, görünüşte basit bir sorunun nasıl 'çözüldüğü' düşünülürken daha sonra nasıl daha karmaşık hale geldiğine dair bir örnektir ve bir bilgisayarın bir matematiksel teoremi kanıtlamaya dahil olduğu ilk muhteşem örnektir.

Herhangi bir haritanın yalnızca dört renk kullanılarak boyanabileceği varsayımı ilk olarak, New University College London'daki ilk matematik profesörü olan Augustus De Morgan'ın (1806-1871), ünlü İrlandalı matematikçi arkadaşı William Rowan Hamilton'a (1805-1865) 1852'de yazdığı bir mektupta ortaya çıktı. Bu varsayım, De Morgan'a, ağabeyi Francis (daha sonra Cape Town Üniversitesi'nde matematik profesörü oldu) adına, öğrencilerinden biri olan Frederik Guthrie tarafından önerilmişti.

Basitçe tarif edilen ancak ispatı çok zor olan bu problem, o dönemde birçok matematikçinin hayal gücünü ele geçirdi. 1860'ların sonlarında De Morgan problemi ve ispatını Amerika'ya bile götürdü; burada ünlü bir matematikçi ve astronom olan Benjamin Peirce (1809-1880) gibi başkaları da mantıksal yöntemlerini geliştirmenin bir yolu olarak bununla ilgilenmeye başladı.

De Morgan, dört bölgenin bulunduğu ve her birinin diğer üç bölgeye değdiği bir haritada, bunlardan birinin diğerleri tarafından tamamen çevrelenmiş olduğu gerçeğini kullandı. Bunu kanıtlamanın bir yolunu bulamadığı için, bunu bir aksiyom olarak, yani kanıtının temeli olarak kullandı.

1878'de Arthur Cayley (1821-1895) Londra Matematik Derneği'nin bir toplantısında De Morgan'ın orijinal sorusuna bir çözüm bulunup bulunmadığını sordu, ancak bir miktar ilgi olmasına rağmen, kimse önemli bir ilerleme kaydedememişti. Cayley bu soruna ilgi duymaya başladı ve 1879'da Haritaların renklendirilmesi üzerine kısa bir makale yayınladı ve burada bir kanıt denemesindeki zorluklardan bazılarını açıkladı. Soruna yaklaşım biçimine bazı önemli katkılarda bulundu. 'Belirli bir harita zaten dört renkle başarıyla renklendirilmişse ve bir alan daha eklersek, aynı renklendirmeyi koruyabilir miyiz?' sorusu, matematiksel tümevarımın uygulanmasına yol açan başka bir araştırma hattının başlangıcı oldu.

Cayley ayrıca, sınırların birleşme biçimini kısıtlayarak sorunun bir versiyonunu çözmenin mümkün olduğunu gözlemledi. Örneğin, sadece üç ülkenin birleştiği haritalarda, bir tepe noktasında birleşen üç kenar bulunur. Bunlara 'kübik haritalar' denir ve ayrıca, bir harita dört renkle renklendirilebiliyorsa, sınırda sadece üç renk görünecektir.

Denizle çevrili bir adanın haritasını hayal edin. Ada ülkelerinin renklendirilmesinde denizi tek bir bölge olarak sayıyoruz. Bazı ülkelerin sadece iki sınırı (bir digon), bazılarının üç sınırı (bir üçgen gibi), bazılarının dört sınırı (bir kare) ve bazılarının beş sınırı (bir beşgen) veya daha fazlası olabilir.

1813 yılında, Euler'in çokyüzlüler için formülü, çokyüzlüyü bir düzleme yansıtarak ve böylece katının netini oluşturarak Augustin Cauchy (1759-1857) tarafından iki boyuta uyarlandı. Bu şekilde formül f + v - e = 1.

Dört renk problemini ele almanın bir başka yolu da bunun yanlış olduğunu varsaymak ve bunun nereye varacağını görmektir. Heawood, 1890 yılında Kempe'nin ispat yöntemindeki en büyük hatayı bulmasına rağmen, dört renk teoremini ispatlayamadı, ancak önemli bir atılım yaparak tüm haritaların beş renkle boyanabileceğini kesin olarak ispatladı.

Cauchy'nin Euler formülünün kanıtı, herhangi bir çokyüzlünün ağının, üçgen olmayan yüzleri üçgenlere dönüştürmek için kenarlar eklenerek üçgenleştirilebileceği fikrini de içeriyordu. Daha sonra kenarları tek tek sildiği bir prosedür geliştirdi ve Euler formülünün her adımda korunabileceğini gösterdi.

Euler Formülünün Cauchy Kanıtı

Cauchy'nin 1813'teki Euler Formülü kanıtı, bir düzlem ağı elde etmek için bir polihedronun izdüşümünün fikriyle başladı. Ayrıca herhangi bir ağın üçgenleştirilebileceğini gösterdi ve Euler Formülü kanıtı o zamanlar kabul edildi.

Prensip olarak, her çokgensel ağ üçgenleştirilebilir. Cauchy'nin argümanı, diyagram (a)'dan dış kenarları tek tek kaldırmak ve diyagram (b)'deki gibi bir aşamaya ulaştığında tüm T üçgenini kaldırarak Euler formülünü korumaktı. On dokuzuncu yüzyılın başlarındaki birçok matematikçi, bu prosedürün tüm çokyüzlüler için Euler formülünün bir kanıtını gösterdiği konusunda hemfikirdi.

Yirminci yüzyılın ilk yarısında matematikçiler, karmaşık haritaları tanımlanabilen ve sınıflandırılabilen özel durumlara indirgemek, onların özel özelliklerini araştırmak için bu tür teknikleri değiştirmeye odaklandılar ve test edilebilecek asgari bir harita yapılandırmaları kümesi fikrini geliştirdiler.

İlk etapta, kümenin yaklaşık 9.000 üye içerdiği düşünülüyordu ki bu çok büyük bir görevdi ve bu yüzden matematikçiler, onlar adına test yapabilecek algoritmalar yazmak için bilgisayar tekniklerine yöneldiler. Algoritmalar, Kempe'nin zincirler hakkındaki orijinal fikrinin değiştirilmiş versiyonlarını, minimal kümenin üye sayısını azaltmak için diğer tekniklerle birlikte kullandı.

John Koch ile indirgenebilirlik problemi üzerinde işbirliği yaptıktan sonra, 1976'da Illinois Üniversitesi'nde Kenneth Appel ve Wolfgang Haken sonunda test problemini 1.936 yapılandırmalı kaçınılmaz bir kümeye indirgediler ve Dört Renk Varsayımı için tam bir çözüme ulaşıldı. Haritaların indirgenebilirliğini tek tek kontrol etme problemi farklı programlar ve farklı bilgisayarlarla iki kez kontrol edildi. Kanıtları, beş renk gerektiren mümkün olan en az sayıda bölgeye sahip en az bir haritanın var olamayacağını gösterdi.

İlk ispattan bu yana 4 renkli haritalar için daha verimli algoritmalar bulunmuş ve 1994 yılına gelindiğinde kaçınılmaz konfigürasyon kümesi 633'e düşürülmüştür.