Graf eulerian

Triunghiul 1–2–3–1 are trei muchii, iar ciclul le parcurge pe toate. Aici contează muchiile, nu obligația de a vizita fiecare nod exact o dată.

Definițiile

Un lanț eulerian este un lanț care conține fiecare muchie a grafului exact o dată. Dacă se închide, adică primul și ultimul nod coincid, este un ciclu eulerian. Un graf care are un ciclu eulerian se numește graf eulerian. Nodurile se pot repeta: important este ca nicio muchie să nu fie folosită de două ori și să nu rămână nefolosită.

Teorema lui Euler, pe înțeles

Când un ciclu trece printr-un nod, intră pe o muchie și iese pe alta, deci consumă muchiile nodului câte două. Ca toate muchiile să fie folosite, fiecare nod trebuie să aibă grad par. În plus, toate muchiile trebuie să fie în aceeași bucată a grafului, deci graful trebuie să fie conex. Teorema spune că aceste două condiții sunt și suficiente: un graf fără noduri izolate este eulerian dacă și numai dacă este conex și toate nodurile lui au grad par. Teorema se enunță de obicei pentru grafuri fără noduri izolate; un nod izolat nu are muchii, deci nu poate fi atins de niciun ciclu, iar la examen enunțul precizează cum se tratează.

Pentru lanț, nodurile de la capete fac excepție: din primul nod doar se iese, iar în ultimul doar se intră. De aceea un lanț eulerian care nu e ciclu există exact când graful este conex și are două noduri de grad impar, iar lanțul pornește dintr-unul și se termină în celălalt. Problema a fost rezolvată de Leonhard Euler în 1736, pentru cele șapte poduri din Königsberg: cele patru zone de uscat aveau 5, 3, 3 și 3 poduri, adică patru noduri de grad impar, deci nu exista o plimbare care să treacă o singură dată pe fiecare pod.

Cum construiești ciclul

Pornești dintr-un nod oarecare și mergi pe muchii nefolosite, ștergându-le pe măsură ce treci, până te întorci în nodul de plecare (cu grade pare, nu ai cum să te blochezi în alt nod). Dacă au rămas muchii nefolosite, pornești, la fel, un al doilea ciclu dintr-un nod al primului ciclu care mai are muchii libere și îl inserezi în primul ciclu în acel nod. Repeți până folosești toate muchiile.

Cum verifici în C++

Calculezi gradele din matricea de adiacență, apoi parcurgi graful în adâncime din primul nod care are muchii și verifici că ai atins toate nodurile neizolate. Programul afișează eulerian, lant eulerian intre x si y sau nu.

#include <iostream>
using namespace std;

int a[101][101], g[101], viz[101], n, m;

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

int main() {
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
        g[x]++;
        g[y]++;
    }
    int start = 0;
    for (int i = n; i >= 1; i--)
        if (g[i] > 0)
            start = i;                      // primul nod cu muchii
    if (start == 0) {
        cout << "nu\n";                     // graf fara muchii
        return 0;
    }
    dfs(start);
    int conex = 1, impare = 0, x1 = 0, x2 = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i] > 0 && viz[i] == 0)
            conex = 0;                      // nod cu muchii neatins
        if (g[i] % 2 == 1) {
            impare++;
            if (x1 == 0) x1 = i; else x2 = i;
        }
    }
    if (conex == 1 && impare == 0)
        cout << "eulerian\n";
    else if (conex == 1 && impare == 2)
        cout << "lant eulerian intre " << x1 << " si " << x2 << "\n";
    else
        cout << "nu\n";
    return 0;
}

Exemplu de verificare. În triunghiul 1–2–3–1, cele trei grade sunt 2, deci traseul este un ciclu eulerian. Dacă adăugăm nodul 4 și muchia $[3,4]$, nodurile 3 și 4 au grad impar. Traseul 4–3–1–2–3 folosește fiecare muchie o dată și este un lanț eulerian deschis.

Exemplu — grade pare, graf neconex. Muchiile $[1,2]$, $[2,3]$, $[3,1]$ formează un triunghi, iar $[4,5]$, $[5,6]$, $[6,4]$ formează altul. Fiecare vârf are gradul 2, dar muchiile aparțin la două componente conexe. Niciun traseu nu poate folosi muchiile ambelor triunghiuri, deci graful nu are ciclu eulerian.

Exemple rezolvate

Exemplul 1: un graf eulerian

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

1. Gradele: d(1) = 2, d(2) = 2, d(3) = 4, d(4) = 2, d(5) = 2, toate pare.
2. Graful este conex: din nodul 3 ajungi direct la toate celelalte.
3. Deci graful este eulerian. Un ciclu eulerian: 1, 2, 3, 4, 5, 3, 1. Nodul 3 apare de două ori, iar fiecare dintre cele 6 muchii apare o singură dată.

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

eulerian

Exemplul 2: o muchie în plus

Aceluiași graf i se adaugă muchia [1, 4]. Mai este eulerian?

1. Gradele lui 1 și 4 cresc la 3, deci graful are exact două noduri de grad impar.
2. Graful rămâne conex, așa că nu are ciclu eulerian, dar are un lanț eulerian între nodurile 1 și 4, de exemplu 1, 2, 3, 1, 4, 3, 5, 4.
3. Programul afișează lant eulerian intre 1 si 4.

Exemplul 3: grafurile complete

Sunt eulerieni graful complet cu 4 noduri și cel cu 5 noduri?

1. În graful complet cu 4 noduri, fiecare nod are gradul 3, impar, deci graful nu este eulerian; are patru noduri de grad impar, deci nu are nici lanț eulerian.
2. În graful complet cu 5 noduri, fiecare nod are gradul 4, par, iar graful este conex, deci este eulerian.

Exemplul 4: numărul minim de muchii adăugate

Graful are nodurile 1, 2, 3, 4, 5 și muchiile [1, 2], [1, 3], [1, 4], [1, 5]. Care este numărul minim de muchii care trebuie adăugate ca graful să devină eulerian?

1. Gradele: d(1) = 4, iar nodurile 2, 3, 4, 5 au gradul 1. Sunt patru noduri de grad impar.
2. O muchie nouă schimbă paritatea a exact două noduri, deci sunt necesare cel puțin 4 / 2 = 2 muchii.
3. Două muchii ajung: [2, 3] și [4, 5] unesc noduri de grad impar care nu erau adiacente. Toate gradele devin pare (4, 2, 2, 2, 2), iar graful rămâne conex. Răspunsul este 2.

Exemplul 5: nivel de examen, numărul minim de muchii eliminate

Graful are 6 noduri și 9 muchii: triunghiul [1, 2], [1, 3], [2, 3], triunghiul [4, 5], [4, 6], [5, 6] și muchiile [1, 4], [2, 5], [3, 6], care le leagă. Care este numărul minim de muchii care trebuie eliminate, astfel încât graful obținut să aibă un lanț eulerian (închis sau nu)?

1. Fiecare nod are gradul 3, deci toate cele 6 noduri au grad impar. Un lanț eulerian cere cel mult două noduri de grad impar.
2. Eliminarea unei muchii schimbă paritatea exact a două noduri. Cu o singură muchie eliminată rămân 4 noduri de grad impar, prea multe; sunt deci necesare cel puțin 2 muchii.
3. Două muchii ajung, dacă au toate cele patru capete diferite: eliminând [1, 4] și [2, 5], nodurile 1, 2, 4, 5 ajung la gradul 2, iar 3 și 6 rămân cu gradul 3.
4. Graful rămâne conex: triunghiurile sunt încă legate prin muchia [3, 6]. Are deci un lanț eulerian între nodurile 3 și 6, de exemplu 3, 1, 2, 3, 6, 4, 5, 6. Răspunsul este 2.

Verificare: pe graful cu cele 7 muchii rămase, programul de mai sus afișează lant eulerian intre 3 si 6, iar pe graful inițial afișează nu.

Un lanț eulerian deschis, cu capete diferite, cere exact două vârfuri de grad impar și conexitatea părții cu muchii. Pentru ciclu, numărul lor este zero. Vârfurile izolate nu afectează posibilitatea de a parcurge toate muchiile, deoarece ele nu participă la parcurgere. Numărul vârfurilor de grad impar este întotdeauna par, deci un graf nu poate avea exact un vârf impar. Lungimea unui ciclu sau lanț eulerian este numărul tuturor muchiilor grafului. Pe un desen, calculează gradele și numără vârfurile impare: zero înseamnă ciclu eulerian, două înseamnă lanț eulerian deschis, iar orice alt număr înseamnă că graful conex nu poate fi parcurs dintr-o singură trecere. Un graf conex cu patru vârfuri impare cere cel puțin două lanțuri separate pentru a-i parcurge toate muchiile.

Exemplu în formatul examenului. Pentru care dintre perechile de valori ale lui $n$ de mai jos graful complet $K_n$ admite un ciclu eulerian pentru ambele valori?

• a) 3 și 4
• b) 3 și 5
• c) 4 și 6
• d) 5 și 6

Răspunsul corect este b). Graful $K_n$ este conex, iar gradul fiecărui vârf este $n-1$, deci ciclul eulerian există dacă și numai dacă $n-1$ este par, adică $n$ impar. Perechea 3 și 5 conține numai valori impare. În celelalte variante apare cel puțin o valoare pară: $K_4$ are patru vârfuri de grad 3, iar $K_6$ are șase vârfuri de grad 5.

Exemplu în formatul examenului — capetele unui lanț. Un graf are vârfurile 1, 2, 3, 4 și muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,1]$, $[1,3]$. Care pereche de vârfuri poate fi formată din capetele unui lanț eulerian deschis al grafului?

• a) 1 și 2
• b) 1 și 3
• c) 2 și 4
• d) 3 și 4

Răspunsul corect este b). Gradele sunt $3,2,3,2$ și graful este conex, deci există un lanț eulerian deschis, iar capetele lui sunt cele două vârfuri de grad impar, 1 și 3. Un astfel de lanț este 1–2–3–4–1–3 și are 5 muchii, adică toate muchiile grafului. Variantele a), c) și d) conțin cel puțin un vârf de grad par, care nu poate fi capăt al unui lanț eulerian deschis.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: programa de examen enumeră, la proprietățile grafurilor neorientate, graful conex, componenta conexă, graful complet, graful hamiltonian și graful eulerian (programa de examen, anexa 2 la OMECTS 4800/2010). La sesiunea din iunie–iulie 2026, ultimul item al Subiectului I a cerut numărul maxim de muchii care pot fi adăugate unui graf neorientat dat, astfel încât graful obținut să fie eulerian; se rezolvă cu același raționament despre paritatea gradelor ca exemplele 4 și 5 (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 neorientate și orientate, cu terminologia, proprietățile și parcurgerea lor, sunt la clasa a XI-a (programa de clasa a XI-a, OMECI 5099/2009).

Greșeli frecvente

• Greșit: ciclul eulerian trece prin fiecare nod exact o dată.
  Corect: trece prin fiecare muchie exact o dată; ciclul hamiltonian este cel care vizitează fiecare nod o dată, iar un graf poate fi eulerian fără să fie hamiltonian și invers.
• Greșit: toate gradele sunt pare, deci graful este eulerian.
  Corect: este necesară și conexitatea părții cu muchii; două cicluri separate au toate gradele pare, dar nu pot fi parcurse într-un singur ciclu.
• Greșit: două noduri de grad impar permit un ciclu eulerian închis.
  Corect: cu exact două noduri de grad impar există un lanț eulerian deschis, dar graful nu este eulerian.
• Greșit: la exemplele cu muchii adăugate, se adaugă o muchie între două noduri deja adiacente.
  Corect: în grafurile neorientate de la Bacalaureat două muchii diferă prin cel puțin o extremitate, deci verifici că perechea nu există deja.
• Greșit: conexitatea se verifică parcurgând graful din nodul 1.
  Corect: dacă nodul 1 este izolat, parcurgerea din el nu atinge nimic; pornești din primul nod care are muchii, ca în program.

Înainte și după

Întrebări frecvente