Grafuri euleriene și hamiltoniene: diferențe

Un traseu eulerian folosește fiecare muchie exact o dată. Un traseu hamiltonian vizitează fiecare vârf exact o dată. Diferența dintre muchii și vârfuri schimbă radical criteriile de existență și dificultatea algoritmică.

În această lecție lucrăm cu grafuri neorientate simple. Un circuit revine în vârful de plecare. Pentru un ciclu hamiltonian, repetarea de la final a primului vârf este doar închiderea traseului, nu o vizită interioară suplimentară.

Cum funcționează

Pentru un circuit eulerian care folosește toate muchiile, toate vârfurile de grad nenul trebuie să aparțină aceleiași componente conexe și toate gradele lor trebuie să fie pare. La fiecare intrare într-un vârf trebuie să existe o ieșire, iar muchiile se grupează în perechi. Pentru un lanț eulerian deschis, exact două vârfuri au grad impar: începutul și sfârșitul.

Vârfurile izolate nu împiedică parcurgerea tuturor muchiilor, deoarece nu au muchii de vizitat. Unele enunțuri folosesc însă definiția de graf eulerian numai pentru un graf conex în ansamblu. De aceea, programul precizează cerința: clasifică posibilitatea de a folosi toate muchiile și ignoră vârfurile izolate în testul de conexitate. Pentru zero muchii acceptă traseul vid ca circuit.

Criteriile hamiltoniene sunt diferite. Gradele pare nu sunt suficiente și nici necesare pentru un ciclu hamiltonian. Un graf cu un vârf de grad unu nu poate avea ciclu hamiltonian când n>=3, dar absența gradelor unu nu garantează existența ciclului. Un graf complet cu n>=3 are ciclu hamiltonian. Pentru grafuri generale, o căutare prin backtracking construiește o ordine de vârfuri, verificând muchiile consecutive și închiderea finală; timpul poate fi exponențial.

Programul citește 1 <= n <= 100 și muchii distincte fără bucle. Matricea clasică folosește capacitatea 101 și indicii 1..n. Varianta vector păstrează aceeași reprezentare. DFS verifică numai componenta cu muchii, iar numărarea gradelor decide între circuit, lanț deschis și imposibilitate. Programul nu construiește traseul și nu pretinde că testează proprietatea hamiltoniană.

Exemplu urmărit pas cu pas

Un triunghi are toate gradele doi, deci admite circuit eulerian; el are și ciclu hamiltonian. Două triunghiuri care au un singur vârf comun admit tot circuit eulerian: gradul comun este patru, celelalte sunt doi.

Al doilea graf nu are ciclu hamiltonian, fiindcă pentru a trece între cele două triunghiuri ar trebui să revizitezi vârful comun. În schimb, un drum 1-2-3 are lanț eulerian deschis, cu capetele impare 1 și 3, și are și un lanț hamiltonian, dar nu ciclu.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int a[101][101] = {}, degree[101] = {};
bool seen[101] = {};
int n;
void dfs(int x) {
    seen[x] = true;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !seen[y])
            dfs(y);
}
int main() {
    int m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
        ++degree[x];
        ++degree[y];
    }
    int start = 0, odd = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i])
            start = i;
        if (degree[i] % 2)
            ++odd;
    }
    if (start)
        dfs(start);
    bool connected = true;
    for (int i = 1; i <= n; ++i)
        if (degree[i] && !seen[i])
            connected = false;
    if (!connected || (odd != 0 && odd != 2))
        std::cout << "NU\n";
    else
        std::cout << (odd == 0 ? "CIRCUIT" : "LANT DESCHIS") << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
std::vector<std::vector<int>> a(101, std::vector<int>(101, 0));
std::vector<int> degree(101, 0);
std::vector<char> seen(101, 0);
int n;
void dfs(int x) {
    seen[x] = true;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !seen[y])
            dfs(y);
}
int main() {
    int m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
        ++degree[x];
        ++degree[y];
    }
    int start = 0, odd = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i])
            start = i;
        if (degree[i] % 2)
            ++odd;
    }
    if (start)
        dfs(start);
    bool connected = true;
    for (int i = 1; i <= n; ++i)
        if (degree[i] && !seen[i])
            connected = false;
    if (!connected || (odd != 0 && odd != 2))
        std::cout << "NU\n";
    else
        std::cout << (odd == 0 ? "CIRCUIT" : "LANT DESCHIS") << '\n';
}

De ce funcționează și cât costă

Paritatea este necesară prin perechile intrare-ieșire. Împreună cu conexitatea părții care conține muchii, ea este suficientă pentru existența traseului eulerian. Construirea efectivă se poate face prin algoritmul Hierholzer, care unește circuite locale.

Testul cu matrice costă O(n²+m) timp și O(n²) memorie. Cu liste de adiacență poate fi O(n+m). Acest cost mic pentru proprietatea euleriană nu se transferă la verificarea hamiltoniană generală.

Greșeli frecvente

Nu înlocui „fiecare muchie” cu „fiecare vârf”. Nu aplica testul gradelor fără conexitate: două cicluri separate au grade pare, dar nu pot fi parcurse într-un singur traseu. Nu folosi criteriul neorientat pentru grafuri orientate.

Exersează

Explică de ce reuniunea a două triunghiuri fără niciun vârf comun nu admite circuit eulerian.

Rezolvare explicată: Toate gradele sunt pare, dar graful cu muchii are două componente. Nu există o muchie care să permită trecerea din primul triunghi în al doilea.

Continuă să înveți

Grade și reprezentări, conexitate și backtracking.

Întrebări frecvente

Ce se vizitează o singură dată într-un traseu eulerian?

Fiecare muchie. Același vârf poate fi întâlnit de mai multe ori, dacă traseul folosește muchii diferite.

Ce se vizitează o singură dată într-un traseu hamiltonian?

Fiecare vârf. Pentru ciclu, revenirea finală la primul vârf închide traseul și este tratată separat.

Gradele pare sunt suficiente pentru Euler?

Numai împreună cu conexitatea tuturor vârfurilor care au muchii, pentru convenția utilizată aici. Componentele separate nu pot fi legate de un singur traseu.

Exact două grade impare ce înseamnă?

Dacă partea cu muchii este conexă, există un lanț eulerian deschis. Cele două vârfuri impare sunt capetele lui.

Un graf eulerian este automat hamiltonian?

Nu. Două cicluri care au un singur vârf comun oferă un contraexemplu: muchiile pot fi parcurse, dar un ciclu prin toate vârfurile ar repeta vârful comun.