Euler yolları ve devreleri açıklaması
Bazı şekiller tek hamlede, kalemi kaldırmadan ve hiçbir çizgiden iki kez geçmeden çizilebilir, bazıları ise ne kadar uğraşsanız da çizilemez. Denemeye gerek yok: her köşedeki çizgileri sayın. En çok iki köşede tek sayıda çizgi varsa şekil çizilebilir ve hamlenin başlaması ile bitmesi gereken yerler o köşelerdir. Leonhard Euler bu kuralı 1736'da buldu ve onunla çizge kuramını başlattı.
Königsberg'in yedi köprüsü
Prusya kenti Königsberg, bugünkü Kaliningrad, Pregel nehrinin iki yakasında ve nehirdeki iki adada, Kneiphof ile Lomse'de kuruluydu. Yedi köprü dört parçayı birbirine bağlıyordu: Kneiphof'tan her kıyıya ikişer, iki ada arasında bir ve Lomse'den her kıyıya birer köprü. Kentliler bir yürüyüşün her köprüden tam bir kez geçip geçemeyeceğini merak ediyordu. Euler, 1735'te Sankt Petersburg akademisine sunduğu ve 1741'de basılan çalışmasında yanıtladı: geçemez. Belirleyici adımı, kentin parçaları ile aralarındaki köprüler dışında her şeyi bir yana bırakmaktı; graf da tam olarak bunu yapar: her kara parçası için bir düğüm, her köprü için bir kenar; aynı yerleri iki köprü bağlıyorsa iki kenar.
Derece kuralı
Bir düğümün derecesi, ona ulaşan kenarların sayısıdır. Bir düğümden geçen hamle bir kenardan girer, başka bir kenardan çıkar; yani o düğümün kenarlarını çiftler hâlinde kullanır. Yalnızca hamlenin ilk ve son düğümü eşsiz bir kenar tutabilir. Bu yüzden tek dereceli bir düğüm hamlenin başı ya da sonu olmalıdır. Kneiphof'un beş, öteki üç parçanın üçer köprüsü vardı: dört tek dereceli düğüm, ikisi fazla. Genel olarak bağlantılı bir grafın her derecesi çiftse bir Euler devresi, yani başladığı yerde biten bir hamle vardır; tam iki derece tekse birinden ötekine giden bir Euler yolu vardır. Tek dereceli düğüm sayısı hiçbir zaman bir ya da başka bir tek sayı olmaz: her kenar tüm derecelerin toplamına 2 ekler, dolayısıyla toplam çifttir. Euler bunu da fark etmişti; bugün el sıkışma önermesi deniyor.
Kural neden yeter
Euler, ikiden fazla tek dereceli düğümü olan bir şeklin çizilemeyeceğini gösterdi ve kanıtlamadan, bağlantılı her şeklin çizilebileceğini söyledi. Kanıtı, 1871'de genç yaşta ölen Alman matematikçi Carl Hierholzer getirdi; çalışması 1873'te yayımlandı. Varsa tek dereceli bir düğümden, yoksa herhangi bir yerden başlayın ve kullanılmamış kenarlar boyunca gidebildiğiniz kadar gidin. Öteki düğümlerin derecesi çift olduğundan ancak bitiş düğümünde tıkanabilirsiniz. Kenar kaldıysa bazıları şimdiye kadarki yolu değer, çünkü şekil bağlantılıdır. Böyle bir düğümden yine tıkanana kadar yürüyün; bu kez o düğüme dönerek tıkanırsınız ve ilmeği yola orada ekleyin. Hiç kenar kalmayana kadar yineleyin. Kanıt aynı zamanda en hızlı algoritmadır: her kenara sabit sayıda bakılır.
Fleury algoritması: köprülerinizi yakmayın
Bir hamle, çizilebilen bir şekilde bile başarısız olabilir. Tek bir kenarla bağlanmış iki üçgen alın ve birincinin bir köşesinden başlayın: birinci bitmeden ikinci üçgene geçerseniz bir daha geri dönemezsiniz. Bağlayan kenar bir köprüdür: kaldırılırsa şekil ikiye ayrılır. Fleury'nin 1883 tarihli algoritması tek bir kural verir: her düğümde, kalan kenarlar için köprü olmayan bir kenar seçin; başka kenar yoksa o ayrı. Bunu izleyen her zaman bitirir. Köprü sınaması zaman alır, bu yüzden Fleury algoritması Hierholzer'inkinden yavaştır, ama kalemle izlenebilen odur ve uygulamadaki ipucu onu kullanır.
Bir şekli onarmak
k tek dereceli düğümü olan bir şekil k/2 hamle gerektirir. Tek hamlede çizmek için tek dereceli düğümleri ikişer ikişer birleştiren kenarlar ekleyin: her yeni kenar iki tek dereceli düğümü çift yapar. k/2 − 1 kenar eklenince iki tek dereceli düğüm kalır ve bir yol çıkar; k/2 kenar eklenince hiç kalmaz ve bir devre çıkar. Königsberg'de dört parçanın herhangi ikisi arasına bir köprü daha olsaydı yürüyüş mümkün olurdu, iki köprü daha olsaydı tur da mümkün olurdu. Tarih buna benzer bir şey yaptı: iki köprü İkinci Dünya Savaşı'nda yitirildi, ikisi modern bir yolla değiştirildi ve bugün eski yerlerinde duran beş köprüden birer kez geçilebiliyor, bir adadan ötekine.
Yolları saymak
Noel Baba'nın evi, iki köşegeni ve çatısı olan bir kare, bulmacanın Alman çocuk sürümüdür: „Das ist das Haus vom Ni-ko-laus” sekiz hecedir, her çizgi için bir hece. Alttaki iki köşesi tek dereceli tek düğümlerdir ve her birinden tam 44 çizme yolu vardır, toplamda 88. Yönlü graflar için Euler devrelerinin sayısını veren bir formül vardır: de Bruijn, van Aardenne-Ehrenfest, Smith ve Tutte'un adlarını taşıyan BEST teoremi. Sıradan graflar için böyle bir formül bilinmiyor ve sayma genel olarak zor kabul ediliyor; bu yüzden uygulama küçük şekilleri her yolu deneyerek sayar ve şekli ikiye ayıracak adımları atlar.
Euler yolları nerede kullanılır
Bir kar küreme aracı, bir süpürge aracı ya da bir postacı her sokaktan bir kez geçip dönmek ister. Her kavşakta çift sayıda sokak varsa bir Euler devresi bunu sağlar; yoksa bazı sokaklardan iki kez geçmek gerekir ve en ucuzlarını seçmek, Meigu Guan'ın 1962'de ortaya attığı Çinli postacı problemidir. Bir kalemli çizici ya da lazer kesici, kalemi kaldırmadan olabildiğince çok çizgi çizerek zaman kazanır. Genom dizilemede milyonlarca kısa DNA parçası, her parçanın bir kenar olduğu bir de Bruijn grafında Euler yolu aranarak birleştirilir. Aynı kural, bir bulmaca kitabındaki hangi çizimleri denemeye değer olduğunu da söyler.
Siz deneyin
Euler Yolu Bulucu'yu açın ve on iki şeklin üzerinden kendiniz geçin: 1736'daki ve bugünkü Königsberg'den yıldızlara, iç içe karelere ve bir küpe kadar. Ya da paralel kenarlarla kendi şekillerinizi çizin. Tek dereceli düğümler dolu çizilir, her düğüm derecesini gösterir ve şeklin altındaki derece kuralı neyin mümkün olduğunu ve hangi kenarların şekli onaracağını söyler. Tıkanırsanız uygulama yanlış düğümden mi başladığınızı yoksa bir köprüden çok erken mi geçtiğinizi ve bunun hangi adımda olduğunu söyler. İpucu güvenli bir kenar verir; Çöz ise şekli Fleury algoritmasıyla köprü sınamasını göstererek ya da Hierholzer algoritmasıyla her eklemeyi göstererek çizer.
Sık sorulan sorular
Euler yolu ile Hamilton yolu aynı şey midir?
Hayır. Euler yolu her kenarı bir kez kullanır ve bir düğüme birçok kez uğrayabilir; Hamilton yolu her düğüme bir kez uğrar ve her kenarı kullanmak zorunda değildir. Bir grafın Euler yolu olup olmadığı tek dereceli düğümler sayılarak hemen anlaşılır, ama Hamilton yolları için hızlı bir sınama bilinmiyor ve birini bulmak bilgisayar biliminin klasik zor problemlerinden biridir.
İki düğüm birden fazla kenarla bağlıysa derece kuralı yine geçerli midir?
Evet. Her kenar iki ucunun da derecesine sayılır; aynı iki düğümü başka bir kenar bağlasa da bağlamasa da. Königsberg böyle bir çoklu graftır: Kneiphof'u her kıyıya ikişer köprü bağlar. Bir düğümden kendine giden kenar, yani ilmek, derecesine 2 ekler ve tek olup olmadığını hiç değiştirmez.
Tek yönlü sokaklarda durum nedir?
Yönlü grafta her kenarın bir yönü vardır ve kural, her düğüme giren kenarlarla çıkanları karşılaştırır. Her düğüme giren ve çıkan kenar sayısı eşitse ve kenarlar bir arada duruyorsa Euler devresi vardır; bir düğümün çıkanı girenden bir fazla, bir başkasınınki bir eksikse ve geri kalanların hepsi dengeliyse Euler yolu vardır. Yol o zaman birinciden ikinciye gider.
Tam bir tek dereceli düğümü olan bir şekil olabilir mi?
Hayır. Tüm düğümlerin dereceleri toplamı kenar sayısının iki katıdır, çünkü her kenarın iki ucu vardır. Bu toplam çifttir, dolayısıyla içindeki tek derecelerin sayısı da çift olmalıdır: 0, 2, 4 ve böyle sürer; asla 1 ya da 3 olmaz.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Euler Yolu Bulucu'yu açın