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à.
Teorema di Eulero per i grafi
Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Torna a “Glossario e teoria di base”
Vai a
- Getting Started
- ↳ Comitato di accoglienza nuovi utenti
- ↳ Ciao a tutti, mi presento:
- ↳ Glossario e teoria di base
- Problem solving olimpico
- ↳ Algebra
- ↳ Combinatoria
- ↳ Geometria
- ↳ Teoria dei Numeri
- Altri esercizi
- ↳ Matematica ricreativa
- ↳ Matematica non elementare
- ↳ Fisica
- ↳ Informatica
- Supporto tecnico
- ↳ Il sito delle olimpiadi della matematica
- ↳ LaTeX, questo sconosciuto
- Gare e concorsi
- ↳ Olimpiadi della matematica
- ↳ Gara a squadre
- ↳ Giornalino del gruppo tutor
- ↳ Altre gare
- ↳ Scuole d'eccellenza e borse di studio
- Tra un problema e l'altro...
- ↳ Cultura matematica e scientifica
- ↳ Il colmo per un matematico
- ↳ Discorsi da birreria
- I messaggi del vecchio forum (memoria storica di sola lettura)
- ↳ [vecchio forum]Le olimpiadi della matematica
- ↳ [vecchio forum]Come vedo il sito delle Olimpiadi della Matematica
- ↳ [vecchio forum]Giornalino della Matematica
- ↳ [vecchio forum]Gruppo Tutor
- ↳ [vecchio forum]Proponi gli esercizi
- ↳ [vecchio forum]Compro, baratto, vendo, rido!
- ↳ [vecchio forum]Cesenatico
- ↳ [vecchio forum]Sondaggi, che passione!
- ↳ [vecchio forum]Proposte ai Responsabili Provinciali
- ↳ [vecchio forum]Tra responsabili
- ↳ [vecchio forum]Non solo Matematica!