Cammini e cicli Euleriani e Hamiltoniani

Eulero ha definito formalmente per la prima volta il grafo.

Circuito euleriano: circuito che passa una volta per tutti gli archi del grafo

Trail eulerino: è conosciuto com percorso euleriano

Sette ponti di Konigsberg: è un problema

Partendo da un’arco devo poter, passando per tutti gli archi, tornare a quello iniziale.

Eulero per risolvere questo problema ha creato il teorema di eulero.

4 nodi tutti uguali con grado dispari:

• non esiste trail euleriano
• cammino euleriano

Teorema di Eulero

solo se punti 1 e 2 (sono rispettati)

Dimostrazione:

1. percorriamo il circuito, ogni volta che passiamo per un nodo, consumiamo 2 archi il circuito NON PASSA mai 2 VOLTE per lo stesso nodo.