Dili değiştir

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Mathigon'da oturum açın

ya da

Yeni hesap     Şifreyi yenile     

Çizgeler ve Ağlar
Giriş
Königsberg Köprüleri
El sıkışma ve Partiler
Düzlemsel Çizgeler
Harita Boyama
Gezgin Satıcı Problemi
Scheduling Problems
Günlük Hayatta Çizgeler

Paylaş

İlerlemeyi Sıfırla

Bu, bu kurstaki tüm bölümler için ilerleme durumunuzu ve sohbet verilerinizi silecek ve geri alınamaz!

Sözlük

Soldaki anahtar kelimelerden birini seçin…

Çizgeler ve AğlarHarita Boyama

Okuma zamanı: ~10 min

Kimi haritalar için daha önce çizgelerden yararlandık. Daha yukarıdan baktıkça tek tek yollar ve köprüler kaybolur, onun yerine ülkelerin sınırlarını görmeye başlarız.

Bir haritayı ya da farklı bölgelerden oluşan bir çizimi renklendirirken komşu bölgeler için aynı rengi kullanamayız. Ayrıca olabildiğince az renk de kullanmak isteyebiliriz.

Satranç tahtası gibi kimi basit “haritalar” için sadece iki renk gerekir (siyah ve beyaz), ancak daha karmaşık haritalar için daha çok renge ihtiyaç duyarız.

ABD’nin eyaletlerini boyarken 50 renk fazlasıyla yeterli olacaktır, ancak çok daha azı da yetebilir. Aşağıdaki haritayı olabildiğince az renk kullanarak boyamaya çalışın.

Amerika Birleşik Devletleri

0 renk kullanıldı

Güney Amerika

0 renk kullanıldı

Almanya

0 renk kullanıldı

İngiltere

0 renk kullanıldı

Bütün bu haritalar sadece dört renk ile boyanabilir, fakat çok daha karmaşık haritalar için daha fazla rengin gerekeceğini hayal etmek çok zor değil. Aslında kimi haritalar için en azından dört gerekir: hepsi birbirine komşu dört ülke olduğu zaman.

Daha önce yaptığımız gibi ülkelerin ve sınırların olduğu bir haritayı düzlemsel bir çizgeye dönüştürebiliriz: her ülke bir olur ve ülkeler birbirine bir çizgi ile bağlanır.

Şimdi bu çizgenin noktalarını boyamak istiyoruz, ve aralarında çizgi olan iki noktanın farklı renkleri olsun istiyoruz.

1852’de botanik öğrencisi Francis Guthrie İngilteredeki bölgelerin haritasını renklendirmek zorundaydı. Denediği her harita için dört rengin yeterli olduğunu gözlemledi, ancak her harita için bunu gösterecek bir kanıt bulmayı başaramadı. Sonuçta bunun bir hayli zor bir soru olduğu ortaya çıktı ve dört renk teoremi adıyla anılmaya başladı.

İlerleyen 100 yılda pek çok matematikçi dört renk teoremi için “kanıtlar” yayınladılar, ama hepsinde sonradan hatalar bulundu. Bu geçersiz kanıtlardan bazıları o kadar ikna ediciydi ki içerdikleri hatayı bulmak 10 yıldan uzun sürdü.

Uzunca bir süre matematikçiler dört rengin yeterli olduğunu da kanıtlayamadılar, dörtten fazla renge ihtiyaç duyulan bir harita da bulamadılar.

1976’da Wolfgang Haken ve Kenneth Appel sonunda soruyu bilgisayar yardımı ile çözene kadar dört renk probleminde çok ilerleme kaydedilemedi. Haken ve Appel sonsuz harita seçeneğini 1936 özel duruma indirip her birisini bilgisayara kontrol ettirdiler, hesaplar toplamda 1000 saatten uzun sürdü.

Dört renk teoremi bilgisayar yardımıyla kanıtlanmış ilk ünlü matematiksel teorem, o günden bu güne kanıtlarda bilgisayar kullanmak çok daha yaygınlaştı ve daha az tepki görmeye başladı. Hızlı bilgisayarlar ve etkin algoritmalar sayesinde bugün dört renk teoremini kendi bilgisayarınızda bir kaç saatte kanıtlayabilirsiniz.

Haken ve Appel’in çalıştığı Illinois Urbana-Champaign Üniversitesi
Matematik Bölümünün posta işareti

Dört renk teoremi sadece bir düzlemde ya da küre yüzeyinde yer alan ve her ülkenin tek bir bölgeden oluştuğu haritalar için geçerli.

Tabi matematikçiler ülkelerin birden fazla bağlantısız bölgelerinin olabildiği imparatorluk haritalarını da çalıştılar, ve torus(simit şekli) gibi başka şekildeki gezegenlerin haritalarını da. Bu durumlarda dörtten fazla renge ihtiyacınız olabilir ve kanıtı yapmak daha da zorlaşıyor.

Torus üzerindeki bu haritayı boyamak için yedi renk gerekli.

Archie