Grafuri hamiltoniene

Un traseu care pleacă dintr-un punct, trece exact o dată prin fiecare dintre celelalte puncte și revine la punctul de plecare corespunde, într-un graf, unui ciclu hamiltonian. Grafurile care conțin un asemenea ciclu se numesc hamiltoniene, după matematicianul William Rowan Hamilton.

Spre deosebire de alte proprietăți ale grafurilor, pentru care există o regulă simplă de verificare, nu se cunoaște o condiție simplă care să fie și necesară, și suficientă pentru ca un graf să fie hamiltonian. De aceea, lecția prezintă:

• condiții necesare, care arată când un graf nu este hamiltonian;
• condiții suficiente, care arată când un graf este hamiltonian;
• căutarea ciclurilor hamiltoniene prin metoda backtracking, care decide în orice caz.

Noțiuni preliminare

Grafurile hamiltoniene se definesc cu ajutorul următoarelor noțiuni:

• graful neorientat este o pereche G = (X, U), în care X este o mulțime finită și nevidă de noduri, iar U o mulțime de perechi neordonate de noduri distincte, numite muchii;
• gradul unui nod x, notat d(x), este numărul muchiilor care au o extremitate în x;
• lanțul elementar este un lanț în care nodurile sunt distincte;
• ciclul elementar este un ciclu în care, cu excepția primului și a ultimului, nodurile sunt distincte.

Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie.

Graful hamiltonian

Definiții

Fie un graf neorientat G = (X, U) cu n noduri.

• Un lanț hamiltonian este un lanț elementar care conține toate nodurile grafului.
• Un ciclu hamiltonian este un ciclu elementar care conține toate nodurile grafului. Se obține dintr-un lanț hamiltonian dacă primul și ultimul nod al lanțului sunt adiacente: muchia dintre ele închide ciclul.
• Un graf hamiltonian este un graf care conține cel puțin un ciclu hamiltonian.

Un ciclu hamiltonian are n muchii și trece exact o dată prin fiecare nod, cu excepția nodului de pornire, care apare la început și la sfârșit. Același ciclu se poate scrie pornind din oricare nod și în oricare dintre cele două sensuri: (1, 2, 3, 6, 5, 4, 1) și (1, 4, 5, 6, 3, 2, 1) reprezintă același ciclu.

La graful orientat, noțiunile corespunzătoare sunt drumul hamiltonian și circuitul hamiltonian. Graful turneu are întotdeauna un drum hamiltonian, după cum se arată în subcapitolul Tipuri speciale de grafuri.

U = {[1,2], [1,3], [1,4],
     [2,3], [2,5], [3,6],
     [4,5], [4,6], [5,6]}

Condiții necesare

Dacă un graf cu n noduri este hamiltonian, atunci:

• n ≥ 3, fiindcă un ciclu elementar are cel puțin trei noduri;
• graful nu are noduri izolate și fiecare nod are gradul cel puțin 2: ciclul intră în fiecare nod pe o muchie și iese pe alta;
• graful este conex, fiindcă ciclul leagă oricare două noduri;
• prin eliminarea oricărui nod, împreună cu muchiile lui, graful rămâne conex: ciclul fără un nod devine un lanț care leagă toate celelalte noduri. Un nod a cărui eliminare face graful neconex se numește nod de articulație; în G11, nodul 3 este nod de articulație;
• dacă graful este bipartit, cu mulțimile de noduri A și B, atunci A și B au același număr de noduri, fiindcă nodurile ciclului aparțin alternativ celor două mulțimi. În particular, un graf bipartit cu număr impar de noduri nu este hamiltonian.

Condițiile sunt necesare, dar nu și suficiente: graful G11 le îndeplinește pe primele trei și nu este hamiltonian. Folosite invers, ele arată repede că un graf nu este hamiltonian: un graf cu un nod de grad 1 nu are ciclu hamiltonian.

Graful complet

Proprietate. Graful complet Kn, cu n ≥ 3, este hamiltonian: fiecare nod este adiacent cu toate celelalte, deci nodurile, luate în orice ordine, formează un ciclu hamiltonian.

Numărul ciclurilor hamiltoniene distincte ale lui Kn este (n − 1)!/2. Nodul de pornire se poate fixa, fiindcă un ciclu nu depinde de nodul din care începe scrierea lui; celelalte n − 1 noduri se așază în (n − 1)! ordini, iar fiecare ciclu apare de două ori, o dată pentru fiecare sens de parcurgere. Pentru K4 există 3!/2 = 3 cicluri, iar pentru K10 există 9!/2 = 181440 de cicluri.

Teoreme de caracterizare

Următoarele teoreme dau condiții suficiente: dacă graful le îndeplinește, el este hamiltonian.

Teorema lui Dirac. Dacă graful G are n ≥ 3 noduri și gradul fiecărui nod x satisface condiția d(x) ≥ n/2, atunci G este hamiltonian.

Teorema lui Ore. Dacă graful G are n ≥ 3 noduri și pentru oricare două noduri neadiacente x și y este îndeplinită condiția d(x) + d(y) ≥ n, atunci G este hamiltonian.

Teorema lui Dirac este un caz particular al teoremei lui Ore: dacă fiecare nod are gradul cel puțin n/2, atunci suma gradelor oricăror două noduri este cel puțin n.

Exemplu. În graful G12, n = 6 și fiecare nod are gradul 3. Condiția d(x) ≥ 6/2 = 3 este îndeplinită pentru toate nodurile, deci, după teorema lui Dirac, graful este hamiltonian, ceea ce confirmă ciclurile găsite mai sus.

Verificarea unui ciclu dat

Enunț. Se citește un graf neorientat cu n noduri și m muchii, apoi un șir de n + 1 noduri. Să se verifice dacă șirul este un ciclu hamiltonian al grafului.

Șirul c[1], c[2], …, c[n+1] este un ciclu hamiltonian dacă:

• graful are cel puțin 3 noduri, iar c[1] = c[n+1];
• nodurile c[1], …, c[n] sunt distincte, deci sunt toate cele n noduri ale grafului;
• pentru fiecare i de la 1 la n, nodurile c[i] și c[i+1] sunt adiacente.

Date de intrare. Pe prima linie n și m, pe următoarele m linii muchiile, pe ultima linie cele n + 1 noduri ale șirului. Pentru graful G12:

6 9
1 2
1 3
1 4
2 3
2 5
3 6
4 5
4 6
5 6
1 2 3 6 5 4 1

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], c[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    for (int i = 1; i <= n + 1; i++)
        cin >> c[i];
}

/* Graful are cel putin 3 noduri, primul si ultimul nod din sir coincid,
   iar primele n noduri sunt distincte, deci sunt toate nodurile grafului. */
int noduriCorecte() {
    int apare[MAX] = {0};
    if (n < 3 || c[1] != c[n + 1])
        return 0;
    for (int i = 1; i <= n; i++) {
        if (c[i] < 1 || c[i] > n || apare[c[i]] == 1)
            return 0;
        apare[c[i]] = 1;
    }
    return 1;
}

/* Oricare doua noduri consecutive din sir sunt adiacente. */
int muchiiCorecte() {
    for (int i = 1; i <= n; i++)
        if (a[c[i]][c[i + 1]] == 0)
            return 0;
    return 1;
}

int main() {
    citire();
    if (noduriCorecte() && muchiiCorecte())
        cout << "Sirul este un ciclu hamiltonian\n";
    else
        cout << "Sirul nu este un ciclu hamiltonian\n";
    return 0;
}

Programul afișează Sirul este un ciclu hamiltonian. Pentru șirul 1 2 3 6 4 5 1 afișează Sirul nu este un ciclu hamiltonian, fiindcă nodurile 5 și 1 nu sunt adiacente.

Descrierea soluției. Subprogramul noduriCorecte marchează în vectorul apare nodurile întâlnite și oprește verificarea la primul nod repetat sau în afara intervalului [1, n]. Subprogramul muchiiCorecte verifică în matricea de adiacență fiecare pereche de noduri consecutive. Timpul este de ordinul O(n).

Verificarea condițiilor din teoreme

Enunț. Se citește un graf neorientat. Să se afișeze dacă graful nu este hamiltonian, conform unei condiții necesare, dacă este hamiltonian, conform teoremei lui Dirac sau a lui Ore, ori dacă aceste condiții nu decid.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], g[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
        g[x]++;
        g[y]++;
    }
}

/* Conditie necesara: intr-un graf hamiltonian cu cel putin 3 noduri,
   fiecare nod are gradul cel putin 2. */
int areNodCuGradMic() {
    for (int i = 1; i <= n; i++)
        if (g[i] < 2)
            return 1;
    return 0;
}

/* Conditie suficienta (teorema lui Dirac): n >= 3 si
   gradul fiecarui nod este cel putin n/2. */
int conditiaDirac() {
    if (n < 3)
        return 0;
    for (int i = 1; i <= n; i++)
        if (2 * g[i] < n)
            return 0;
    return 1;
}

/* Conditie suficienta (teorema lui Ore): n >= 3 si pentru oricare
   doua noduri neadiacente suma gradelor este cel putin n. */
int conditiaOre() {
    if (n < 3)
        return 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i][j] == 0 && g[i] + g[j] < n)
                return 0;
    return 1;
}

int main() {
    citire();
    if (n < 3 || areNodCuGradMic())
        cout << "Graful nu este hamiltonian\n";
    else if (conditiaDirac())
        cout << "Graful este hamiltonian (teorema lui Dirac)\n";
    else if (conditiaOre())
        cout << "Graful este hamiltonian (teorema lui Ore)\n";
    else
        cout << "Conditiile nu decid; se cauta un ciclu hamiltonian\n";
    return 0;
}

Pentru graful G12 programul afișează Graful este hamiltonian (teorema lui Dirac). Pentru graful G11 și pentru graful ciclu cu 6 noduri afișează Conditiile nu decid; se cauta un ciclu hamiltonian: primul nu este hamiltonian, al doilea este.

Descrierea soluției. Gradele se calculează la citire, în vectorul g. Subprogramul areNodCuGradMic verifică o condiție necesară, iar conditiaDirac și conditiaOre verifică cele două condiții suficiente. Ordinea verificărilor din main pune întâi condiția care exclude graful, apoi condițiile care îl confirmă. Verificarea teoremei lui Ore examinează toate perechile de noduri, deci cere O(n²).