Drum hamiltonian

În domeniul matematic al teoriei grafurilor, un drum hamiltonian este un drum într-un graf neorientat sau orientat care vizitează fiecare nod o singură dată. Un ciclu hamiltonian este un drum hamiltonian care este un ciclu. Determinarea dacă un astfel de drum sau ciclu există într-un graf este problema drumului hamiltonian, care este NP-completă.

Drumurile și ciclurile hamiltoniene sunt numite după William Rowan Hamilton, care a inventat icosianul^⁠(d), denumit astăzi și puzzle-ul lui Hamilton, care implică găsirea unui ciclu hamiltonian în graful muchiilor unui dodecaedru. Hamilton a rezolvat această problemă folosind calculul icosian^⁠(d), o structură algebrică pe bază de rădăcini ale unității, cu multe similitudini cu cuaternionii (inventați tot de Hamilton). Această soluție nu se generalizează la grafuri arbitrare.

Deși își trag numele de la Hamilton, ciclurile hamiltoniene din poliedre fuseseră studiate cu un an mai devreme de Thomas Kirkman^⁠(d), care, în special, a dat un exemplu de poliedru fără cicluri hamiltoniene.^[1] Chiar mai devreme, ciclurile și drumurile hamiltoniene din graful calului^⁠(d) de pe tabla de șah, drumul calului^⁠(d), au fost studiate în secolul al IX-lea în matematica indiană^⁠(d) de către Rudrata^⁠(d), și în aceeași perioadă, în matematica musulmană de al-Adli ar-Rumi. În al Europa secolului al XVIII-lea, drumul calului a fost publicat de către Abraham de Moivre și Leonhard Euler.^[2]

Definiții

Un drum hamiltonian este un drum care vizitează fiecare nod al grafului exact o dată. Un graf este hamiltonian-conex dacă pentru fiecare pereche de noduri există un drum hamiltonian între ele.

Un ciclu Hamiltonian este un ciclu care vizitează fiecare nod o singură dată (cu excepția nodului care este și primul și ultimul). Un graf care conține un ciclu hamiltonian se numește graf hamiltonian.

Noțiuni similare pot fi definite pentru grafurile orientate, unde fiecare arc al unui drum sau ciclu poate fi urmărit numai într-o singură direcție (de exemplu, nodurile sunt conectate cu săgeți și muchiile trasate „de la coadă la cap”).

O descompunere hamiltoniană este o descompunere a unui graf pe muchii în cicluri hamiltoniene.

Exemple

un graf complet cu mai mult de două noduri este hamiltonian
orice graf ciclu^⁠(d) este hamiltonian
orice graf turneu are un număr impar de drumuri hamiltoniene (Rédei^⁠(d) 1934)
orice poliedru regulat, considerat ca graf, este hamiltonian^[3]
graful Cayley^⁠(d) al unui grup Coxeter finit este hamiltonian.

Proprietăți

Orice ciclu hamiltonian poate fi convertit într-un drum hamiltonian prin eliminarea uneia din muchiile sale, dar un drum hamiltonian poate fi extins la un ciclu hamiltonian numai dacă extremitățile sale sunt adiacente.

Toate grafurile hamiltoniene sunt biconexe^⁠(d), dar un graf biconex nu este obligatoriu și hamiltonian (de exemplu, graful Petersen).^[4]

Un graf eulerian G (graf conex în care fiecare nod are grad par) are în mod necesar un ciclu eulerian, un drum închis care parcurge fiecare muchie din G exact o dată. Acest drum corespunde unui ciclu Hamiltonian în graful linie^⁠(d) L(G), astfel încât graful linie al fiecărui graf eulerian este hamiltonian. Grafurile linie pot avea alte cicluri hamiltoniene care nu corespund ciclurilor euleriene, în special graful linie L(G) din orice graf hamiltonian G este în sine hamiltonian, indiferent dacă graful G este eulerian.^[5]

Un graf turneu (cu mai mult de două noduri) este hamiltonian dacă și numai dacă este tare conex^⁠(d).

Numărul de cicluri hamiltoniene diferite într-un graf neorientat complet de n noduri este (n − 1)! / 2 și într-un graf orientat complet de n noduri este (n − 1)!. Aceste afirmații se bazează pe presupunerea că ciclurile care sunt aceleași cu excepția punctului de plecare nu sunt luate în calcul separat.

Teorema Bondy–Chvátal

Cea mai bună caracterizare a gradelor nodurilor grafurilor hamiltoniene a fost furnizată în 1972 de teorema Bondy^⁠(d)–Chvátal^⁠(d), care generalizează rezultatele anterioare ale lui G. A. Dirac^⁠(d) (1952) și Øystein Ore^⁠(d). Atât teorema lui Dirac cât și cea a lui Ore pot fi deduse din teorema lui Pósa^⁠(d) (1962). Hamiltonicitatea a fost studiată pe larg în raport cu diferiți parametri, cum ar fi densitatea^⁠(d), duritatea^⁠(d), subgrafurile interzise^⁠(d) și distanța^⁠(d), între alți parametri.^[6] Teoremele lui Dirac și Ore afirmă în esență că un graf este hamiltonian dacă are suficiente muchii.

Teorema Bondy–Chvátal funcționează pe închiderea cl(G) unui graf G cu n noduri, obținută prin adăugarea în mod repetat a unei muchii uv care leagă o pereche de noduri neadiacente u și v cu $deg(v) + deg(u) \geq n$ , până când nu se mai pot găsi perechi cu această proprietate.

Enunț

Un graf este hamiltonian dacă și numai dacă închiderea sa este hamiltoniană.

Cum grafurile complete sunt hamiltoniene, toate grafurile a căror închidere este completă sunt hamiltoniene, acesta fiind și enunțul teoremelor lui Dirac și Ore.

Dirac (1952)

Un graf simplu cu n noduri (n ≥ 3) este hamiltonian dacă fiecare nod are gradul n / 2 sau mai mare.

Minereu (1960)

Un graf cu n noduri (n ≥ 3) este hamiltonian dacă, pentru fiecare pereche de noduri neadiacente, suma gradelor lor este n sau mai mare.

Următoarele teoreme pot fi considerate ca fiind versiuni ale acesteia:

Ghouila-Houiri (1960)

Un graf orientat simplu tare conex cu n noduri este hamiltonian dacă orice nod are gradul total mai mare sau egal cu n.

Meyniel (1973)

Un graf orientat simplu tare conex cu n noduri este hamiltonian dacă suma gradelor totale ale fiecărei perechi de noduri neadiacente distincte este mai mare sau egală cu 2n − 1.

Numărul de noduri trebuie să fie dublat pentru că orice muchie neorientată corespunde la două arce orientate și, astfel, gradul total al unui nod dintr-un graf orientat este dublul gradului unui nod dintr-un graf neorientat.

Rahman-Kaykobad (2005)

Un graf simplu cu n noduri are un drum hamiltonian dacă, pentru fiecare pereche de noduri neadiacente, suma dintre gradele lor și lungimea celei mai scurte căi între ele este mai mare decât n.^[7]

Teorema de mai sus poate recunoaște doar existența unui drum hamiltonian într-un graf și nu a unui ciclu hamiltonian. O condiție similară de suficiență pentru cicluri hamiltoniene este introdusă de Kaykobad.^[8] Rezultă:

Un graf simplu biconex^⁠(d) cu n noduri este hamiltonian dacă, pentru orice pereche de noduri neadiacente, suma gradelor lor și a căii celei mai scurte este mai mare sau egală cu n+1, cu inegalitatea fiind strictă pentru cel puțin o pereche de noduri.

Existența unor cicluri hamiltoniene în grafuri planare

Teoremă (Whitney, 1931): O triangulare plană 4-conexă are un ciclu hamiltonian.

Teoremă (Tutte, 1956): Un graf planar 4-conex are un ciclu hamiltonian.

Note

^ Biggs, N. L. (1981), „T. P. Kirkman, mathematician”, The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093 .
^ Watkins, John J. (2004), „Chapter 2: Knight's Tours”, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5 .
^ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi."
^ Eric Weinstein. „Biconnected Graph”. Wolfram MathWorld.
^ Balakrishnan, R.; Ranganathan, K. (2012), „Corollary 6.5.5”, A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296 .
^ Gould, Ronald J. (8 iulie 2002). „Advances on the Hamiltonian Problem - A Survey” (PDF). Emory University. Arhivat din original (PDF) la 13 iulie 2018. Accesat în 10 decembrie 2012.
^ Rahman, M. S.; Kaykobad, M. (aprilie 2005). „On Hamiltonian cycles and Hamiltonian paths”. Information Processing Letters. 94: 37–41. doi:10.1016/j.ipl.2004.12.002.
^ Kaykobad, Tanvir; Kaykobad, M. (10 decembrie 2015). „Hamiltonicity Revisited”. Accesat în 10 decembrie 2015.

Bibliografie

Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
DeLeon, Melissa (2000), „A study of sufficient conditions for Hamiltonian cycles” (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1) .
Dirac, G. A. (1952), „Some theorems on abstract graphs”, Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69 .
Hamilton, William Rowan (1856), „Memorandum respecting a new system of roots of unity”, Philosophical Magazine^⁠(d), 12: 446 .
Hamilton, William Rowan (1858), „Account of the Icosian Calculus”, Proceedings of the Royal Irish Academy^⁠(d), 6: 415–416 .
Meyniel, M. (1973), „Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté”, Journal of Combinatorial Theory^⁠(d), Series B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9 .
Ore, Øystein (1960), „Note on Hamilton circuits”, The American Mathematical Monthly, 67: 55, doi:10.2307/2308928 .
Pósa, L. (1962), „A theorem concerning Hamilton lines”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226 .
Whitney, Hassler (1931), „A theorem on graphs”, Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197 .
Tutte, W. T. (1956), „A theorem on planar graphs”, Trans. American Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8 .

Legături externe

Portal Matematică

Materiale media legate de drum hamiltonian la Wikimedia Commons
Cicluri euleriene și hamiltoniene

[1] Biggs, N. L. (1981), „T. P. Kirkman, mathematician”, The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093 .

[2] Watkins, John J. (2004), „Chapter 2: Knight's Tours”, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5 .

[3] Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi."

[4] Eric Weinstein. „Biconnected Graph”. Wolfram MathWorld.

[5] Balakrishnan, R.; Ranganathan, K. (2012), „Corollary 6.5.5”, A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296 .

[6] Gould, Ronald J. (8 iulie 2002). „Advances on the Hamiltonian Problem - A Survey” (PDF). Emory University. Arhivat din original (PDF) la 13 iulie 2018. Accesat în 10 decembrie 2012.

[7] Rahman, M. S.; Kaykobad, M. (aprilie 2005). „On Hamiltonian cycles and Hamiltonian paths”. Information Processing Letters. 94: 37–41. doi:10.1016/j.ipl.2004.12.002.

[8] Kaykobad, Tanvir; Kaykobad, M. (10 decembrie 2015). „Hamiltonicity Revisited”. Accesat în 10 decembrie 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]