Redaktor:Patrick23

Hamiltonovské grafy

Úvod

V roku 1857 WILLIAM R. HAMILTON zostrojil matematický hlavolam, ktorého cielom bolo nájst takú uzavretú prechádzku po hranách pravidelného dvanáststena, ktorá by obsahovala každý vrchol práve raz. Ak zabudneme na plochy dvanáststena a nakreslíme jeho vrcholy a hrany v rovine, tak dostaneme graf nakreslený na obrázku:

Definícia Hamiltonovskej kružnice

Hamiltonovská kružnice grafu je taká cesta, ktorá prejde práve raz všetky vrcholy grafu a medzi jeho začiatočným a konečným vrcholom existuje platná cesta. Teda riešením Hamiltonovho hlavolamu je Hamiltonovská kružnica. Zistiť, či má graf uzavretý Eulerovský ťah, je ľahký problém, lebo stačí zistiť súvislosť grafu a paritu stupňov všetkých jeho vrcholov. Je prekvapujúce, že analogický problém pre Hamiltonovské kružnice je ťažký. Tento problém patrí do skupiny takzvaných NP-úplných problémov. Poznáme však veľmi veľa podmienok, ktorých splnenie vynucuje v grafe existenciu Hamiltonovskej kružnice. Jednu z najznámejších postačujúcich podmienok tohto typu dokázal O. ORE v roku 1960(1.podmienka).

Postačujúce podmienky

1. Nech G je graf, |V | = n, n ≥ 3. Ak pre každú dvojicu vrcholov, ktoré nie sú spojené hranou súčet ich stupňov je aspoň n, tak G je hamiltonovský.

2. Nech G je graf, |V | = n, n ≥ 3. Ak má každý vrchol stupeň aspoň n/2 , tak graf je hamiltonovský.

3. Nech G je graf, |V | = n a predpokladajme, že n ≥ 3. Ak pre každé prirodzené číslo k < n/2 je počet vrcholov, ktorých stupeň neprevyšuje k, menší ako k, tak je graf hamiltonovský.

Príklady

1.Príklad

                                       
               Obr.1                                                       Obr.2

Podľa podmienok uvedených hore graf ktorý je uvedený hore na obrázku(Obr. 1) nie je Hamiltonovský, pretože nespĺňa ani jednu z podmienok. Síce nespĺňa ani jednu z podmienok ale dá sa nakresliť hamiltonovská kružnica, ktorú som uviedol červenou farbou na obr. 2. Je to možno spôsobené tým, že neexistuje nutná podmienka hamiltonovskych grafov.

2.Príklad

Graf na obrázku spĺňa všetky 3 podmienky: 1. podmienku, lebo každý jeho vrchol má stupeň aspoň 3 a spĺňa aj 2. podmienku, lebo každé dva vrcholy nespojené hranou majú súčet stupňov aspoň 6. A konečne spĺňa aj 3. podmienku, lebo v ňom nie sú žiadne vrcholy stupňa menšieho ako 3.