Dört renk teoremi harita boyayıcı
Bir harita ne kadar karmaşık olursa olsun, sınır paylaşan ülkeler asla aynı rengi almayacak şekilde onu boyamak için dört renk her zaman yeterlidir. Bu önerme bir çocuğun boya kalemleriyle sınayabileceği kadar basittir, ama kanıtlanması bir asırdan fazla sürdü ve bir bilgisayar gerektirdi. Rastgele bir haritayı kendiniz boyayın, hangi sınırların çakıştığını görün, ardından üç yöntemin bu işi yapışını izleyin: bazen beşinci bir renge ihtiyaç duyan hızlı bir açgözlü kuraldan her zaman dört renkle yetinen bir geri izleme aramasına kadar. Bir renk seçin ve ülkeleri boyamak için üzerlerine tıklayın; iki komşu aynı rengi paylaştığında aradaki sınır kırmızıya döner. Yalnızca bir köşede birbirine değen ülkeler aynı rengi paylaşabilir. Ya da işi bilgisayara bırakın: bir yöntem seçin ve onu izlemek için Çöz'e, hamleleri tek tek takip etmek için Adım'a basın. En az renk, bu haritanın üç, hatta iki renkle yetinip yetinemeyeceğini kontrol eder. Yeni harita başka bir harita çizer, Komşuları göster ise sınır paylaşan ülkelerin ağını çizer.
Nasıl çalışır
- Ülke sayısını seçip Yeni harita'ya basın ya da gösterilen haritayla başlayın.
- Bir renk seçin ve ülkeleri boyamak için üzerlerine tıklayın; komşuların çakıştığı yerlerdeki kırmızı sınırlara dikkat edin.
- Bir yöntem seçin ve haritayı boyayışını izlemek için Çöz'e ya da Adım'a basın; bu haritanın kaç renge ihtiyaç duyduğunu görmek için de En az renk'e basın.
Haritalardan çizgelere
Her ülkeye bir nokta koyun ve ülkeleri sınır paylaşan iki noktayı birleştirin. Harita bir çizgeye dönüşür ve haritayı boyamak, birleştirilen noktalar farklı renkte olacak şekilde noktaları boyamakla aynı şeydir. Haritalar düz bir yaprak üzerine çizildiği için bu çizgeler düzlemseldir: çizgiler kesişmeden çizilebilirler. Bir köşede buluşan dört kare gibi yalnızca tek bir noktada buluşan ülkeler komşu değildir. Dört renk teoremi, her düzlemsel çizgenin dört renkle boyanabileceğini söyler. Mevcut haritanın çizgesini görmek için Komşuları göster'i açın.
Boyamanın üç yolu
Açgözlü boyama ülkeleri, en çok komşusu olanlardan başlayarak teker teker ele alır ve her birine komşularının kullanmadığı ilk rengi verir. Hızlıdır ama ileriyi göremez ve bazı haritalarda beşinci, hatta altıncı bir renge başvurur. Daniel Brélaz'ın 1979'da geliştirdiği DSATUR, her seferinde komşuları hâlihazırda en çok farklı rengi gösteren ülkeyi seçer; bu da genellikle o tuzaktan kaçınmayı sağlar. Geri izleme renkleri sırayla dener ve bir ülkeye uygun renk kalmadığında en son seçimlerini geri alıp yeniden dener; bazen birçok kez geri döndükten sonra da olsa her zaman dört renkli bir boyama bulur.
Sık sorulan sorular
Dört renk neden her zaman yeterlidir?
Kimse kısa bir gerekçe bulamadı. Kenneth Appel ve Wolfgang Haken'in 1976'daki kanıtı, her haritanın 1.936 küçük konfigürasyondan birini içermek zorunda olduğunu ve bunların her birinin çıkarılıp boyamanın sonradan geri getirilebileceğini gösterdi; hepsini kontrol etmek bin saatten fazla bilgisayar zamanı aldı. Neil Robertson, Daniel Sanders, Paul Seymour ve Robin Thomas'ın 1996'daki daha basit bilgisayar kanıtı 633 konfigürasyon gerektirir; 2005'te ise Georges Gonthier bir kanıtı Coq ispat asistanıyla tamamen doğruladı.
Bazı haritalar dört rengin hepsine ihtiyaç duyar mı?
Evet. Her biri diğer üçüne değen dört ülke, örneğin bir halka hâlinde üç ülkeyle çevrili bir ülke, dört renk gerektirir. Ancak birçok harita üç renkle yetinir ve En az renk bunu ekrandaki harita için bulur. Bir haritanın üç renkle boyanıp boyanamayacağına genel olarak karar vermek, dört renk her zaman yetse de zor, NP-tam bir problemdir.
Açgözlü yöntem neden bazen beş renk kullanır?
Her ülkeyi bir kez boyar ve kararını asla değiştirmez. Erken bir seçim, sonraki bir ülkeyi dört rengin hepsiyle çevrili bırakabilir ve tek çıkış yolu beşinci bir renktir. Geri izleme ise geri dönüp önceki seçimleri değiştirirdi.
Teorem başka yüzeylerde de geçerli mi?
Kürede evet: küre düzlemle aynıdır. Bir simidin yüzeyi olan torusta bazı haritalar yedi renk gerektirir ve Percy Heawood'un gösterdiği gibi yedi renk her zaman yeterlidir. Ülkeler, sömürgeleri olan bir devlet gibi birkaç ayrı parçadan oluşabiliyorsa dört renk artık yetmez.
Bir sunucuya herhangi bir şey gönderiliyor mu?
Hayır. Harita, boyama yöntemleri ve kontrol tarayıcınızda çalışır. Ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git