Teorema di Eulero per i grafi

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
MindFlyer

Teorema di Eulero per i grafi

Messaggio da MindFlyer » 30 lug 2005, 22:39

Diciamo che un grafo è Euleriano se esiste un cammino nel grafo che percorre ogni arco una ed una sola volta, e termina nel nodo di partenza (vedi anche il thread di Marco sui grafi).

Teorema (Euler, 1736).
Un grafo connesso G è Euleriano se e solo se ogni suo vertice ha grado pari.
Dimostrazione.
Se G è Euleriano, il cammino per G deve toccare tutti i suoi nodi (in quanto percorre tutti i suoi archi, e G è connesso). Se un dato nodo viene toccato k volte, allora da esso partono 2k archi.
Viceversa, se G ha tutti i vertici di grado pari, allora consideriamo il più lungo cammino $ C=n_1n_2\ldots n_k $ che non percorre mai due volte lo stesso arco. Siccome C non può essere esteso dalla parte di $ n_k $, e siccome $ n_k $ ha grado pari, necessariamente dev'essere $ n_1=n_k $. Quindi C è un cammino chiuso. Se per assurdo C non fosse Euleriano, per la connessione di G esisterebbe un arco $ a $ uscente da un vertice di C, tale che C non passa per $ a $. Se $ a $ collega $ n_i $con $ v $, allora il cammino $ vn_i n_{i+1}\ldots n_k n_2\ldots n_i $ non percorre mai due volte lo stesso arco, ed è più lungo di C, contraddicendo la sua massimalità.

Rispondi