Graful eulerian
Un graf este graf eulerian dacă are un ciclu eulerian.
Se numește ciclu eulerian un ciclu care conține toate muchiile unui graf.
Cu alte cuvinte, un graf care conține un ciclu ce parcurge toate muchiile grafului se numește graf eulerian.
Exemplu de graf eulerian:
Un graf eulerian poate avea mai multe cicluri euleriene.
În exemplul anterior, chiar dacă nodul este izolat, am găsit un ciclu care să conțină toate muchiile grafului, deci graful este un graf eulerian.
Teoremă
Un graf este graf eulerian dacă și numai dacă muchiile se află în aceeași componentă conexă și are toate gradele pare.
Necesitatea gradelor pare provine de la nevoia de a „intra” și a ne și „întoarce” din noduri. Asigurăm acest lucru prin gradul par.
Transformarea în graf eulerian
Pentru ca un graf neorientat să poată fi transformat într-un graf eulerian prin adăugarea de muchii, trebuie să îndeplinească următoarele condiții:
- Toate muchiile să se afle în aceeași componentă conexă;
- Dacă numărul de noduri este par, să nu existe noduri cu grad maxim. Un graf cu număr par de noduri implică un grad maxim impar infirmă teorema;
- Numărul de noduri cu grad impar să fie par. La inserarea unei muchii, gradul a două noduri crește, astfel că pentru a impune gradele pare avem nevoie de un număr par de noduri între care inserăm.
După adăugarea muchiilor, am ales un ciclu care satisface proprietatea de ciclu eulerian (parcurge toate muchiile) și astfel putem numi graful nou un graf eulerian.