Graful eulerian

Un graf neorientat 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 cicluCiclul este un lanț în care primul nod coincide cu ultimul. ce parcurge toate muchiile grafului se numește graf eulerian.

Un graf eulerian poate avea mai multe cicluri euleriene.

Graf eulerian

  Chiar dacă nodul 6 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ăO componentă conexă este un subgraf maximal în raport cu proprietatea de conexitate. ș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ă fie 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 gradul 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)
Transformarea în graf eulerian

  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.