← OlimpiApp
Difficile
Informatica · Grafi
Archi minimi per un circuito Euleriano (6 nodi)
Un grafo non orientato e connesso ha 6 nodi (0..5) e archi: 0—1; 0—2; 0—3; 1—2; 3—4; 4—5. Un circuito che percorre ogni arco esattamente una volta e torna al punto di partenza esiste solo se ogni nodo ha grado pari. Qual è il numero minimo di archi da aggiungere (anche fra nodi già collegati) perché il grafo ammetta un tale circuito?