Question

Un graf neorientat are 10 noduri, numerotate de la 1 la 10, și muchiile [1,2], [2,3], [2,10], [3,10], [4,5], [4,6], [5,6], [6,9], [7,8], [7,9], [8, 9]. Indicați numărul minim de muchii care trebuie adăugate pentru ca graful obţinut să fie eulerian..
​

Answer 1

Un graf este eulerian dacă are cel puțin un ciclu eulerian, care este un ciclu care trece prin toate muchiile grafului o singură dată. Pentru a determina dacă un graf este eulerian, putem verifica dacă toate nodurile grafului au gradul par.

În cazul dat, graful are nodurile 1, 2, 3, 4, 5, 6, 7, 8, 9 și 10, iar gradul fiecărui nod este următorul:

1. Gradul nodului 1 este 1, deoarece are o singură muchie care îl leagă de nodul 2.
2. Gradul nodului 2 este 3, deoarece are trei muchii care îl leagă de nodurile 1, 3 și 10.
3. Gradul nodului 3 este 2, deoarece are două muchii care îl leagă de nodurile 2 și 10.
4. Gradul nodului 4 este 2, deoarece are două muchii care îl leagă de nodurile 5 și 6.
5. Gradul nodului 5 este 2, deoarece are două muchii care îl leagă de nodurile 4 și 6.
6. Gradul nodului 6 este 3, deoarece are trei muchii care îl leagă de nodurile 4, 5 și 9.
7. Gradul nodului 7 este 2, deoarece are două muchii care îl leagă de nodurile 8 și 9.
8. Gradul nodului 8 este 2, deoarece are două muchii care îl leagă de nodurile 7 și 9.
9. Gradul nodului 9 este 4, deoarece are patru muchii care îl leagă de nodurile 6, 7, 8 și 10.
10. Gradul nodului 10 este 3, deoarece are trei muchii care îl leagă de nodurile 2, 3 și 9.

Observăm că gradul nodurilor 1, 3 și 10 este impar, deci graful nu este eulerian. Pentru a face graful eulerian, trebuie să adăugăm cel puțin trei muchii, astfel încât să creștem gradul nodurilor 1, 3 și 10 la un număr par. De exemplu, putem adăuga muchiile [1,3], [3,9] și [1,9], astfel încât gradul fiecărui nod să fie par. Astfel, graful obținut va fi eulerian și va avea un ciclu eulerian.