Diszkrét matematika 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 képsor tartalma

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.

 

A Hamilton kör és Hamilton út szükséges feltételei

05
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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.

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez