Hamilton yolları ve çevrimleri açıklandı
Halka biçiminde beş nokta çizin, her birini iki komşusuyla birleştirin; her noktadan bir kez geçerek turu tamamlayıp eve dönebilirsiniz: bir Hamilton çevrimi. Birkaç kenar ekleyin ya da birkaçını çıkarın, soru şaşırtıcı biçimde zorlaşır. Bir çizgenin böyle bir çevrimi olup olmadığı, hiçbir bilgisayarın her çizge için henüz hızlıca yanıtlayamadığı en bilinen problemlerden biridir.
Her düğüm bir kez
Çizge, kenarlar denen çizgilerle birleştirilmiş, düğümler denen noktalar kümesidir. Hamilton yolu kenarlar boyunca gider ve her düğümü tam bir kez ziyaret eder; Hamilton çevrimi ayrıca başladığı yere döner, bu yüzden düğüm sayısı kadar kenarı vardır. Hamilton çevrimi olan çizgeye Hamiltonyen denir. Önerilen bir rotayı denetlemek kolaydır: düğümleri sayın ve her adıma bakın. Böyle bir rotayı bulmak ya da hiç olmadığını kanıtlamak zor kısımdır, çünkü düğümlerin ziyaret edilebileceği sıraların sayısı n! gibi büyür: 20 düğümde bile 2,4 × 10¹⁸.
Hamilton'un Icosian oyunu
Kuaterniyonları bulan İrlandalı matematikçi William Rowan Hamilton, Icosian oyununu 1857'de tasarladı. Tahtası düzleme yassılaştırılmış bir dodekahedronu gösteriyordu; 20 köşesi ünsüzlerle işaretliydi ve asıl görev, 1'den 20'ye numaralı çivileri köşelere öyle yerleştirmekti ki ardışık sayılar, ayrıca 20 ile 1, kenarlarla birleşik olsun. Hamilton hakları 25 sterline Londralı oyuncak üreticisi John Jaques and Son'a sattı; oyun 1859'da çıktı ve az sattı. Bulmacanın 30 çözümü vardır; çevrim başlangıcı ve yönü ne olursa olsun bir kez sayıldığında. Sorunun kendisi yeni değildi: Thomas Kirkman, 1855'te Royal Society'ye gönderdiği bir yazıda hangi çokyüzlülerin bütün köşelerinden geçen bir çevrimi olduğunu sormuş ve olmayan birini göstermişti.
At turları
At turu, satrançtaki atı her kareye tam bir kez inecek şekilde oynatır: düğümleri kareler, kenarları at hamleleri olan çizgede bir Hamilton yolu. Kapalı tur, başlangıcından bir at hamlesi uzakta biter, yani bir Hamilton çevrimidir. Satranç oyuncuları böyle sorunları bin yıldan uzun süre önce ortaya atıyordu; Euler bunları 1759 tarihli bir yazıda inceledi. 1823'te H. C. von Warnsdorff her zaman devam hamlesi en az olan kareye gitmeyi önerdi; bu basit kural 8 × 8 tahtada çoğu zaman geri dönmeden bir turu tamamlar. At her zaman kare rengini değiştirir, bu yüzden kapalı tur açık ve koyu karelerden eşit sayıda ister; bu da tek sayıda karesi olan tahtaları dışlar. Allen Schwenk 1991'de hangi dikdörtgen tahtaların kapalı turu olduğunu tam olarak gösterdi; kare tahtalar arasında kenarı 6 ya da daha büyük çift sayı olan her tahtanın kapalı turu vardır. Alışıldık satranç tahtasında 13.267.364.410.532 kapalı tur vardır; bunları 1997'de Brendan McKay saydı.
Hamilton çevrimi olmayan çizgeler
Çevrim olmadığının en hızlı kanıtları sayma savlarıdır. Düğümler, her kenar farklı renkleri birleştirecek biçimde iki renge boyanabiliyorsa, bir çevrim renkleri sırayla değiştirir ve her renkten eşit sayıda düğüm ister; 5 × 5 ızgarada bir renkten 13, öbüründen 12 vardır, bu yüzden Hamilton çevrimi yoktur. Çıkarılması çizgeyi bölen bir kesme düğümünden iki kez geçilmesi gerekirdi; derecesi 1 olan bir düğümden ise hiç geçilemez. Bazı çizgeler bütün bu savlardan kaçar. Julius Petersen'in 1898'de yayımladığı Petersen çizgesinde derecesi 3 olan 10 düğüm vardır ve Hamilton çevrimi yoktur; yine de herhangi bir düğüm silindiğinde Hamilton çevrimi olan bir çizge kalır. Bu özellikteki en küçük hipohamiltonyen çizgedir. 1862'de Icosian oyunu üzerine yazan Alexander Stewart Herschel'in adını taşıyan Herschel çizgesinde 11 düğüm ve 18 kenar vardır; dokuz dörtgen yüzlü bir çokyüzlünün çizgesidir. Daha az köşesi olan hiçbir çokyüzlüde Hamilton çevrimi eksik değildir. 1884'te Peter Guthrie Tait, her köşesinde üç ayrıt bulunan her çokyüzlünün Hamilton çevrimi olduğunu öne sürdü; W. T. Tutte 1946'da 46 düğümlü bir karşı örnek buldu.
Çevrimi güvence altına alan koşullar
Bir çizgenin çok kenarı varsa Hamilton çevrimi kesindir. Gabriel Dirac 1952'de, n ≥ 3 düğümlü ve her düğümünün derecesi en az n/2 olan bir çizgenin Hamilton çevrimi olduğunu kanıtladı; Øystein Ore 1960'ta koşulu zayıflattı: birleşik olmayan iki düğümün dereceleri toplamının her zaman en az n olması yeter. İki koşul da yalnızca tek yönde işler. 100 düğümlü yalın bir halkada derece her yerde 2'dir, 50'nin çok altında, ama yine de bir Hamilton çevrimidir. Genel tablo şudur: yeterli koşullar vardır, başarısızlık nedenleri vardır ve ikisinin arasında yalnızca bir aramanın karara bağlayabileceği geniş bir çizge alanı uzanır.
Neden hızlı bir sınama bilinmiyor
Bir çizgenin Hamilton çevrimi olup olmadığına karar vermek NP-tamdır; Richard Karp'ın 1972 tarihli listesindeki 21 problemden biriydi. Bunu her çizge için hızlıca çözen bir yöntem binlerce başka problemi de hızlıca çözer ve P ile NP sorusunu karara bağlardı. Her kenarı bir kez kullanan Euler yollarıyla karşıtlık çarpıcıdır: Euler 1736'da tek dereceli düğümleri saymanın o soruyu hemen karara bağladığını gösterdi. Hamilton çevrimleri için en iyi kesin yöntemler hâlâ üstel zaman alır. Düğümlerin bütün altkümeleri üzerinde dinamik programlama, 1962'de Richard Bellman ile Michael Held ve Richard Karp tarafından bulundu ve yaklaşık n² × 2ⁿ adım gerektirir; Andreas Björklund'un 2010 tarihli rastgeleleştirilmiş yöntemi ise yaklaşık 1,657ⁿ. Uygulamada iyi budamalı geri izleme birkaç düzine düğümlü çizgelerin üstesinden gelir; en kısa Hamilton çevrimini arayan gezgin satıcı problemi de aynı sorunun ağırlıklı sürümüdür.
Gray kodları ve hiperküp
0'dan 7'ye kadar sayıları 3 bitlik kodlar olarak yazın ve tam olarak tek bitte ayrılan iki kodu birleştirin: sonuç bir küpün çizgesidir. İçinden geçen bir Hamilton çevrimi, örneğin 000, 001, 011, 010, 110, 111, 101, 100, sekiz kodun hepsini her biri bir öncekinden tek bitte ayrılacak biçimde sıralar. Böyle bir listeye Gray kodu denir; adını, 1947'de verilen bir patentte onu betimleyen Bell Labs'tan Frank Gray'den alır. Her hiperküpte bir tane vardır: kodları bir bit eksikle yazın, sonra aynı listeyi tersten yazın ve ilk yarının önüne 0, ikincinin önüne 1 koyun. Döner kodlayıcılar Gray kodlarını kullanır; böylece iki konum arasında alınan bir okuma hiçbir zaman bir adımdan fazla yanlış olmaz. Küpte 6, 4 bitlik hiperküpte 1.344 Hamilton çevrimi vardır.
Kendiniz deneyin
Hamilton'un bulmacasını kendiniz denemek için Hamilton yolu gezginini açın; kesik halkalar nereye gidebileceğinizi gösterir. Ya da Arama kipine geçip geri izlemenin çalışmasını izleyin: yol büyür, kırmızı kesikler geri döndüğü yerleri işaretler ve çubuklar yol uzunluğuna göre düğümleri sayar. Çıkmaz denetimini, bağlantı denetimini ve Warnsdorff sıralamasını açıp kapatın, her birinin kaç düğüm gerektirdiğini karşılaştırın, küçük bir çizgenin bütün çevrimlerini sayın ya da kendi çizgenizi çizip hızlı sınamalardan hangilerinin geçerli olduğunu görün.
Sık sorulan sorular
Euler devresi olan bir çizge aynı zamanda Hamiltonyen midir, ya da tersi?
Hiçbiri öbüründen çıkmaz. Bir düğümü paylaşan iki üçgenden oluşan papyonun Euler devresi vardır, çünkü her derece çifttir; ama Hamilton çevrimi yoktur, çünkü ortak düğümden iki kez geçilmesi gerekirdi. Tam çizge K₄ çizgesinin Hamilton çevrimleri vardır, ama dört düğümün de derecesi 3'tür, bu yüzden Euler devresi yoktur.
Bilgisayar her sırayı tek tek deneyemez mi?
Yalnızca küçük çizgelerde. n düğümün n! sırası vardır; 20 için yaklaşık 2,4 × 10¹⁸. Geri izleme çok daha iyisini yapar, çünkü yalnızca kenarları izler ve tıkanır tıkanmaz kısmi yoldan vazgeçer: 20 düğümlü dodekahedronun 30 çevriminin hepsini yaklaşık 1.400 adımda bulur. Yine de bazı çizgelerde kısmi yolların sayısı üstel büyür ve bunu her çizge için önleyen bir yöntem bilinmiyor.
Hamilton yolu problemi çevrim probleminden daha kolay mı?
Hayır, ikisi de NP-tamdır. Her biri öbürüne dönüştürülebilir: eski düğümlerin hepsiyle birleşik yeni bir düğüm ekleyin; eski çizgenin Hamilton yolu olması, tam olarak yeni çizgenin Hamilton çevrimi olmasıyla aynı anlama gelir. Ters yönde ise bir çevrim problemi, bir düğümün aynı komşulara sahip bir kopyası eklenip düğüme bir yeni uç düğüm, kopyasına da bir başkası bağlanarak yol problemine dönüşür.
5 × 5 tahtada at turu neden köşe renginde başlamak zorundadır?
25 karenin 13'ü köşelerin rengindedir, 12'si öbür renktedir ve at her hamlede renk değiştirir. 25 kare üzerinden giden bir tur renkleri sırayla değiştirir, bu yüzden kare sayısı fazla olan renkte başlar ve biter. Uygulama 5 × 5 tahtanın 1.728 açık turunun hepsini bulur; bir tur ile tersi bir sayılırsa 864 eder ve her biri köşe renginde bir karede başlayıp biter.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Hamilton yolu gezginini aç