Grafikler ve AğlarHarita Boyama
Belli haritalarla grafik teorisini zaten kullandık. Uzaklaştıkça, bireysel yollar ve köprüler kayboluyor ve bunun yerine tüm ülkelerin ana hatlarını görüyoruz.
Bir haritayı - veya farklı bölgelerden oluşan başka bir çizimi - renklendirirken, bitişik ülkeler aynı renge sahip olamaz. Mümkün olduğunca az farklı renk kullanmak da isteyebiliriz.
Bir satranç tahtası gibi bazı basit “haritalar” sadece iki renge (siyah beyaz) ihtiyaç duyar, ancak çoğu karmaşık harita daha fazlasına ihtiyaç duyar.
ABD eyaletlerinin haritasını renklendirirken, 50 renk yeterlidir, ancak çok daha azı gereklidir. Aşağıdaki haritaları olabildiğince az renkle boyamayı deneyin:
United States
South America
Germany
England
Bu haritaların hepsi sadece dört farklı renkle renklendirilebilir, ancak diğer çok karmaşık haritaların daha fazla renge ihtiyacı olabileceğini hayal etmek zor değildir. Aslında, bazı haritaların hepsi birbirine bağlı dört ülke içerdiğinde en az dört renge ihtiyaç duyar.
Daha önce olduğu gibi, ülkeleri ve sınırları olan bir haritayı düzlemsel bir grafiğe dönüştürebiliriz: her ülke
Şimdi bir grafiğin köşelerini renklendirmek istiyoruz ve bir kenarla bağlanırlarsa iki köşenin farklı bir rengi olmalıdır.
1852'de, botanik öğrencisi
Takip eden 100 yıl boyunca, birçok matematikçi sadece daha sonra bulunacak hatalar için dört renk teoremine “kanıt” yayınladı. Bu geçersiz ispatlardan bazıları o kadar ikna ediciydi ki hataları bulmak 10 yıldan fazla sürdü.
Uzun bir süre, matematikçiler ya dört rengin yeterli olduğunu kanıtlayamadı ya da dörtten fazla renge ihtiyaç duyan bir harita bulamadılar.
Dört renk teoremi, bilgisayar kullanılarak kanıtlanmış ilk bilinen matematiksel teoremdir, o zamandan beri çok daha yaygın ve daha az tartışmalı hale gelen bir şeydir. Daha hızlı bilgisayarlar ve daha verimli bir algoritma, bugün bir dizüstü bilgisayarda dört renk teoremini birkaç saat içinde kanıtlayabileceğiniz anlamına gelir.
Dört renk teoremi yalnızca düz bir düzlemde veya bir küre üzerinde ve tüm ülkelerin tek bir alandan oluştuğu haritalar için çalışır.
Ancak matematikçiler, ülkelerin birden fazla bağlantısız bileşenden oluşabileceği imparatorluk haritalarına ve bir torus (çörek şekli) gibi farklı şekilli gezegenlerdeki haritalara da baktılar. Bu durumlarda dörtten fazla renge ihtiyacınız olabilir ve provalar daha da zorlaşır.