Grafik teorisinin uygulamaları
Düzlemsel grafikler
G grafiğinin, bir düzlemde, köşelerin tümünün ayrı noktalar olacağı, kenarların basit eğriler olduğu ve uçları dışında iki kenarın birbiriyle buluşmadığı şekilde düzlemsel olduğu söylenir. Örneğin, K 4, dört nokta ile ilgili tam bir grafiktir, Şekil 4A gösterdiği gibi, düzlemseldir.
Her ikisi de aynı grafikten kenarların alt bölümleri ile elde edilebilirse, iki grafiğin homeomorfik olduğu söylenir. Örneğin, Şekil 4A ve Şekil 4B'deki grafikler homeomorfiktir.
K m, n grafik tepe grubu iki alt, m noktalar ile bir ve n köşenin diğer ayrılabilir olan bir grafiktir. Aynı altkümenin herhangi iki köşesi bitişik değildir, oysa farklı alt kümelerin iki köşesi bitişiktir. Polonyalı matematikçi Kazimierz Kuratowski 1930'da şu ünlü teoremi kanıtladı:
Düzlemsel olarak bir grafik G için gerekli ve yeterli koşul bu ya K bir alt grafiğinin homeomorphic içermemesi olan 5 ya da K 3,3, Şekil 5 de gösterilen.
Bir grafik G bir basit büzülme yeni grafik G G bir dönüşümdür 1 iki bitişik noktalar u ve G υ G ağırlık yeni tepe ile ikame edilen, örneğin 1 ve w, G bitişiktir 1 tüm vertices u veya υ, G'de bitişiktir. G *, G'den bir dizi temel kasılma dizisi ile elde edilebilirse, G * grafiğinin G kasılması olduğu söylenir. Aşağıdakiler, Alman matematikçi K. Wagner'in 1937'deki bir düzlemsel grafiğinin başka bir karakterizasyonu.
Bir grafik düzlemsel halinde elde edilmiştir ve K, kısaltılabilir değildir, yalnızca 5 veya K 3,3.
Dört renkli harita sorunu
Yüzyılı aşkın bir süredir dört renkli harita sorununun çözümü, onu deneyen her analisti kaçırdı. Sorun Möbius'un dikkatini çekmiş olabilir, ancak ilk yazılı referans 1852'de bir Francis Guthrie'den Augustus De Morgan öğrencisi olan kardeşi için bir mektup gibi görünüyor.
Sorun, düzlemsel haritalarla ilgilidir - yani, düzlemin basit kapalı eğrilerle sınırlanmış, örtüşmeyen bölgelere alt bölümleri. Coğrafi haritalarda deneysel olarak, denendiği kadar çok özel durumda, bölgelerin renklendirilmesi için en fazla dört renge ihtiyaç duyulduğu, böylece ortak bir sınırı paylaşan iki bölgenin her zaman farklı renkte olduğu ve en az dört rengin gerekli olduğu bazı durumlar. (Amerika Birleşik Devletleri'ndeki Colorado ve Arizona eyaletleri gibi yalnızca bir noktada toplanan bölgelerin ortak bir sınırı olduğu düşünülmemektedir). Bu ampirik gözlemin resmileştirilmesi, “dört renkli teorem” olarak adlandırılan şeyi oluşturur. Sorun, her düzlemsel harita için durumun böyle olduğu iddiasını kanıtlamak veya çürütmektir. Üç rengin yeterli olmayacağını kolayca gösterirken, beş rengin yeterliliği 1890'da İngiliz matematikçi PJ Heawood tarafından kanıtlandı.
1879'da bir İngiliz olan AB Kempe, dört renkli sorunun çözümünü önerdi. Heawood, Kempe'nin argümanının kusurlu olduğunu göstermesine rağmen, kavramlarından ikisi daha sonraki araştırmalarda verimli oldu. Kaçınılmazlık denilen bunlardan biri, dört konfigürasyondan her birinin olmadığı bir haritayı inşa etmenin imkansızlığını doğru bir şekilde ifade eder (bu konfigürasyonlar, biri üç, biri dört ve beşi olmak üzere iki komşusu olan bir bölgeden oluşur). İkinci kavram olan indirgenebilirlik, ismini Kempe'nin geçerli kanıtından alır, en az beş renk gerektiren ve dört (veya üç veya iki) komşu bir bölge içeren bir harita varsa, beş gerektiren bir harita olması gerekir. daha az sayıda bölge için renkler. Kempe'nin beş komşusu olan bir bölge içeren bir haritanın indirgenebilirliğini kanıtlama girişimi hatalıydı, ancak 1976'da Amerika Birleşik Devletleri'nden Kenneth Appel ve Wolfgang Haken tarafından yayınlanan bir kanıtta düzeltildi. Kanıtları bazı eleştirilere neden oldu, çünkü her biri 500.000 mantıksal işlem içeren 1.936 ayrı vakanın değerlendirilmesini gerektiriyordu. Appel, Haken ve ortak çalışanları, büyük bir dijital bilgisayarın bu ayrıntıları ele almasını mümkün kılan programlar geliştirdi. Bilgisayarın görevi yerine getirmesi 1.000 saatten fazla sürdü ve ortaya çıkan resmi kanıt birkaç yüz sayfa uzunluğunda.
Euler döngüleri ve Königsberg köprüsü sorunu
Bir çoklu grafik G, boş olmayan bir V (G) köşeleri setinden ve her bir çifte f ≥ 1 frekansı eklenmiş V (G) 'nin farklı elemanlar grubunun sıralanmamış çiftlerinin bir alt kümesinden (E (G) oluşur. F frekansı olan çift (x 1, x 2) E (G) ye aitse, x 1 ve x 2 köşeleri f kenarlarıyla birleştirilir.
Multigraph G'nin bir Euler döngüsü, her bir kenarın tam olarak bir kez göründüğü kapalı bir zincirdir. Euler, bir çoklu grafiğin bir Eulerian döngüsüne sahip olduğunu ve sadece bağlıysa (yalıtılmış noktaların dışında) ve tek dereceli köşelerin sayısı sıfır veya iki ise gösterdi.
Bu sorun ilk olarak aşağıdaki şekilde ortaya çıktı. İki kolunun birleşmesiyle oluşan Pregel Nehri, Königsberg kasabasından geçiyor ve Kneiphof adasının her iki tarafından akıyor. Şekil 6A'da gösterildiği gibi yedi köprü vardı. Kasaba halkı, bir yürüyüşe çıkmanın ve her köprüyü sadece bir kez geçmenin mümkün olup olmadığını merak etti. Bu, Şekil 6B'deki multigraf için bir Euler döngüsü bulmakla eşdeğerdir. Euler bunun imkansız olduğunu gösterdi çünkü garip düzenin dört köşesi var.
