Bevezetés a számításelméletbe 2 epizód tartalma:
Elmeséljük, mi az a Hamilton kör és Hamilton út, hogyan lehet rájönni, hogy van-e egy gráfban Hamilton kör, mik a szükséges feltételei a Hamilton kör létezésének. Példák Hamilton körre, Hamilton körös feladatok.
A gráfok csúcsainak bejárására van egy nagyon speciális módszer, amit Hamilton körnek hívunk.
A Hamilton kör lényege az, hogy egy olyan körön haladunk végig a gráfban, amely a gráf összes pontját pontosan egyszer tartalmazza.
Hamilton kör nem minden gráfban van.
Ebben a gráfban épp van.
Ha a gráfból ezt az élt elhagyjuk…
akkor a megmaradó gráfban már lehet, hogy nincs Hamilton kör.
De az is lehet, hogy van.
Olyan kritérium, ami egyértelműen meg tudja mondani, hogy egy gráfban van-e Hamilton kör,nem létezik.
Árulkodó jelek viszont vannak.
Ebben a gráfban egészen biztosan nincs Hamilton kör.
Ha a gráfban van legalább egy elsőfokú csúcs, akkor a Hamilton körnek annyi.
De Hamilton út még lehet.
A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.
Lássuk, van-e ebben a gráfban Hamilton kör vagy Hamilton út.
Hamilton út biztosan van.
Viszont Hamilton kör…
Hát, az úgy ránézésre nincsen.
De ez a különbség a matematikusok és a csodadoktorok között.
Sajnos a ránézés itt kevés.
Van viszont egy remek kis tétel, ami segít.
Ehhez a tételhez azt kell megértenünk, hogy ha egy gráfnak bizonyos pontjait elhagyjuk…
akkor a gráf több komponensre esik szét.
Ebben a gráfban például most két csúcsot hagytunk el és három komponensre esett szét.
A Hamilton kör létezésének szükséges feltétele, hogy ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense van.
Ez a feltétel most nem teljesül, mert 2 darab csúcsot töröltünk, a gráf mégis 3 komponensre esett szét.
Sajnos ehhez a tételhez azért kis szerencse is kell.
Ha például ezeket a csúcsokat töröljük ki…
Akkor 2 csúcsot töröltünk és a gráf 2 tartományra esik szét.
Vagyis teljesíti a feltételt, pedig nincs Hamilton köre.
Most lássuk, mit is kezdhetnénk az eredeti gráfunkkal.
Olyan csúcsokat érdemes elhagyni, amitől a gráf várhatóan tényleg szétesik.
Terrorista hajlamúak előnyben…
4 csúcs elhagyásával a gráf 5 komponensre esett szét.
Vagyis nem teljesül a szükséges feltétel, a gráfban biztosan nincs Hamilton kör.
Hamilton kör szükséges feltétele:
Ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense lehet.
A Hamilton út szükséges feltétele hasonló:
Egy G gráfban akkor lehet Hamilton út, ha a gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k+1 darab komponense van.
Ennél a gráfnál például teljesül a feltétel.
1 csúcs elhagyásával a gráf 1+1=2 komponensre esett szét.
2 csúcs elhagyásával pedig 3 komponensre.
De minden hiába.
Vagyis a feltétel csak szükséges, de nem elégséges.
Attól, hogy teljesül, még nem biztos, hogy van Hamilton út.
És ezúttal például biztosan nincs.
A három darab első fokú csúcs miatt lehetetlen.
Vannak aztán elégséges feltételei is a Hamilton kör létezésének.
Ha egy gráfban minden csúcs foka elég nagy, akkor biztosan lesz benne Hamilton kör.
Nézzük, milyen elégséges feltételek vannak a Hamilton kör létezésére.
Az egyik ilyen feltétel a Dirac-tétel.
Ez azt mondja ki, hogy ha egy G egyszerű, n≥3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Vagyis ebben a gráfban például egészen biztosan van Hamilton kör.
Sőt, ebben is.
Dirac-tétel:
Ha egy G egyszerű, n ≥ 3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Egy másik elégséges feltétel az Ore-tétel.
Az Ore-tétel azt mondja, hogy ha egy G egyszerű, n≥3 csúcsú gráfban bármely Vi és Vj nem szomszédos csúcsra d(Vi)+d(Vj) ≥n teljesül, akkor a gráfban van Hamilton kör.
Remek. Most pedig lássunk néhány gráfot.
Bevezetés a számításelméletbe 2 epizód.