Proprietăți: conex, complet, hamiltonian, eulerian

Graf conex

Un graf e conex dacă între oricare două noduri există un lanț.

O componentă conexă e un subgraf conex maximal: nu mai poți adăuga niciun nod fără să pierzi conexitatea. Un graf neconex are cel puțin două componente.

Graf complet

Un graf complet $K_n$ are muchie între oricare două noduri distincte.

$m = \frac{n(n-1)}{2}$

Fiecare nod are gradul $n - 1$.

Graf hamiltonian

Are un ciclu hamiltonian: un ciclu elementar care trece prin toate nodurile, fiecare exact o dată.

Condiție suficientă (Dirac): dacă $n \geq 3$ și fiecare nod are $d(x) \geq n/2$, graful e hamiltonian. Atenție: e suficientă, nu necesară.

Graf eulerian

Are un ciclu eulerian: un ciclu care parcurge toate muchiile, fiecare exact o dată.

Teoremă (condiție necesară și suficientă): un graf conex e eulerian dacă și numai dacă toate nodurile au grad par.

Dacă exact două noduri au grad impar, graful nu e eulerian, dar admite un lanț eulerian între acele două noduri.

Greșeli frecvente

1. Se inversează hamiltonian cu eulerian.
2. Se aplică teorema lui Euler pe un graf neconex. Condiția cere graful conex.
3. Se crede că teorema lui Dirac e și necesară. Un graf poate fi hamiltonian fără s-o respecte.

#include <iostream>
using namespace std;

int n, m, a[101][101];
bool vizitat[101];

void dfs(int x) {
    vizitat[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] && !vizitat[y]) dfs(y);
}

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

    int componente = 0;
    for (int i = 1; i <= n; i++)
        if (!vizitat[i]) { componente++; dfs(i); }

    int impare = 0;
    for (int i = 1; i <= n; i++) {
        int g = 0;
        for (int j = 1; j <= n; j++) g += a[i][j];
        if (g % 2 == 1) impare++;
    }

    cout << "componente=" << componente << " ";
    cout << (componente == 1 ? "conex" : "neconex") << " ";
    cout << ((componente == 1 && impare == 0) ? "eulerian" : "neeulerian");
    return 0;
}