Graf teorisi
Noktalar ve aralarındaki çizgiler: graf bundan ibarettir. Yine de aynı resim bir yol haritasını, bir arkadaş ağını, bir molekülü ve interneti anlatır; onunla ilgili sorabileceğiniz sorular da, kaç renge ihtiyaç duyduğundan tek çizgide çizilip çizilemeyeceğine kadar, 1736'dan beri matematikçileri meşgul ediyor.
Köşeler ve kenarlar
Bir grafın köşeleri (bunlara düğüm de denir) ve her biri iki köşeyi birleştiren kenarları vardır. Köşelerin nereye çizildiği önemli değildir, yalnızca hangi çiftlerin birleştiği önemlidir; bu yüzden aynı graf kâğıt üzerinde çok farklı görünebilir. Oyun alanındaki graflar basittir: hiçbir kenar bir köşeyi kendisine bağlamaz ve iki köşe arasında en fazla bir kenar bulunur. n köşeli bir grafta en fazla n(n − 1) / 2 kenar olabilir; bunların hepsine sahip bir grafa tam graf denir ve K5, beş köşeli tam graftır.
Dereceler ve el sıkışma lemması
Bir köşenin derecesi, ona bağlı kenarların sayısıdır. Tüm dereceleri toplarsanız kenar sayısının tam iki katını elde edersiniz, çünkü her kenarın iki ucu vardır ve her uçta bir kez sayılır. Bu, el sıkışma lemmasıdır: herhangi bir grupta, kişi kişi sayılan el sıkışmaların toplamı, el sıkışma sayısının iki katıdır. Bu aynı zamanda derecesi tek olan köşelerin sayısının her zaman çift olduğu anlamına gelir. Her köşesinin derecesi aynı k sayısı olan grafa k-düzenli denir.
Bağlantılı graflar, ağaçlar ve döngüler
Kenarlar boyunca her köşeden diğer her köşeye gidebiliyorsanız graf bağlantılıdır; değilse bileşen adı verilen parçalara ayrılır. Döngü, hiçbir köşeden iki kez geçmeden başladığı yere dönen bir turdur; en kısa döngünün uzunluğu grafın çevresidir. Döngüsü olmayan bağlantılı bir graf ağaçtır ve n köşeli bir ağacın her zaman tam olarak n − 1 kenarı vardır: bir kenar eksik olsa parçalanır, bir kenar fazla olsa döngü oluşur. Her bağlantılı graf bir kapsayan ağaç, yani kenarların yalnızca bir kısmını kullanarak tüm köşelere ulaşan bir ağaç içerir.
İki parçalı graflar ve boyama
Köşeleri, hiçbir kenar aynı renkte iki köşeyi birleştirmeyecek şekilde boyayın. Bunu sağlayan en az renk sayısı kromatik sayıdır. Tek renk yalnızca hiç kenar yoksa yeterlidir. İki renk tam olarak graf iki parçalı olduğunda yeterlidir: köşeleri iki tarafa ayrılır ve her kenar bir taraftan diğerine geçer. Dénes Kőnig 1936'da bunun, tek uzunlukta hiç döngü olmamasıyla aynı şey olduğunu gösterdi, çünkü tek uzunluktaki bir döngüde iki renk dönüşümlü olarak sıralanamaz. Üç ya da daha fazla renk için böyle basit bir test bilinmiyor: üç rengin yetip yetmediğine karar vermek NP-tam bir problemdir, bu yüzden programlar, oyun alanının yaptığı gibi, arama yapar.
Bir örnek: Petersen grafı
Bir A–B–C–D–E beşgeni ve onun içinde beş uçlu bir F–H–J–G–I yıldızı alın; beşgenin her köşesini yıldızın bir ucuna bağlayın: A–F, B–G, C–H, D–I ve E–J. İşte 10 köşeli ve 15 kenarlı Petersen grafı. Her köşenin derecesi 3'tür, dolayısıyla derecelerin toplamı 30, yani 15'in iki katıdır. En kısa döngüsünün uzunluğu 5'tir, yani hiç üçgen içermez; ama beşgen tek uzunlukta bir döngüdür, bu yüzden graf iki parçalı değildir ve 3 renge ihtiyaç duyar. Herhangi iki köşe arasında en fazla 2 kenar vardır, dolayısıyla çapı 2'dir. On derecenin hepsi tektir, bu yüzden Euler yolu yoktur; ayrıca kesişmeler olmadan çizilemez.
Euler yolları ve Königsberg köprüleri
Königsberg şehrinde dört kara parçasını birbirine bağlayan yedi köprü vardı ve insanlar her köprüden tam olarak bir kez geçen bir yürüyüş yapılıp yapılamayacağını merak ediyordu. 1736'da Leonhard Euler bunun mümkün olmadığını gösterdi ve graf teorisi böyle doğdu. Bir yürüyüş bir kara parçasından her geçtiğinde iki köprü kullanır; bu yüzden köprü sayısı yalnızca başlangıç ve bitiş noktalarında tek olabilir, oysa Königsberg'in dört kara parçasının hepsinde köprü sayısı tekti. Her kenarı bir kez kullanan bir yola bugün Euler yolu, başladığı yerde bitiyorsa Euler devresi denir. Carl Hierholzer 1873'te bu koşulun yeterli de olduğunu kanıtladı: tüm kenarlar tek parçadaysa ve en fazla iki derece tekse böyle bir yol vardır; onun kapalı turları birleştirme yöntemi bugün de bu yolu bulur.
Uzaklık, çap ve tümleyen
İki köşe arasındaki uzaklık, onları birleştiren bir yol üzerindeki en az kenar sayısıdır; çap ise graftaki en büyük uzaklıktır ve bağlantılı olmayan bir grafta sonsuzdur. Sosyal ağların çapı küçüktür; altı derece ayrılık fikrinin arkasında bu yatar. Bir grafın tümleyeni aynı köşelere sahiptir ve tam olarak birleşik olmayan çiftleri birleştirir. Bir graf ile tümleyeninden en az biri her zaman bağlantılıdır.
Keşfedin
Oyun alanı, üç renge boyanmış Petersen grafıyla açılır. Dereceler düğmesine tıklayıp el sıkışma lemmasını kontrol edin, tek uzunlukta bir döngü görmek için İki parçalı düğmesine tıklayın, sonra küpü yükleyip iki tarafın belirmesini izleyin. Evi yükleyin ve tek çizginin nereden başlaması gerektiğini görmek için Euler yolu düğmesine tıklayın. Kendi grafınızı çizin ve kenarları birer birer ekleyin: en kısa döngünün kısalmasını, çapın düşmesini ve bir K4'ün son kenarı eklendiğinde kromatik sayının artmasını izleyin.
Sık sorulan sorular
Yol, iz ve yürüyüş arasındaki fark nedir?
Yürüyüş, kenarlarla birleştirilmiş herhangi bir köşe dizisidir ve hem köşeleri hem kenarları tekrarlayabilir. İz, köşeleri tekrarlayabilir ama kenarları tekrarlayamaz; bu yüzden aslında bir iz olan Euler yolu bir köşeden birkaç kez geçebilir. Yol ise hiçbirini tekrarlamaz.
Dört renk teoremi nedir?
Kenarları kesişmeden kâğıda çizilebilen her grafın en fazla dört renkle boyanabileceğini söyler; dolayısıyla hiçbir harita dörtten fazla renge ihtiyaç duymaz. 1976'da Kenneth Appel ve Wolfgang Haken tarafından bir bilgisayarın yardımıyla kanıtlandı ve bu şekilde kanıtlanan ilk büyük teorem oldu.
Hamilton döngüsü nedir?
Her kenardan değil, her köşeden tam olarak bir kez geçen bir döngüdür. Euler sorusuna benzer, ama bunun için basit bir test bilinmiyor: bir grafta böyle bir döngü olup olmadığına karar vermek NP-tamdır. Petersen grafında bir Hamilton yolu vardır ama Hamilton döngüsü yoktur.
Graf teorisi nerelerde kullanılır?
Rota planlayıcıları yol graflarında arama yapar, arama motorları web sayfalarını bağlantılarına göre sıralar, derleyiciler işlemci yazmaçlarını paylaştırmak için grafları boyar, ders programları çakışmaları önlemek için bir çakışma grafını boyar, kimyagerler molekülleri graf olarak sayar; bilgisayar ağları, elektrik hatları ve arkadaşlık ağları da graf olarak incelenir.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Graf Teorisi Oyun Alanını açın