Calea hamiltoniană - Hamiltonian path

Acest articol este despre natura căilor hamiltoniene. Pentru întrebarea existenței unei căi sau a unui ciclu hamiltonian într-un grafic dat, a se vedea problema căii hamiltoniene .
Un ciclu hamiltonian în jurul unei rețele de șase vârfuri

În câmpul matematic al teoriei graficelor , o cale Hamiltoniană (sau cale trasabilă ) este o cale într-un grafic nedirecționat sau direcționat care vizitează fiecare vârf exact o dată. Un ciclu hamiltonian (sau circuit hamiltonian ) este o cale Hamiltoniană care este un ciclu . Determinarea dacă astfel de căi și cicluri există în grafice este problema căii hamiltoniene , care este NP-completă .

Căile și ciclurile hamiltoniene poartă numele lui William Rowan Hamilton, care a inventat jocul icosian , cunoscut și sub numele de puzzle Hamilton , care presupune găsirea unui ciclu hamiltonian în graficul de margine al dodecaedrului . Hamilton a rezolvat această problemă folosind calculul icosian , o structură algebrică bazată pe rădăcini de unitate cu multe asemănări cu cuaternionele (inventate și de Hamilton). Această soluție nu se generalizează la grafice arbitrare.

În ciuda numirii după Hamilton, ciclurile hamiltoniene din poliedre fuseseră studiate și cu un an mai devreme de Thomas Kirkman , care, în special, a dat un exemplu de poliedru fără cicluri hamiltoniene. Chiar mai devreme, cicluri hamiltoniene și de căi în grafic cavaler al tabla de șah , The tur cavaler , a fost studiat în secolul al 9 - lea în matematică indiene de Rudrata , și în jurul același timp , în matematică islamice de către Al-Adli ar-Rumi . În Europa secolului al XVIII-lea, tururile cavalerilor au fost publicate de Abraham de Moivre și Leonhard Euler .

Definiții

O cale hamiltoniană sau cale trasabilă este o cale care vizitează fiecare vârf al graficului exact o dată. Un grafic care conține o cale Hamiltoniană se numește grafic trasabil . Un grafic este legat de Hamiltonian dacă pentru fiecare pereche de vârfuri există o cale Hamiltoniană între cele două vârfuri.

Un ciclu hamiltonian , un circuit hamiltonian , un tur de vârf sau un ciclu grafic este un ciclu care vizitează fiecare vârf exact o dată. Un grafic care conține un ciclu hamiltonian se numește grafic hamiltonian .

Noțiuni similare pot fi definite pentru graficele direcționate , unde fiecare margine (arc) a unei căi sau a unui ciclu poate fi urmărită numai într-o singură direcție (adică vârfurile sunt conectate cu săgeți și marginile trasate „coadă-cap”).

O descompunere hamiltoniană este o descompunere de margine a unui grafic în circuite hamiltoniene.

Un labirint Hamilton este un tip de puzzle logic în care scopul este de a găsi ciclul hamiltonian unic într-un grafic dat.

Exemple

Proiecții ortografice și diagrame Schlegel cu cicluri hamiltoniene ale vârfurilor celor cinci solide platonice - doar octaedrul are o cale sau ciclu eulerian, prin extinderea traseului său cu cel punctat

Proprietăți

Graficul Herschel este cel mai mic posibil Graficul poliedrică , care nu are un ciclu hamiltonian. Este prezentată o posibilă cale hamiltoniană.

Orice ciclu hamiltonian poate fi convertit într-o cale Hamiltoniană prin eliminarea uneia dintre muchiile sale, dar o cale Hamiltoniană poate fi extinsă la ciclul Hamiltonian numai dacă punctele sale finale sunt adiacente.

Toate graficele hamiltoniene sunt biconectate , dar un grafic biconectat nu trebuie să fie hamiltonian (vezi, de exemplu, graficul Petersen ).

Un grafic eulerian G (un grafic conectat în care fiecare vârf are un nivel egal) are în mod necesar un tur Euler, o plimbare închisă care trece prin fiecare margine a lui G exact o dată. Acest tur corespunde unui ciclu hamiltonian în graficul liniar L ( G ), deci graficul liniar al fiecărui grafic eulerian este hamiltonian. Graficele liniare pot avea alte cicluri hamiltoniene care nu corespund tururilor lui Euler și, în special, graficul liniar L ( G ) al fiecărui grafic hamiltonian G este el însuși hamiltonian, indiferent dacă graficul G este eulerian.

Un turneu (cu mai mult de două vârfuri) este hamiltonian dacă și numai dacă este puternic conectat .

Numărul diferitelor cicluri hamiltoniene într-un grafic complet nedirecționat pe n vârfuri este și într-un grafic complet direcționat pe n vârfuri este . Aceste numărări presupun că ciclurile care sunt aceleași în afară de punctul lor de plecare nu sunt numărate separat.

Teorema Bondy – Chvátal

Cea mai bună caracterizare a gradului de vârf al graficelor hamiltoniene a fost oferită în 1972 de teorema Bondy - Chvátal , care generalizează rezultatele anterioare de GA Dirac (1952) și Øystein Ore . Atât teoremele lui Dirac, cât și cele ale lui Ore pot fi derivate și din teorema lui Pósa (1962). Hamiltonicitatea a fost studiată pe scară largă în raport cu diferiți parametri, cum ar fi densitatea graficului , rezistența , subgrafurile interzise și distanța, printre alți parametri. Teoremele lui Dirac și Ore afirmă practic că un grafic este hamiltonian dacă are suficiente margini .

Teorema Bondy – Chvátal operează pe închiderea cl ( G ) a unui grafic G cu n vârfuri, obținută prin adăugarea în mod repetat a unei noi margini uv conectând o pereche neadiacentă de vârfuri u și v cu deg ( v ) + deg ( u ) ≥ n până când nu mai pot fi găsite perechi cu această proprietate.

Teorema lui Bondy – Chvátal (1976). Un grafic este hamiltonian dacă și numai dacă închiderea acestuia este hamiltoniană.

Deoarece graficele complete sunt hamiltoniene, toate graficele a căror închidere este completă sunt hamiltoniene, care este conținutul următoarelor teoreme anterioare de Dirac și Ore.

Teorema lui Dirac (1952). Un grafic simplu cu n vârfuri ( ) este hamiltonian dacă fiecare vârf are grad sau mai mare.
Teorema minereului (1960). Un grafic simplu cu n vârfuri () este hamiltonian dacă, pentru fiecare pereche de vârfuri neadiacente, suma gradelor lor este n sau mai mare.

Următoarele teoreme pot fi considerate ca versiuni direcționate:

Ghouila-Houiri (1960). Un grafic direcționat simplu puternic conectat cu n vârfuri este hamiltonian dacă fiecare vârf are un grad complet mai mare sau egal cu n .
Meyniel (1973). Un grafic direcționat simplu puternic conectat cu n vârfuri este hamiltonien dacă suma gradelor complete ale fiecărei perechi de vârfuri neadiacente distincte este mai mare sau egală cu .

Numărul de vârfuri trebuie dublat deoarece fiecare margine nedirecționată corespunde a două arce direcționate și astfel gradul unui vârf din graficul direcționat este de două ori gradul din graficul nedirecționat.

Rahman– Kaykobad (2005). Un grafic simplu cu n vârfuri are o cale Hamiltoniană dacă, pentru fiecare pereche de noduri non-adiacente suma gradelor lor și cea mai scurtă lungime a căii lor este mai mare decât n .

Teorema de mai sus poate recunoaște existența unei căi hamiltoniene într-un grafic și nu a unui ciclu hamiltonian.

Multe dintre aceste rezultate au analogi pentru graficele bipartite echilibrate , în care gradele de vârf sunt comparate cu numărul de vârfuri de pe o singură parte a bipartiției, mai degrabă decât cu numărul de vârfuri din întregul grafic.

Existența ciclurilor hamiltoniene în grafice plane

Teorema (Whitney, 1931). O triangulație plană cu 4 conexiuni are un ciclu hamiltonian.
Teorema (Tutte, 1956). Un grafic plan cu 4 conexiuni are un ciclu hamiltonian.

Polinomul ciclului hamiltonian

O reprezentare algebrică a ciclurilor hamiltoniene ale unui digraf ponderat dat (ale cărui arce sunt atribuite greutăți dintr-un anumit câmp la sol) este polinomul ciclului hamiltonian al matricei sale de adiacență ponderate definită ca suma produselor greutăților arcului din ciclurile hamiltoniene ale digrafului. . Acest polinom nu este identic zero ca o funcție în greutățile arcului dacă și numai dacă digraful este hamiltonian. Relația dintre complexitățile de calcul ale calculării acestuia și calculul permanentului a fost arătată de Grigoriy Kogan.

Vezi si

Note

Referințe

linkuri externe