Question

Se consideră un graf neorientat cu 9 noduri şi muchiile [1,2], [4,8], [5,9], [2,3],[7,8], [3,7], [6,9], [6,7], [4,6], [4,5], [1,7]. Numărul minim de muchii care trebuie adăugate pentru ca graful să devină eulerian este:

Answer 1

Răspuns:

Numărul minim de muchii care trebuie adăugate pentru ca graful să devină eulerian este 2.

Explicație:

Un graf neorientat este eulerian dacă are același număr de grade de intrare și de ieșire pentru fiecare nod. Graful dat are 9 noduri, prin urmare trebuie să existe 9 noduri cu grade pare. Dacă sunt mai puține de 9 noduri cu grade pare, trebuie adăugate muchii astfel încât să se obțină 9 noduri cu grade pare. În acest caz, trebuie adăugate cel puțin 2 muchii.