A matematika , keretében gráfelmélet , a Hamilton út egy irányított vagy irányítatlan gráf egy olyan út, amely átmegy az összes csúcsot csak egyszer. A hamiltoni ciklus egy hamiltoni út, amely egy ciklus . A hamiltoni gráf egy olyan gráf , amelynek Hamilton-ciklusa van.
Egy hamiltoni gráfot nem szabad összetéveszteni egy euleri gráffal , ahol az összes élen egyszer és egyszer megyünk keresztül: egy hamiltoni ciklusban nagyon jól elhanyagolhatunk bizonyos éleken való áthaladást. A gráf lehet euleri, hamiltoni, mindkettő, vagy egyik sem: a pillangó gráf egy példa egy euleri gráfra, de nem hamilton.
Egy hamiltoni gráf tartalmazhat több hamiltoni ciklust: így Chvátal grafikonjának 12 csúcsa, 24 éle és 370 különálló hamiltoni ciklusa van.
Mi már bizonyította egy bizonyos számú matematikai feltételeknek, amelyek, ha azokat elégedett, lehetővé teszik, hogy egy gráf Hamilton, valamint a feltételeket, amelyek, ha nem elégedett, biztosítani, hogy ez nem az.. Számítógépekre is bízhatjuk a Hamilton-ciklusok keresését apránként optimalizált algoritmusok segítségével . Mindkét esetben a hamiltoni út algoritmikus problémája NP-teljes , vagyis általános esetben ésszerű időn belül nehéz megoldani. A hamiltoni grafikonok mind a matematika, mind az informatika területén aktív kutatási területet jelentenek.
A IX . Században az indiai költő, Rudrata volt az első, aki sakktáblán, de lovas mellett találta meg a problémás kerékpáros utakat / Hamilton-ösvényeket (vagyis minden dobozban böngészhetett, egyszer csak egy lovas mozdulatait használva) . Ez a versenyző problémája .
A hamiltoni grafikonokat William Rowan Hamiltonról nevezték el, aki a XIX . Század közepén az írországi csillagász volt . Feltalálta az általa ikosz játéknak nevezett játékot , amely abból áll, hogy a dodekaéder széleinek grafikonján talál egy hamiltoni ciklust . Hamilton megoldotta ezt a problémát egy új típusú számítások felhasználásával, amelyeket ő hívott Icosian calculus (in) -nek , és ez manapság egy nem kommutatív csoportba tartozó számításokkal írná le . Ez a megoldás sajnos nem általánosít tetszőleges gráfra.
Bár ezek a grafikonok Hamiltonról kapták a nevüket, a polyhedrában található Hamilton-ciklusokat Thomas Kirkman már egy évvel korábban tanulmányozta .
Az alábbi meghatározások irányítatlan vagy irányított grafikonokra vonatkoznak. A szigorúság érdekében ívekről, utakról és áramkörökről kell beszélnünk irányított gráfok esetén, élekről, láncokról és ciklusokról pedig irányítatlan gráfok esetén.
Nem hamiltoni gráf
Fél-hamiltoni grafikon
Hamilton-grafikon
Az Eulerian-gráfok esetében egyszerű és szükséges feltételünk van annak meghatározására, hogy a gráf Eulerian-e (Euler-tétel). Sajnos nem találtunk megfelelőt a hamiltoni gráfokra.
Ennek ellenére rendelkezünk bizonyos számú, egyre általánosabb kritériummal, amelyek lehetővé teszik annak biztosítását, hogy egy ilyen és egy ilyen gráf Hamilton-féle legyen. Gabriel Andrew Dirac volt az, aki 1952-ben elindította a labdát, azzal az intuitív elképzeléssel, hogy a grafikon szükségszerűen Hamilton-féle, ha „elég éle van”. A csúcsok mértéke szerint az eddigi legjobb jellemzés az 1976-os Bondy és Chvátal tétel.
Más tételek, mint például Ghouila-Houiri, verziók az irányított gráfok esetében.
Ez a tétel Gabriel Andrew Dirac-nek köszönhető, 1952-ben. A következőképpen fogalmaznak:
Tétel - Egy egyszerű gráf a csúcsok ( ), ahol minden csúcs legalább foka van Hamilton.
DemonstrációLegyen egy olyan gráf, amelynek csúcsaival az egyes csúcsok legalább fokúak . Először észrevesszük, hogy kapcsolódik . Sőt, vegye figyelembe már, hogy feltételezés szerint egy összekapcsolt komponenst magasabb rendűnek engedélyez, mint (egy tetszőlegesen választott csúcs és szomszédos csúcsai). Tegyük fel, hogy ez nincs csatlakoztatva. Kevesebb, mint (a két komponens diszjunkt, a két komponens két rendjének összege és egyenlő ) kisebb összefüggésű összetevőt ismer be . A csúcsok mértéke ekkor a maximális , ami ellentmond a kezdeti hipotéziseknek.
Tekintsük a leghosszabb , különálló csúcsú láncot , vagy az egyik leghosszabb láncot, ha egynél több van.
Ha és szomszédok, építünk a ciklus .
Ha és nem szomszédok, mert a lánc nem hosszabbítható meg, az összes csúcs szomszédos vége szintén tartozik a csúcsai a lánc . Ezért vannak legalább szomszédos csúcsok, amelyek a . Hasonlóképpen vannak legalább szomszédos csúcsok , amelyek a lánc csúcsaihoz tartoznak . amely legfeljebb csúcsai, a elve fiókok lehetővé teszi, hogy következtetni, hogy van között , és úgy, hogy a szomszédja , és a szomszédja (ábra) . Intuitív szempontból nincs elég hely arra, hogy a szomszédok távol maradhassanak a szomszédoktól .
Felépítjük a ciklust (az ábrán piros színnel) .
Minden esetben Hamilton-i.
Tegyük fel, hogy ez nem hamiltoni. Tehát nem fedi le a . Hagyja, hogy a (nem üres) csúcsok halmaza ne jelenjen meg . Amint van csatlakoztatva, létezik az , és az ilyen, hogy egy éle a grafikon. Tudjuk majd hozzá , hogy építeni egy lánc hosszabb, mint (illusztráció) , ami ellentmond a hipotézist, hogy volt a maximális hossz.
Ez a tétel az 1960-as Øystein ércnek köszönhető . A következőképpen fogalmaznak:
Tétel - Egy egyszerű gráf csúcsokkal ( ) oly módon, hogy a nem szomszédos csúcsok bármely párjának fokainak összege legalább egyenlő Hamilton-nal.
Dirac-tétel az Ore-tétel speciális esete: valóban, ha minden csúcs legalább fokozatú , akkor bármely csúcspár fokainak összege, szomszédos vagy nem szomszédos, legalább .
DemonstrációVegye figyelembe a tulajdonságot: „a nem szomszédos csúcsok párjának fokozatainak összege legalább n ”.
Ore tételének bizonyítása megegyezik azzal, hogy megmutatjuk, hogy bármely nem hamiltoni gráf nem elégíti ki a tulajdonságot .
Legyen egy nem hamiltoni gráf csúcsokkal ( ). Ne feledje, hogy élek hozzáadásával szükségszerűen bármilyen Hamilton-gráfot készítünk, mivel szélsőséges esetben a teljes gráfhoz jutunk, amely Hamilton-féle. Mi döntjük el, hogy építsenek egy grafikon származó hozzáadásával élek kialakítása nélkül Hamilton kör, amíg ez már nem lehetséges.
Legyen és legyen bármely két nem szomszédos csúcsa . Mivel a hozzáadása , hogy képezné egy Hamilton kör, a másik élei, hogy alkotnak Hamilton láncot. Jelölje ezt a csúcsláncot a -val .
Legyen olyan egész szám, hogy . Érdekelnek a lehetséges élek és . tartalmazhatnak legfeljebb csak az egyik a két szélén, mert különben lehet építeni a Hamilton-kör a (ábra) .
A végélek teljes száma, vagy ennélfogva legfeljebb megegyezik a választások számával , vagyis . Más szóval, . ezért nem tiszteli a vagyont .
Mentünk , hogy hozzáadásával élek: fokát csúcsainak tehát kisebb vagy egyenlő a mértéke csúcsainak . ezért sem tiszteli .
Több tételsel tartozunk Pósa Lajosnak (en) a Hamilton-ciklusokon. Különösen idézhetünk egy 1962-es tételt, amely a gyengén összekapcsolt csúcsokra vonatkozik:
Tétel - Egyszerű gráf csúcsokkal ( ) oly módon, hogy:
a Hamiltonian.
Vegye figyelembe, hogy a 2. feltétel akkor szerepel az 1. feltételben, ha páros, és ezért csak akkor érdekes, ha páratlan.
Alkalmazási példa : a szemközti grafikonnak 6 csúcsa van. Ő hamiltoni: a csúcsokat úgy rendeztük meg, hogy kiemeljük a hamiltoni ciklust, ez a piros külső ciklus .
Ore tételéből ihletve John Adrian Bondy és Václav Chvátal 1976-ban találtak egy módszert annak meghatározására, hogy egy gráf Hamilton-féle: amíg vannak csúcsok, és nem szomszédosak, addig hozzáadjuk a grafikon élét . Amikor nem tudunk többet hozzáadni, megszereztük azt, amit a grafikon bezárásának hívunk . Ezután a következő tételt alkalmazzuk:
Tétel - A gráf akkor és csak akkor hamiltoni, ha lezárása hamiltoni.
Különösen, ha egy gráf bezárása a teljes gráf , amely Hamilton-féle, akkor biztosak vagyunk abban, hogy a kiinduló gráf Hamilton-féle.
Kezdő grafikon | Középső szakasz | A kezdő grafikon bezárása |
---|---|---|
Alkalmazási példa : vegye figyelembe a ház grafikonját a szemközti ábrán. 5 csúcsot tartalmaz.
Ennek megbizonyosodása érdekében először vörös színű éleket adunk a fok és a fok csúcsai közé . Ezután zöld színű éleket adunk a fok csúcsa és az éppen fokokra változott csúcsok közé . Megkapjuk a teljes gráfot , ami Hamilton-féle, ami azt bizonyítja, hogy a kezdő gráf is az volt.
Alain Ghouila-Houri 1960 -ban kimondta a következő tételt, amely megegyezik Dirac irányított grafikonok tételével:
Tétel - Egy nagymértékben kapcsolódó egyszerű irányított gráf a csúcsok, ahol minden csúcs legalább fokú belépő és mértéke elhagyó van Hamilton.
Az irányított gráfok esetében két tétel felel meg Ore tételének.
Douglas R. Woodall 1972-ben a következő tételt mondta:
Tétel - A digráf könnyű a csúcsokat úgy, hogy bármely két és csúcsok, vagy van egy ív az egyik jelentése Hamilton.
Henry Meyniel 1973-ban kijelentette a következő kapcsolódó tételt:
Tétel - Egy erősen összefüggő egyszerű irányított gráf a csúcsok úgy, hogy az összeg a fok bármely pár nem szomszédos csúcsok legalább van Hamilton.
Bizonyos esetekben azt is tudjuk, hogyan kell bebizonyítani, hogy a grafikon nem hamiltoni. Így a Grindberg (en) tétel egy olyan karakterisztikát ad, amelyet minden Hamilton-féle síkgráf tiszteletben tart . Ha ezt a feltételt egy síkdiagramon nem tartják be, akkor tudjuk, hogy ez nem hamiltoni.
E sok részeredmény ellenére sok esetben nincs hatékony matematikai eszközünk annak megállapítására, hogy egy adott gráf Hamilton-féle-e vagy sem. Így egyik előző tétel sem ad olyan kritériumot, amely lehetővé tenné számunkra, hogy automatikusan megállapítsuk, hogy az ellentétes ábrán látható gráf Hamilton-féle, bármely csúcspár fokainak összege mindig egyenlő , ami kisebb, mint a csúcsok száma .
Az előző eredmények mindegyike a csúcsok fokaival kapcsolatos szempontokra összpontosít. Egy másik kutatási vonal annak kiderítése, hogy a grafikonok bizonyos kategóriái hamiltoni-e vagy sem:
A hamiltoni pálya probléma az a döntési probléma, amely egy grafikon alapján abból áll, hogy eldönti, elfogad-e egy hamiltoni utat. Ez a probléma NP-teljes, vagyis tudjuk, hogyan ellenőrizhetünk egy lehetséges megoldást polinomiális időben a csúcsok számának függvényében , de hogy ez a probléma legalább olyan nehéz, mint más NP-teljes problémák, ami erős jelzés hogy valószínűleg általában nem leszünk képesek ezt a megoldást polinomiális időben megtalálni. A kapcsolódó probléma annak tesztelése, hogy létezik-e hamiltoni út.
A két változat - irányított gráf és irányítatlan gráf - a Hamilton-kör probléma része Karp a 21 problémát és NP-teljes.
Az utazó eladó problémája egy Hamilton-ciklus keresése egy teljes gráfban, amelynek élei súlyozottak , egy korlátozás hozzáadásával: ennek a ciklusnak minimálisnak kell lennie.
A megoldások keresését általában egy számítógépre bízzák, amely például az összes láncot tesztelheti, amíg meg nem talál egy Hamilton-ciklust (nagyon naiv algoritmus esetén). Ez a technika sem igazán kielégítő, mert a számítások legrosszabb esetben is nagyon hosszúak lehetnek. Ráadásul, miután megtaláltuk ezeket a láncokat, nem értjük jobban, hogy mi alkot Hamilton-gráfot, vagy sem. Ez a módszer mindazonáltal lehetővé teszi a gyakorlati problémák megoldását.
A Hamilton-féle lánc- és ciklusproblémák hagyományos számítógépekkel történő megoldásának nehézségei miatt nem konvencionális számítási modelleket is vizsgáltak. Például Leonard Adleman kimutatta, hogy a Hamilton-út problémája megoldható egy DNS-számítógép segítségével .
Egyszerűen elmehetünk a Hamilton-lánc megtalálásának problémájáról a Hamilton-ciklus megtalálására és fordítva.
Egyrészt ahelyett, hogy Hamilton-láncot keresnénk egy gráfban , létrehozhatunk egy gráfot abból, hogy hozzáadunk egy új csúcsot, amelyhez kapcsolódunk az összes létező csúcshoz , majd megkeressük a Hamilton-ciklust .
Másrészt ahelyett, hogy Hamilton-ciklust keresnénk a gráfban , kiválaszthatjuk az egyik csúcsát , majd az egyes élekhez, amelyek összekötik a szomszéddal , készítsen egy gráfot abból , hogy ezt az élt egy új párral cseréli 1 fokú csúcsok, az egyik kapcsolódik a másikhoz , és végül egy Hamilton-láncot keresünk .
Szóval mi tudunk :
A legrosszabb Hamilton-féle lánckeresési problémamegoldó algoritmus, amelyre gondolhat, az, ha felveszi az egyik csúcsot, majd figyelembe veszi a fennmaradó csúcsok bármelyik élét stb. Ez lehetővé teszi a láncok tesztelését: a növekmény nagyon gyors növekedésének tényezője egy kombinatorikus robbanásnak lehetünk tanúi, és a keresés bizonyos hosszúságú csúcsoktól nagyon hosszú lehet .
Egy ilyen kimerítő keresési algoritmus, amely kihasználja a számítógép számítási teljesítményét, többféleképpen optimalizálható.
Így Frank Rubin egy olyan keresési módszert vet fel, ahol a grafikon széleit három csoportba soroljuk: azoknak, amelyeknek a láncban kell lenniük, azoknak, amelyek nem lehetnek a láncban, és azoknak, amelyeket nem ismerünk. A keresés előrehaladtával a döntési szabályok összessége osztályozza azokat az éleket, amelyekről még nem ismert, és meghatározza, hogy a keresést folytatni kell-e vagy le kell állnia. Az algoritmus felosztja a grafikont külön feldolgozható komponensekre.
A dinamikus programozás esete, amelyet Bellman, Held és Karpnak köszönhetünk, fel lehet használni a probléma O ( n 2 2 n ) sorrendben történő megoldására . Ebben a módszerben meghatározzuk a csúcsok minden részhalmazára és minden egyes csúcsára vonatkozóan , hogy létezik-e olyan lánc, amely pontosan átfogja a csúcsokat és azokra végződik . Minden választás és a lánc létezik akkor, ha van egy szomszéd csúcsa , hogy a lánc létezik , amelyek ellenőrizhetők az adatai már számítható a programot.
Andreas Björklund egy másik megközelítést alkalmazott az inklúzió-kizárás elvének felhasználásával , hogy a Hamilton-ciklusok számlálásának problémáját az átfedő ciklusok számolására csökkentse, ami a mátrixok bizonyos determinánsainak kiszámításával megoldható. Ezzel a módszerrel megmutatta, hogyan lehet egy tetszőleges csúcsgráfban megoldani a Hamilton-ciklus problémáját Monte-Carlo módszerrel , O rendű időkorlátban (1,657 n ); abban az esetben, páros gráfban ez az algoritmus lehet javítani, hogy válaszoljon időn belül O-rendű (1,414 n ).
A maximális három fokozatú grafikonok esetén a visszakövetéssel körültekintően végzett keresés során egy Hamilton-ciklus (ha van ilyen) megtalálható egy O idő alatt (1,251 n ).
Leonard Adleman megtervezte és a laboratóriumban sikeresen tesztelte a probléma megoldásának módszerét a DNS-ből kiindulva, ezzel utat nyitva egy DNS-számítógépes kutatás számára .
Az ötlet az, hogy a grafikon íveit DNS-szekvenciákkal jelenítsük meg, amelyek lineárisan összeállíthatók, ha közös végük van. Az ezen szekvenciák által képzett polimer tehát egy útnak felel meg.
Az Adleman által javasolt algoritmus a következő:
Ennek a módszernek az az előnye, hogy összehasonlítjuk a hagyományos számítógépes felbontás módszereivel, hogy időben sokkal olcsóbb. Ez az algoritmus kihasználja a kémiai reakciók belső párhuzamosságát, és a problémát számos lineáris kémiai reakció lépésben lehet megoldani a grafikon csúcsainak számától függően.
Ez az eredmény fontos az elméleti számítástechnikában: egy NP-teljes probléma polinomiális időben történő megoldásának módszeréről szól, ezért polinomiális időben módszert nyújt bármely NP-teljes probléma megoldására, amire a mai számítógépek nem képesek ez.
Ezt az alacsony időköltséget azonban más módon fizetik meg: a szükséges DNS mennyisége a probléma nagyságától függ, amely visszahat többek között a szükséges gép tömegére is. Egy kutató kiszámította, hogy egy gép, amely képes megoldani a problémát egy 200 csúcsú gráfnál, 3 × 10 25 kg lehet . Az algoritmus azt is feltételezi, hogy tényleges számú különféle típusú DNS-molekula van, amely részt vesz a reakcióban. Ezek a problémák, valamint a használható DNS-gépek előállításához kapcsolódó egyéb problémák jelenleg nem tették lehetővé a DNS-számítógépek valódi fejlesztését az ilyen típusú problémák konkrét megoldására.
A Hamilton-féle ciklus vagy áramkörproblémák orientált vagy irányítatlan grafikonokban a Karp 21 NP-teljes problémája közül a két probléma . Az irányítatlan gráfban szereplő probléma összpontosul az irányított gráf problémájával. Az irányított grafikon esete a csúcsok általi lefedettség problémájára vezethető vissza .
A Hamilton-ciklus megtalálásának problémája az FNP (en) osztályban van .
A Hamilton-ciklus és az áramkör problémái még NP-ként is teljesek:
Ha azonban összegyűjtjük ezeket a feltételeket, akkor továbbra is nyitva marad az a probléma, hogy megtudjuk, hogy a kétoldalas, 3 összekapcsolt köbös síkbeli gráfok mindig tartalmaznak-e egy Hamilton-ciklust ( Barnette-sejtés (en) ), és ha igen, akkor a grafikonokra korlátozott probléma nem lehet NP -teljes.
Egy olyan gráfban, ahol az összes csúcs páratlan fokú, a kézfogás lemmájával kapcsolatos bizonyíték azt bizonyítja, hogy a bármely élen áthaladó Hamilton-ciklusok száma mindig páros. Tehát, ha ismert egy hamiltoni ciklus, akkor egy másodiknak is léteznie kell. Ennek ellenére a második ciklus megtalálása nem tűnik könnyű matematikai feladatnak. Papadimitriou az ilyen problémák csoportosítására határozta meg a PPA komplexitási osztályt.
(en) Eric W. Weisstein , „ Hamiltonian Cycle ” , a MathWorld- on
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">