Ciclu/Lanț Eulerian

Condiția existenței unui lanț eulerian într-un graf neorientat

• Un graf neorientat fără vârfuri izolate conține un lanț eulerian, dacă și numai dacă este conex și toate vârfurile au grad par, mai puțin două. Aceste vârfuri vor fi extremitățile lanțului eulerian.

• Un graf neorientat conține un lanț eulerian dacă are cel puțin un vârf izolat.

• Un graf neorientat are un lanț eulerian dacă toate vârfurile au grad impar.

• Un graf neorientat conține un lanț eulerian dacă este complet.

Definiție graf eulerian

• Un graf neorientat se numește graf eulerian dacă conține un ciclu eulerian.

• Un graf orientat se numește graf eulerian dacă are toate vârfurile de grad impar.

• Un graf se numește graf eulerian dacă are exact două vârfuri de grad impar.

• Un graf neorientat se numește graf eulerian dacă nu conține niciun ciclu.

Definiție lanț elementar

• Un lanț care conține fiecare vârf din graf.

• Un lanț care conține fiecare muchie din graf.

• Un lanț care nu conține nici o muchie din graf.

• Un lanț care conține doar vârfuri izolate.

Definiție ciclu eulerian

• Un ciclu care conține toate vârfurile din graf.

• Un ciclu care conține toate muchiile din graf.

• Un ciclu care nu se repetă niciodată.

• Un ciclu care are un număr impar de muchii.

Condiția ca un graf neorientat să fie eulerian

• Un graf neorientat fără vârfuri izolate este eulerian dacă și numai dacă este conex și toate vârfurile au grad par.

• Un graf neorientat este eulerian dacă are cel puțin un vârf izolat.

• Un graf neorientat este eulerian dacă toate vârfurile au grad impar.

• Un graf neorientat este eulerian dacă este bipartit.