Graf hamiltonian

Triunghiul 1–2–3–1 este hamiltonian. Spre deosebire de ciclul eulerian, aici contează nodurile; nu este obligatoriu să folosim toate muchiile grafului.

Definițiile

Un lanț hamiltonian trece prin fiecare nod al grafului exact o dată. Dacă, în plus, ultimul nod este adiacent cu primul și închizi lanțul cu această muchie, obții un ciclu hamiltonian, iar graful se numește hamiltonian. Ciclul are n noduri distincte și n muchii; alte muchii ale grafului pot rămâne nefolosite. Comparat cu ciclul eulerian, care folosește fiecare muchie exact o dată, ciclul hamiltonian vizitează fiecare nod exact o dată (graful eulerian).

Condițiile

Pentru grafurile hamiltoniene nu se cunoaște o condiție simplă, cu gradele, care să fie și necesară, și suficientă. De aceea lucrezi cu două tipuri de condiții:

• necesare, care, dacă nu sunt îndeplinite, arată că graful nu e hamiltonian: graful trebuie să fie conex, iar fiecare nod trebuie să aibă gradul cel puțin 2, pentru că ciclul intră în nod pe o muchie și iese pe alta;
• suficiente, care, dacă sunt îndeplinite, arată că graful este hamiltonian: dacă n ≥ 3 și fiecare nod are gradul cel puțin n / 2, graful este hamiltonian (teorema lui Dirac).

Când niciuna nu decide, cauți efectiv un ciclu.

Căutarea unui ciclu cu backtracking

Fixezi nodul 1 ca prim nod al ciclului (orice ciclu hamiltonian trece prin el). Pe pozițiile 2, …, n pui, cu backtracking, noduri nefolosite, adiacente cu nodul de pe poziția anterioară. Când ai completat toate pozițiile, verifici că ultimul nod este adiacent cu nodul 1. Metoda încearcă, în cel mai rău caz, (n − 1)! ordini, deci se folosește pe grafuri mici.

#include <iostream>
using namespace std;

int a[21][21], x[21], folosit[21], n, m, gasit = 0;

void back(int k) {
    if (gasit) return;                          // ma opresc la primul ciclu
    for (int v = 2; v <= n; v++)
        if (folosit[v] == 0 && a[x[k - 1]][v] == 1) {
            x[k] = v;
            folosit[v] = 1;
            if (k == n) {
                if (a[v][1] == 1) {             // inchid ciclul
                    gasit = 1;
                    for (int i = 1; i <= n; i++) cout << x[i] << " ";
                    cout << "1\n";
                }
            } else
                back(k + 1);
            folosit[v] = 0;
            if (gasit) return;
        }
}

int main() {
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        int p, q;
        cin >> p >> q;
        a[p][q] = a[q][p] = 1;
    }
    x[1] = 1;
    folosit[1] = 1;
    back(2);
    if (gasit == 0)
        cout << "nu este hamiltonian\n";
    return 0;
}

Exemplu — pătrat cu diagonală și lanț fără ciclu.

În graful cu nodurile 1, 2, 3, 4 și muchiile unui pătrat plus diagonala $1,3$, traseul 1–2–3–4–1 este ciclu hamiltonian, iar diagonala rămâne nefolosită. Un nod de grad 1 într-un graf cu cel puțin trei noduri împiedică existența unui ciclu hamiltonian, fiindcă ciclul trebuie să intre și să iasă prin muchii distincte.

Lanțul 1–2–3 are un traseu care vizitează toate nodurile, dar nu are ciclu hamiltonian, deoarece lipsește muchia 3–1. Distinge întotdeauna cererea de lanț de cea de ciclu.

În $K_4$, fiecare nod are gradul 3, iar $3\ge 4/2$; ciclul 1–2–3–4–1 este hamiltonian, conform teoremei lui Dirac. Un graf poate fi hamiltonian și fără să îndeplinească această condiție, deci ea nu este necesară.

Exemplu — limita condiției necesare. Două triunghiuri cu un singur nod comun formează un graf conex în care fiecare nod are gradul cel puțin 2. Totuși, graful nu are ciclu hamiltonian: pentru a trece prin ambele triunghiuri și a reveni la început, ar trebui vizitat de două ori nodul comun.

Exemple rezolvate

Exemplul 1: un graf hamiltonian care nu e eulerian

Graful are 5 noduri și muchiile [1, 2], [2, 3], [3, 4], [4, 5], [5, 1], [1, 3]. Este hamiltonian? Dar eulerian?

1. Ciclul 1, 2, 3, 4, 5, 1 trece o dată prin fiecare nod, deci graful este hamiltonian. Muchia [1, 3] rămâne nefolosită.
2. Gradele lui 1 și 3 sunt 3, impare, deci graful nu este eulerian.

Pentru intrarea 5 6 urmată de cele șase muchii, programul de mai sus afișează:

1 2 3 4 5 1

Exemplul 2: un graf eulerian care nu e hamiltonian

Graful are 5 noduri și muchiile [1, 2], [2, 3], [3, 1], [3, 4], [4, 5], [5, 3]: două triunghiuri cu nodul comun 3.

1. Toate gradele sunt pare și graful este conex, deci este eulerian.
2. Un ciclu care pleacă din triunghiul {1, 2, 3} și trebuie să ajungă la nodurile 4 și 5 trece prin 3 la dus și încă o dată la întors. Nodul 3 s-ar repeta, deci nu există ciclu hamiltonian.
3. Programul confirmă: afișează nu este hamiltonian.

Exemplul 3: condiția cu gradele

Graful are 6 noduri, împărțite în grupele {1, 2, 3} și {4, 5, 6}, iar fiecare nod din prima grupă este unit cu fiecare nod din a doua. Este hamiltonian?

1. Fiecare nod are gradul 3 = 6 / 2, deci condiția suficientă este îndeplinită: graful este hamiltonian.
2. Un ciclu: 1, 4, 2, 5, 3, 6, 1, care alternează între cele două grupe. Programul afișează exact acest ciclu, primul găsit în ordinea crescătoare a nodurilor.

Exemplul 4: ciclurile din graful complet

Câte cicluri hamiltoniene are graful complet cu 5 noduri?

1. Fixezi nodul 1 la început. Celelalte 4 noduri se pot ordona în 4! = 24 de moduri, iar oricare ordine dă un ciclu, pentru că toate muchiile există.
2. Fiecare ciclu apare de două ori, o dată în fiecare sens (1, 2, 3, 4, 5, 1 și 1, 5, 4, 3, 2, 1), deci sunt 24 / 2 = 12 cicluri.

#include <iostream>
using namespace std;

int n, x[12], folosit[12], nr = 0;

void back(int k) {
    for (int v = 2; v <= n; v++)
        if (folosit[v] == 0) {
            x[k] = v;
            folosit[v] = 1;
            if (k == n) nr++;      // in graful complet orice ordine inchide un ciclu
            else back(k + 1);
            folosit[v] = 0;
        }
}

int main() {
    cin >> n;
    folosit[1] = 1;
    back(2);
    cout << nr / 2 << "\n";
    return 0;
}

Pentru intrarea 5, programul afișează:

12

Pentru 4 afișează 3, iar pentru 6 afișează 60 = 5! / 2.

Exemplul 5: nivel de examen, câte muchii pot fi eliminate

Care este numărul maxim de muchii care pot fi eliminate din graful complet cu 7 noduri, astfel încât graful obținut să rămână hamiltonian?

1. Graful complet cu 7 noduri are 7 · 6 / 2 = 21 de muchii.
2. Un graf hamiltonian cu 7 noduri trebuie să păstreze cel puțin cele 7 muchii ale unui ciclu hamiltonian.
3. Dacă elimini toate celelalte muchii, rămâne chiar ciclul, care este hamiltonian. Deci se pot elimina cel mult 21 − 7 = 14 muchii.

La verificarea unui traseu propus, controlează trei lucruri: fiecare trecere este muchie, fiecare vârf apare o singură dată înaintea revenirii și traseul se închide. Un graf poate fi hamiltonian fără să fie eulerian sau invers: $K_4$ este hamiltonian, dar nu eulerian, iar două triunghiuri cu un vârf comun sunt euleriene, dar nu hamiltoniene, fiindcă vârful comun ar trebui vizitat de două ori. Condițiile suficiente cunoscute nu trebuie confundate cu definiția: un grad mare nu demonstrează singur existența ciclului într-un graf arbitrar, iar un vârf de grad 1 o infirmă. Un graf cu un vârf a cărui eliminare îl desparte în mai multe componente nu este hamiltonian.

Exemplu în formatul examenului. Un graf are vârfurile 1, 2, 3, 4, 5 și muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,1]$, $[4,5]$. Care afirmație este adevărată?

• a) Succesiunea 1–2–3–4–5–1 este ciclu hamiltonian.
• b) Graful nu are ciclu hamiltonian, deoarece vârful 5 are gradul 1.
• c) Graful are ciclu hamiltonian, deoarece este conex.
• d) Succesiunea 1–2–3–4–1 este ciclu hamiltonian.

Răspunsul corect este b). Vârful 5 are o singură muchie, $[4,5]$, deci un ciclu nu poate intra în el și ieși din el prin muchii diferite. Varianta a) folosește muchia $[5,1]$, care nu există. Varianta c) invocă numai conexitatea, care este necesară, dar nu suficientă. Varianta d) este un ciclu, dar nu vizitează vârful 5, deci nu este hamiltonian. Graful are totuși un lanț hamiltonian, 5–4–1–2–3.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: programa de examen enumeră, printre proprietățile grafurilor neorientate, graful hamiltonian și graful eulerian, alături de graful conex, componenta conexă și graful complet (programa de examen, anexa 2 la OMECTS 4800/2010). Itemii despre grafuri sunt la Subiectul I, cu patru variante de răspuns; în 2026, unul dintre ei a fost despre un graf eulerian (subiectele și baremele Bac 2026). Formatul descris este cel din 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.
• Programa școlară: grafurile, cu terminologia și proprietățile lor, sunt la clasa a XI-a pe programa veche (programa de clasa a XI-a, OMECI 5099/2009).

Greșeli frecvente

• Greșit: ciclul hamiltonian trebuie să folosească toate muchiile, ca ciclul eulerian.
  Corect: trebuie să includă toate nodurile, fiecare o singură dată (exemplele 1 și 2).
• Greșit: condiția suficientă se folosește ca necesară, iar graful cu un grad mai mic decât n / 2 se declară nehamiltonian.
  Corect: un ciclu cu 10 noduri are toate gradele 2 și este hamiltonian.
• Greșit: verificarea gradelor pare decide hamiltonianitatea.
  Corect: este criteriu pentru eulerianitate, împreună cu conexitatea.
• Greșit: ciclul se numără de două ori, parcurs în sens invers sau pornit din alt nod.
  Corect: este același ciclu; de aici împărțirea la 2 și fixarea nodului de plecare.
• Greșit: un lanț hamiltonian face graful hamiltonian.
  Corect: trebuie ca ultimul nod să fie adiacent cu primul.
• Greșit: un nod de grad 1 poate fi inclus într-un ciclu hamiltonian.
  Corect: nu are două muchii distincte pentru intrare și ieșire.
• Greșit: noțiunea se aplică grafurilor cu 1 sau 2 noduri.
  Corect: ciclurile au cel puțin 3 muchii distincte, de aceea se folosește pentru n ≥ 3.

Înainte și după

Întrebări frecvente