Flashcard - Problema celor 7 Poduri

Front

Ce este un graf eulerian?

Back

Un graf eulerian este un graf în care toate nodurile au grad par, permițând astfel parcurgerea tuturor muchiilor fără a repeta vreo muchie.

Front

Ce este un graf semieulerian?

Back

Un graf semieulerian este un graf care are exact două noduri cu grad impar, permițând parcurgerea tuturor muchiilor, dar începând și terminând în noduri diferite.

Front

Care este condiția pentru ca un graf să fie eulerian?

Back

Un graf este eulerian dacă toate nodurile au grad par.

Front

Care este condiția pentru ca un graf să fie semieulerian?

Back

Un graf este semieulerian dacă are exact două noduri cu grad impar.

Front

Ce se întâmplă cu gradul nodurilor atunci când se adaugă o muchie între două noduri?

Back

Gradul fiecărui nod la care se adaugă o muchie crește cu 1.

Front

Ce se întâmplă cu gradul nodurilor atunci când se elimină o muchie?

Back

Gradul fiecărui nod de la care se elimină o muchie scade cu 1.

Front

Ce reprezintă un ciclu într-un graf?

Back

Un ciclu este o secvență de noduri în care se începe și se termină în același nod, fără a repeta alte noduri.

Front

Ce este un graf aciclic?

Back

Un graf aciclic este un graf care nu conține cicluri.

Front

Ce este un graf hamiltonian?

Back

Un graf hamiltonian este un graf care conține un ciclu hamiltonian, adică un ciclu care vizitează fiecare nod exact o dată.

Front

Cum se poate transforma un graf semieulerian într-un graf eulerian?

Back

Se poate transforma prin adăugarea unei muchii între cele două noduri cu grad impar.