Sözlük

Soldaki anahtar kelimelerden birini seçin…

Grafikler ve AğlarHarita Boyama

Okuma zamanı: ~15 min
Bu sayfa otomatik olarak çevrilmiştir ve hatalar içerebilir. Çevirileri incelememize yardımcı olmak istiyorsanız lütfen iletişime geçin!

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

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

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 haline gelir ve ülkeler bir kenarla bağlanır:

Ş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 Francis Guthrie İngiltere'de bir il haritasına renk vermek zorunda kaldı. Denediği herhangi bir harita için dört rengin yeterli göründüğünü gözlemledi, ancak tüm haritalar için işe yarayan bir kanıt bulamadı. Bu son derece zor bir problem olarak ortaya çıktı ve dört renk teoremi olarak biliniyordu.

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.

Wolfgang Haken ve Kenneth Appel'in nihayet çözmek için bir bilgisayar kullandıkları 1976'ya kadar dört renk probleminde çok az ilerleme kaydedildi. Her biri toplamda 1000 saatten fazla süren bir bilgisayar tarafından kontrol edilen 1936 özel vakasına sonsuz sayıda olası haritayı indirdiler.

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.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

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.

This map on a torus requires seven colours.