Question

Se consideră graful neorientat cu 7 noduri şi muchiile: [1,2], [1,4], [1,5], [1,7], [2,3],,7], [3,4], [3,5], [3,7], [4,5], [5,6], [6,7].Care este numărul minim de muchii ce trebuie înlăturate din graf astfel încât să devină eulerian?

Answer 1

Răspuns:

Un graf neorientat este eulerian dacă şi numai dacă are 0 sau 2 noduri impare.

Pentru graful neorientat cu 7 noduri şi muchiile menţionate toate nodurile sunt impare, astfel încât pentru a fi eulerian trebuie să înlăturăm cel puțin una din muchiile sale.

Numărul minim de muchii ce trebuie înlăturate din graf pentru a deveni eulerian este 1