Know-how, előadás, Eulerian és Hamilton-ciklusok
Hamilton útvonalak és ciklusok
A Hamilton-ciklus (útvonal) egy egyszerű ciklus (útvonal), amely tartalmazza a gráf összes csúcsait. A 3. ábrán látható gráfban A baloldali 8.1. Oldalon a Hamilton-ciklus például a ,,,,,. A központban ábrázolt gráfban nincsenek Hamilton-ciklusok, de vannak például Hamilton útvonalak. A jobb oldali grafikonban nincsenek Hamilton útvonalak.
Külsőleg a Hamilton-ciklus meghatározása hasonló az Euler-ciklus meghatározásához. Ugyanakkor alapvető különbség van az elismerés és az építés megfelelő problémáinak megoldásában. Láttuk, hogy meglehetősen egyszerű kritérium létezik egy Euler-ciklus létezésére és egy hatékony algoritmus létrehozására. A Hamilton-ciklusok (és útvonalak) esetében nem léteznek egyszerűen ellenőrizhető, szükséges és elégséges feltételek a létezésükre, és minden ismert algoritmus sok opciót igényel néhány gráfra.
A Hamilton-ciklus kombinatorikus szempontból egyszerűen a grafikon csúcsainak permutációja. Ebben az esetben bármelyik csúcsot a ciklus kezdeti csúcsaként lehet kiválasztani, így a rögzített első elemekkel rendelkező permutációk figyelembe vehetők. A legigényesebb terv a Hamilton-ciklus megtalálásához az összes permutáció egymást követő vizsgálatát és mindegyikük igazolását jelenti, függetlenül attól, hogy egy adott gráf ciklusát képviseli-e. Ez a cselekvési mód, még akkor is, ha a csúcsok száma nem túl nagy, a permutációk számának gyors növekedése miatt gyakorlatilag megvalósíthatatlanná válik - van! rögzített első elemű elemek permutációi.
Egy racionálisabb megközelítés az, hogy megfontolja az összes lehetséges egyszerű útvonalat, amely egy tetszőlegesen választott kezdő csúcson kezdődik, amíg a Hamilton-ciklus felfedeződik vagy minden lehetséges utat vizsgálunk. Tény, hogy permutációkról is beszélünk, de sokkal rövidebb - ha például a csúcs nem szomszédos a csúcshoz, akkor minden! permutációk, amelyekben az első helyet és a másodikikat nem veszik figyelembe.
Tekintsük ezt az algoritmust részletesebben. Feltételezzük, hogy a gráfot a csúcsok szomszédai adják meg: minden csúcshoz egy sor csúcsot adnak meg. Az algoritmus minden lépcsőjén már van egy beépített útvonal, amelyet a PATH verem tárol. A PATH minden egyes csúcsához. tárolt egy sor szomszédos összes csúcsot, amelyeket még nem tekintettek a pálya lehetséges hosszabbításainak a csúcsról. Amikor egy csúcsot adunk hozzá egy úthoz, akkor a készlet egyenlő. A jövőben a megfontolt csúcsokat eltávolítják ebből a készletből. A következő lépés a PATH útvonal utolsó csúcsának szomszédságának feltárása. Ha vannak csúcspontok, amelyek nem tartoznak az útvonalhoz, akkor az egyik ilyen csúcsot hozzá kell adni az elérési úthoz. Ellenkező esetben a csúcs kizárható a veremből. Amikor a következő csúcs hozzáadásával az útra kiderül, kiderül, hogy az útvonal tartalmazza a gráf összes csúcsait. Továbbra is ellenőrizni kell, hogy az út első és utolsó csúcsai szomszédosak-e, és igenlő választ adnak-e a következő Hamilton-ciklus kiadására.
Algoritmus 2. Hamilton-ciklusok keresése
- válasszon tetszőleges csúcsot
- whiledo
- ha
- akkor vegye be
- ha a csúcs nincs PATH-ban
- majd
- ha a PATH minden csúcsot tartalmaz
- akkor a szomszédos
- majd adjon ciklust
- egyébként távolítsa el a csúcsot a PATH-ból
Ez az algoritmus nagyon hasonlít a mélységi első keresési algoritmushoz, és lényegében csak abban különbözik attól, hogy ez egy nyílt csúcs. amikor az egész környékét feltárják, nem záródik le, hanem újból új lesz (kizárva a kötegből). Az elején minden csúcs új. A folyamat akkor fejeződik be, amikor az összes csúcs ismét új lesz. Valójában ez mélyreható keresés. csak a grafikonon nem, hanem az ösvények fájában. Ennek a fának a csúcsai lehetnek egyszerű csúcspontok, amelyek a csúcson kezdődnek, és a fa éle két ösvényt kapcsol össze, amelyek közül az egyiket a csúcsból egy csúcs hozzáadásával nyeri. Az 1. ábrán. A 8.2 ábra mutatja a gráfot és az útvonalak fát a csúcsról.