Grafuri euleriene

Un traseu care trece o singură dată pe fiecare stradă a unui cartier și revine la punctul de plecare corespunde, într-un graf, unui ciclu eulerian: nodurile sunt intersecțiile, iar muchiile sunt străzile. Grafurile care conțin un asemenea ciclu se numesc euleriene, după matematicianul Leonhard Euler, care a studiat în 1736 problema podurilor din orașul Königsberg.

Spre deosebire de grafurile hamiltoniene, grafurile euleriene au o caracterizare simplă: este suficient să se cunoască gradele nodurilor și să se verifice conexitatea. Lecția prezintă:

• definițiile și teorema de caracterizare;
• lanțul eulerian, grafurile cu noduri izolate și graful orientat;
• verificarea unui ciclu dat și verificarea proprietății;
• determinarea unui ciclu eulerian cu ajutorul unei stive.

Noțiuni preliminare

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

• gradul unui nod x, notat d(x), este numărul muchiilor care au o extremitate în x; nodul cu gradul 0 este nod izolat;
• lanțul simplu este un lanț în care muchiile sunt distincte două câte două;
• ciclul este un lanț simplu ale cărui extremități coincid;
• graful este conex dacă între oricare două noduri distincte există un lanț.

Suma gradelor tuturor nodurilor este 2m, unde m este numărul muchiilor, deci numărul nodurilor de grad impar este par. Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie, iar conexitatea în subcapitolul Conexitate și tare conexitate.

Graful eulerian

Definiții

Fie un graf neorientat G = (X, U) cu m muchii.

• Un lanț eulerian este un lanț simplu care conține toate muchiile grafului. Fiecare muchie apare în lanț exact o dată.
• Un ciclu eulerian este un lanț eulerian ale cărui extremități coincid, adică un ciclu care conține toate muchiile grafului.
• Graful care conține cel puțin un ciclu eulerian se numește graf eulerian.

Ciclul eulerian are lungimea m și se scrie ca șir de m + 1 noduri. Muchiile nu se repetă, dar nodurile se pot repeta: ciclul eulerian nu trebuie să fie elementar. Un nod de grad 2p apare în ciclu de p ori, fără a număra repetarea nodului de pornire la sfârșitul șirului.

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

(1, 2, 3, 1, 4, 5, 2, 6, 5, 1)

Problema podurilor din Königsberg

Teorema lui Euler

Teoremă. Fie G un graf neorientat fără noduri izolate. Graful G este eulerian dacă și numai dacă este conex și fiecare nod are gradul par.

Justificare. Condiția este necesară:

• graful este conex, fiindcă ciclul eulerian trece prin toate muchiile, deci prin toate nodurile neizolate, și leagă oricare două dintre ele;
• fiecare nod are gradul par, fiindcă ciclul intră în nod pe o muchie și iese pe o altă muchie, iar muchiile folosite la trecerile prin nod sunt distincte.

Condiția este și suficientă. Pornind dintr-un nod și mergând pe muchii nefolosite, se ajunge la un nod din care nu se mai poate continua; fiindcă gradele sunt pare, acest nod este chiar nodul de pornire, deci s-a format un ciclu. Dacă au rămas muchii nefolosite, una dintre ele are o extremitate pe ciclu, fiindcă graful este conex. Din acea extremitate se formează, la fel, un al doilea ciclu, care se inserează în primul. Procedeul se repetă până se folosesc toate muchiile.

Grafuri cu noduri izolate

Un nod izolat nu este extremitatea niciunei muchii, deci nu influențează existența unui ciclu care folosește toate muchiile. Un graf cu noduri izolate este eulerian dacă graful obținut prin eliminarea nodurilor izolate este eulerian, adică dacă:

• toate nodurile au gradul par;
• toate muchiile aparțin aceleiași componente conexe.

Condiția ca graful să aibă numai grade pare nu este suficientă: un graf format din două cicluri fără noduri comune are toate gradele egale cu 2, dar nu este eulerian.

Lanțul eulerian

Un graf cu mai mult de două noduri de grad impar nu are nici lanț eulerian: fiecare nod interior al lanțului folosește muchiile în perechi, deci numai extremitățile pot avea grad impar.

Graful orientat

La graful orientat, noțiunile corespunzătoare sunt drumul eulerian și circuitul eulerian, care conțin toate arcele, fiecare o singură dată. Un graf orientat fără noduri izolate are un circuit eulerian dacă și numai dacă:

• graful neorientat obținut prin ignorarea sensului arcelor este conex;
• pentru fiecare nod x, gradul intern este egal cu gradul extern: d⁻(x) = d⁺(x).

Circuitul intră în fiecare nod pe un arc și iese pe altul, deci numărul arcelor care intră într-un nod este egal cu numărul arcelor care ies din el.

Verificarea unui ciclu dat

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

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

• c[1] = c[m+1];
• pentru fiecare i de la 1 la m, nodurile c[i] și c[i+1] sunt adiacente;
• muchiile [c[i], c[i+1]] sunt distincte două câte două.

Fiindcă șirul are m perechi de noduri consecutive și muchiile lor sunt distincte, el folosește toate cele m muchii ale grafului.

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

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

#include <iostream>
using namespace std;

const int MAX = 101, MAXM = 5001;
int a[MAX][MAX], folosit[MAX][MAX], c[MAXM], 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 <= m + 1; i++)
        cin >> c[i];
}

/* Sirul c[1..m+1] este un ciclu eulerian daca primul si ultimul nod
   coincid, iar fiecare pereche de noduri consecutive este o muchie a
   grafului, folosita o singura data. Perechile sunt m, deci sunt
   folosite toate muchiile. */
int cicluEulerian() {
    if (c[1] != c[m + 1])
        return 0;
    for (int i = 1; i <= m; i++) {
        int x = c[i], y = c[i + 1];
        if (x < 1 || x > n || y < 1 || y > n)
            return 0;
        if (a[x][y] == 0 || folosit[x][y] == 1)
            return 0;
        folosit[x][y] = folosit[y][x] = 1;
    }
    return 1;
}

int main() {
    citire();
    if (cicluEulerian())
        cout << "Sirul este un ciclu eulerian\n";
    else
        cout << "Sirul nu este un ciclu eulerian\n";
    return 0;
}

Programul afișează Sirul este un ciclu eulerian. Pentru șirul 1 2 3 1 4 5 2 6 5 2 afișează Sirul nu este un ciclu eulerian, fiindcă șirul nu revine în nodul 1, iar muchia [5, 2] apare de două ori.

Descrierea soluției. Subprogramul cicluEulerian compară primul și ultimul nod, apoi parcurge perechile de noduri consecutive. Pentru fiecare pereche verifică în matricea de adiacență că muchia există și în matricea folosit că nu a mai fost parcursă, după care o marchează în ambele sensuri. Timpul este de ordinul O(m), după citire.

Verificarea proprietății

Enunț. Se citește un graf neorientat cu n noduri și m ≥ 1 muchii. Să se afișeze dacă graful este eulerian, dacă are numai un lanț eulerian, caz în care se afișează extremitățile lanțului, sau dacă nu are nici ciclu, nici lanț eulerian.

Graful poate avea noduri izolate. Verificarea urmează teorema lui Euler și proprietatea lanțului eulerian:

1. Se calculează gradele nodurilor la citire.
2. Se parcurge graful în adâncime pornind din primul nod care are muchii. Dacă rămâne nevizitat un nod neizolat, muchiile nu sunt toate în aceeași componentă conexă.
3. Se numără nodurile de grad impar: 0 noduri înseamnă graf eulerian, 2 noduri înseamnă lanț eulerian între ele, iar mai multe noduri înseamnă că nu există nici lanț.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], g[MAX], viz[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]++;
    }
}

void dfs(int x) {
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && viz[j] == 0)
            dfs(j);
}

/* Toate muchiile sunt in aceeasi componenta conexa daca parcurgerea
   pornita din primul nod neizolat atinge toate nodurile neizolate. */
int muchiiInAceeasiComponenta() {
    int start = 1;
    while (g[start] == 0)
        start++;
    dfs(start);
    for (int i = 1; i <= n; i++)
        if (g[i] > 0 && viz[i] == 0)
            return 0;
    return 1;
}

int noduriImpare() {
    int nr = 0;
    for (int i = 1; i <= n; i++)
        if (g[i] % 2 == 1)
            nr++;
    return nr;
}

int main() {
    citire();
    int impare = noduriImpare();
    if (muchiiInAceeasiComponenta() == 0 || impare > 2)
        cout << "Graful nu are ciclu eulerian si nici lant eulerian\n";
    else if (impare == 0)
        cout << "Graful este eulerian\n";
    else {
        cout << "Graful nu este eulerian, dar are un lant eulerian intre";
        for (int i = 1; i <= n; i++)
            if (g[i] % 2 == 1)
                cout << " " << i;
        cout << "\n";
    }
    return 0;
}

Pentru graful G13 programul afișează Graful este eulerian. Pentru graful G14 afișează Graful nu este eulerian, dar are un lant eulerian intre 4 5. Pentru graful podurilor din Königsberg afișează Graful nu are ciclu eulerian si nici lant eulerian.

Descrierea soluției. Subprogramul dfs este parcurgerea în adâncime din subcapitolul Conexitate și tare conexitate. Subprogramul muchiiInAceeasiComponenta pornește parcurgerea dintr-un nod neizolat și verifică dacă au fost vizitate toate nodurile neizolate, iar noduriImpare numără nodurile de grad impar. Cu matricea de adiacență, parcurgerea cere O(n²).

Determinarea unui ciclu eulerian

Descrierea algoritmului

Algoritmul construiește ciclul eulerian după ideea din justificarea teoremei: formează un ciclu și inserează în el, pe rând, ciclurile formate din muchiile rămase. Inserarea se face cu ajutorul unei stive, fără a muta elementele unui vector. Procedeul se numește algoritmul lui Hierholzer.

Se folosesc:

• stiva st, cu vârful pe poziția vf, care conține nodurile lanțului parcurs până la momentul respectiv;
• matricea folosit, cu folosit[v][w] = folosit[w][v] = 1 după ce muchia [v, w] a fost parcursă;
• vectorul traseu, cu nt elemente, în care se adaugă nodurile scoase din stivă.