| Arama | Düğüm | Sonuç |
|---|---|---|
| Düz geri izleme | – | – |
| Warnsdorff sıralaması | – | – |
| Çıkmaz ve bağlantı denetimi | – | – |
| Üçü birden | – | – |
Hamilton yolu gezgini
1857'de William Rowan Hamilton bir bulmaca tasarladı: bir dodekahedronun ayrıtları boyunca yürüyüp 20 köşesinin her birinden tam bir kez geçmek ve başladığınız yerde bitirmek. Böyle bir rotaya bugün Hamilton çevrimi deniyor. Denetlemesi kolay, genel olarak bulması zordur. Birini kendiniz Hamilton'un dodekahedronunda, bir satranç tahtasında ya da çizdiğiniz bir çizgede çizin; ya da geri izlemeli bir aramanın peşine düşüşünü izleyin, girdiği çıkmazları sayın ve birkaç basit denetimin aramayı ne kadar kısalttığını görün. Bir çizge ve bir hedef seçin: başladığı yere dönen bir çevrim ya da bir yol. Çiz: başlamak için bir düğüme, sonra her seferinde bir komşuya tıklayın; kesik halkalar nereye gidebileceğinizi gösterir. Son düğüme tıklamak, Geri ya da Geri al bir adım geri alır; İpucu ise hâlâ sona erdirilebilecek bir sonraki adımı söyler. Arama: Çalıştır ya da Adım ile geri izlemeli bir arama yürür; arama tıkanana kadar düğüm ekler, sonra geri döner. Kırmızı kesikler geri dönüşleri gösterir, çubuklar ise yol uzunluğuna göre düğümleri sayar. Başlamadan önce bir düğüme tıklamak aramanın nereden başlayacağını seçer. Kutular budamayı açıp kapatır, Karşılaştır aynı aramayı budamalı ve budamasız çalıştırır, Hepsini say ise küçük bir çizgenin her çevrimini ya da yolunu sayar. Düzenle: düğüm eklemek için tıklayın, iki düğümü birleştirmek ya da ayırmak için ikisine tıklayın, birini taşımak için sürükleyin; Sil seçili düğümü kaldırır.
Nasıl çalışır
- Bir çizge seçin: örneğin Hamilton'un dodekahedronu, Petersen çizgesi ya da bir at turu; ya da Düzenle kipinde kendinizinkini çizin ve hedef olarak çevrim veya yol seçin.
- Çiz kipinde başlamak için bir düğüme, sonra sırayla komşulara tıklayın. Geri ve Geri al bir adım geri alır, İpucu ise hâlâ sona erdirilebilecek bir sonraki adımı gösterir.
- Arama kipinde geri izlemenin bir rota arayışını izlemek için Çalıştır ya da Adım düğmesine basın, budamayı açıp kapatın ve her sürümün kaç düğüm gerektirdiğini görmek için Karşılaştır düğmesine basın.
Hamilton'a karşı Euler
Euler yolu her kenarı bir kez kullanır; Hamilton yolu her düğümü bir kez ziyaret eder. Kulağa benzer gelir ama çok farklı davranırlar. Bağlantılı bir çizgenin Euler yolu olup olmadığı, Euler'in 1736'da gösterdiği gibi tek dereceli düğümler sayılarak belirlenir: hiç yoksa ya da iki taneyse vardır. Hamilton yolları için böyle bir kural bilinmiyor. Bir çizgenin Hamilton çevrimi olup olmadığına karar vermek NP-tamdır; Richard Karp'ın 1972 tarihli listesindeki 21 problemden biridir, bu yüzden bunun için hızlı bir yöntem binlerce başka zor problem için de hızlı yöntemler verirdi. Var olan şey, bazı çizgeleri belirleyen koşullardır. Dirac'ın 1952 tarihli teoremi, her düğümün derecesi en az n/2 olduğunda bir Hamilton çevrimi güvence altına alır; Ore'un 1960 tarihli teoremi ise birleşik olmayan iki düğümün dereceleri toplamı her zaman en az n olduğunda. Derecesi 1 olan bir düğüm, bir kesme düğümü ya da farklı büyüklükte iki renk sınıfı çevrimi dışlar.
Arama nasıl çalışır
Geri izleme yolu her seferinde bir düğüm ekleyerek kurar; tıkandığında son adımı geri alır ve sonraki komşuyu dener. Bir Hamilton çevrimi varsa onu her zaman bulur, ama kısmi yolların sayısı üstel büyüyebilir. Hamilton çevrimi olmayan 5 × 5 ızgarada düz geri izleme, emin olmadan önce 153.745 düğüm inceler. İki denetim umutsuz yolları erken durdurur: serbest komşusu ikiden az olan ziyaret edilmemiş bir düğüm artık bir çevrime sığdırılamaz; ziyaret edilmemiş düğümler ayrı parçalara ayrıldığında ise tek bir yol hepsini kapsayamaz. İkisiyle birlikte aynı kanıt 1.761 düğüm alır. 1823 tarihli Warnsdorff kuralı, önce en az devam hamlesi olan komşuyu dener ve 8 × 8 tahtada bir köşeden başlayan at turunu tek bir çıkmaza girmeden 64 hamlede bulur.
Sık sorulan sorular
Hamilton yolu ile Hamilton çevrimi arasındaki fark nedir?
Hamilton yolu bir çizgenin her düğümünü tam bir kez ziyaret eder. Hamilton çevrimi aynısını yapar ve sonra bir kenar daha kullanarak başladığı yere döner; bu yüzden düğümlerinden herhangi birinde başlayabilir. Hamilton çevrimi olan her çizgenin Hamilton yolu da vardır (çevrimin bir kenarını çıkarmanız yeter), ama tersi doğru değildir: Petersen çizgesinde Hamilton yolları vardır, Hamilton çevrimi yoktur.
Dodekahedronun Hamilton çevrimi var mı?
Evet, 30 tane; her çevrim başlangıcı ve yönü ne olursa olsun bir kez sayıldığında. Hamilton bunu 1857'de Icosian oyununa dönüştürdü: yassılaştırılmış bir dodekahedronun ünsüzlerle işaretlenmiş 20 köşesini taşıyan bir tahta. Haklarını 25 sterline Londralı oyuncak üreticisi John Jaques and Son'a sattı. Hepsini say, 30 çevrimi yaklaşık 1.400 düğümde bulur.
5 × 5 ızgaranın neden Hamilton çevrimi yoktur?
25 noktayı satranç tahtası gibi boyayın: 13'ü bir rengi, 12'si öbürünü alır ve her adım öbür renge gider. Bir çevrim tur boyunca renkleri sırayla değiştirir, bu yüzden her renkten eşit sayıda ister; 13 ile 12 bunu veremez. Aynı akıl yürütme tek sayıda noktası olan her ızgara için, 5 × 5 ya da 7 × 7 tahtadaki bir at için (at her zaman kare rengini değiştirir) ve iki sınıfı 6 ile 5 düğümlü olan Herschel çizgesi için geçerlidir. Hamilton yolu yine de olabilir: çoğunlukta olan renkte başlar ve biter.
Warnsdorff kuralı bir at turunu nasıl bulur?
H. C. von Warnsdorff 1823'te atı her zaman devam hamlesi en az olacak kareye oynatmayı önerdi. Kenarlara ve köşelere yakın, kolayca kesilip kalan kareler böylece erken ziyaret edilir, at hâlâ onlara girebilirken. Kural bir başparmak kuralıdır, güvence değil; eşitlikler bir biçimde çözülmelidir. Yine de 8 × 8 tahtada çoğu zaman geri dönmeden bir turu tamamlar. Bu uygulamadaki gibi geri izlemeyle birleştiğinde 5 × 5'ten başlayarak açık turları, 6 × 6 ve 8 × 8 tahtalarda ise kapalı turları bulur.
Tam bir çizgenin kaç Hamilton çevrimi vardır?
n ≥ 3 için (n − 1)!/2. Başlangıç düğümünü sabitleyin; kalan n − 1 düğüm herhangi bir sırayla gelebilir ve her çevrim iki kez, her yön için bir kez sayılır. K₆ çizgesinde 5!/2 = 60, K₁₀ çizgesinde 181.440 çevrim vardır. Bunlar bir gezgin satıcının arasından seçmesi gereken turlardır; hepsini denemenin bu kadar çabuk olanaksızlaşmasının nedeni de budur.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git