Matematica · Scuola Superiore · Primo biennio, con possibile approfondimento nel secondo
In breve
Si può attraversare ogni collegamento di una rete una sola volta, senza interrompere il percorso? La risposta dipende dalla connessione della rete e dal numero di vertici con grado dispari. In un grafo connesso con almeno un arco, se i vertici dispari sono zero si può tornare al punto di partenza; se sono due si deve partire da uno e arrivare all’altro; se sono più di due il percorso è impossibile. Impariamo a motivare questo criterio, costruire un itinerario e controllarlo arco per arco.
1. Dalle strade ai grafi
Immagina una piccola rete di vialetti da ispezionare. Vuoi percorrere ogni tratto esattamente una volta: puoi ripassare per un incrocio, ma non per un tratto già controllato. Non stiamo cercando il percorso più corto tra due luoghi, né una visita che tocchi ogni luogo una sola volta. L’obiettivo riguarda tutti i collegamenti, non il numero di visite ai luoghi.
Per rispondere possiamo dimenticare lunghezze, curve e orientamento sulla carta. Sostituiamo ogni incrocio con un punto, chiamato vertice, e ogni collegamento con una linea, chiamata arco. Otteniamo un grafo: non un grafico cartesiano, ma un modello delle connessioni. Se due linee del disegno si incrociano senza un punto segnato, l’incrocio non crea un vertice e non permette di cambiare strada.
In questa lezione usiamo grafi finiti, non orientati, senza cappi e senza archi paralleli: un arco AB collega A e B in entrambi i versi e compare una sola volta nell’elenco. Il disegno può cambiare forma senza cambiare il grafo, purché rimangano gli stessi collegamenti.
La nostra rete di riferimento ha vertici A, B, C, D, E e archi AB, BC, CA, AD, DE, EA. Sono due triangoli che condividono soltanto A. Per ricostruirla non servono misure: basta rispettare l’elenco dei sei archi.
2. Il vocabolario che serve
Il grado di un vertice è il numero di archi che vi arrivano. Nella rete di riferimento A ha grado 4, mentre B, C, D, E hanno grado 2. La somma dei gradi è 4 + 2 + 2 + 2 + 2 = 12: è il doppio dei 6 archi, perché ogni arco ha due estremi.
Questa osservazione vale per tutti i grafi considerati: la somma dei gradi è due volte il numero degli archi. Di conseguenza il numero di vertici di grado dispari è sempre pari. Infatti una somma di interi è pari soltanto se gli addendi dispari sono in numero pari. Non può quindi esserci esattamente un vertice dispari, né esattamente tre.
Un percorso è una successione di vertici collegati, in cui ogni passaggio usa un arco esistente. Nel nostro lessico un percorso generico può ripetere vertici e archi. Un percorso euleriano, invece, usa tutti gli archi del grafo esattamente una volta. Se il punto di arrivo coincide con quello di partenza, si chiama circuito euleriano. Un percorso euleriano può dunque essere aperto oppure chiuso; i vertici possono ripetersi. Altri testi usano “cammino euleriano” o “traccia euleriana”: qui manteniamo la parola “percorso” per evitare ambiguità.
Un grafo è connesso se si può andare da ogni vertice a qualunque altro seguendo archi del grafo. La connettività va controllata prima dei gradi: due reti separate non si possono attraversare con un unico percorso continuo. Le definizioni di connessione e circuito sono approfondite in OpenStax, §12.5, “Connectedness” e “Origin of Euler Circuits” [1].
L’aggettivo euleriano aggiunge dunque un vincolo a un itinerario generico: tutti gli archi, una volta ciascuno. Una componente è una parte connessa massimale del grafo: al suo interno ogni vertice è raggiungibile dagli altri, ma non ci sono collegamenti con il resto. Un arco è incidente a un vertice se lo ha come estremo.
3. Il criterio dei vertici dispari
Teorema. Consideriamo un grafo finito, non orientato, connesso e con almeno un arco.
- Se tutti i gradi sono pari, esiste un circuito euleriano. Si può scegliere come partenza qualsiasi vertice.
- Se ci sono esattamente due vertici dispari, esiste un percorso euleriano aperto, ma non un circuito. I due vertici dispari sono necessariamente gli estremi: si parte da uno e si arriva all’altro.
- Se ci sono più di due vertici dispari, non esiste alcun percorso euleriano.
La connettività non è facoltativa. Se sono presenti vertici isolati, cioè di grado zero, per il solo problema di attraversare gli archi basta che tutti i vertici di grado positivo appartengano a una stessa componente. Operativamente, ignora gli isolati e applica il teorema alla parte che contiene archi: nel caso del circuito puoi partire da qualsiasi vertice di questa parte, non da un isolato. Un punto isolato non contiene archi da attraversare; non richiediamo di visitarlo. Negli esempi connessi della lezione non vi sono vertici isolati.
Il criterio completo per percorso e circuito compare in Oscar Levin, §4.4, riquadro “Euler Paths and Circuits”; l’autore assume esplicitamente grafi connessi nei paragrafi iniziali [2].
Perché le condizioni sono necessarie
Pensa a un vertice che non sia né partenza né arrivo. Ogni volta che vi entri, devi anche uscirne, e devi farlo lungo un arco diverso: non puoi riusare quello appena percorso. Gli archi impiegati lì si accoppiano quindi in entrata e uscita. Se il percorso usa tutti gli archi, il grado del vertice deve essere pari.
In un percorso aperto, alla partenza c’è un’uscita non accoppiata a un ingresso; all’arrivo c’è un ingresso non accoppiato a un’uscita. Anche se torni più volte su questi vertici, tutte le altre visite si accoppiano. Perciò proprio i due estremi hanno grado dispari. In un circuito, invece, anche l’ultima entrata si accoppia con la prima uscita: tutti i gradi sono pari. Questo spiega perché quattro vertici dispari non possano essere gestiti da un unico percorso.
Approfondimento — Perché le condizioni bastano
Supponiamo prima che tutti i gradi siano pari. Parti da un vertice e segui archi non ancora usati finché non puoi proseguire. Non puoi bloccarti in un vertice diverso dalla partenza: lì gli ingressi e le uscite già avvenuti si accoppiano, tranne l’ultimo ingresso. Avresti quindi usato un numero dispari di archi; poiché il grado totale è pari, resterebbe almeno un arco disponibile, in contraddizione con il blocco. Dunque il percorso termina dove è iniziato e forma un circuito.
Se restano archi fuori dal circuito, la connessione assicura che qualche vertice già raggiunto sia incidente a un arco non usato: altrimenti la parte con archi residui sarebbe separata dal circuito. Nel grafo degli archi rimasti i gradi sono ancora pari, perché il circuito precedente ha usato, in ogni vertice, un numero pari di incidenze. Da quel vertice costruisci quindi un nuovo circuito di archi inutilizzati e inseriscilo nel primo. Ripetendo l’operazione, il processo termina: gli archi sono finiti e a ogni passo ne usi di nuovi. Ottieni un circuito che li contiene tutti.
Se i vertici dispari sono due, X e Y, aggiungi provvisoriamente un nuovo vertice Z e gli archi XZ e ZY. Così tutti i gradi diventano pari e il grafo rimane connesso; la costruzione non crea archi paralleli. Trova un circuito euleriano nel nuovo grafo. Poiché Z ha grado 2, i due archi nuovi sono consecutivi nel circuito, considerato ciclicamente. Eliminandoli e tagliando lì il circuito rimane un percorso aperto da X a Y, o viceversa, che usa tutti e soli gli archi originali.
“Considerato ciclicamente” significa che puoi riscrivere lo stesso giro scegliendo un altro punto di partenza: scrivendolo con partenza da Z, i due archi da togliere sono il primo e l’ultimo.
Il metodo di costruzione mediante inserimento di circuiti è descritto anche in OpenStax, §12.5, “Steps to Find an Euler Circuit in an Eulerian Graph”, passi 1–3 [1].
4. Tre esempi svolti
Esempio 1 — Ispezionare due anelli e tornare al deposito
Usiamo la rete di riferimento: AB, BC, CA, AD, DE, EA. Il deposito è A. Il grafo è connesso: da ogni vertice possiamo raggiungere A. I gradi sono A = 4 e B = C = D = E = 2: tutti pari. Esiste dunque un circuito.
Un primo giro è A–B–C–A. Non basta: ha usato soltanto tre archi. Da A possiamo inserire il secondo giro A–D–E–A. Otteniamo A–B–C–A–D–E–A.
Controllo finale: i passaggi sono AB, BC, CA, AD, DE, EA. Sono sei, tutti diversi, ed esauriscono l’elenco. Partenza e arrivo coincidono. Ripetere A non è un errore: il vincolo riguarda gli archi.
Esempio 2 — Una diagonale cambia la possibilità di tornare
Consideriamo un quadrato con una diagonale: AB, BC, CD, DA, AC. È connesso. I gradi sono A = 3, B = 2, C = 3, D = 2. I soli vertici dispari sono A e C.
Esiste un percorso aperto da A a C, per esempio A–B–C–D–A–C. I suoi cinque passaggi sono AB, BC, CD, DA, AC: nessuna ripetizione e nessuna omissione. Non esiste un circuito euleriano. Invertendo l’ordine si ottiene un percorso da C ad A; partire da B, invece, non può funzionare per un percorso che usi ogni arco una volta.
Esempio 3 — L’impossibilità si dimostra senza tentare tutte le strade
Una rete a stella ha archi AB, AC, AD. I gradi sono A = 3 e B = C = D = 1: quattro vertici dispari. Il grafo è connesso, ma non ammette un percorso euleriano. Non occorre provare ogni successione: i quattro dispari richiederebbero quattro estremi, mentre un percorso aperto ne ha soltanto due. Anche se un tentativo attraversa due rami, il terzo non può essere incluso senza ripetere un arco.
5. Come lavorare senza perdere un arco
Per risolvere un esercizio, scrivi l’elenco completo degli archi e verifica che la rete non abbia parti separate con archi. Conta poi i gradi, usando la somma dei gradi come controllo, e identifica i vertici dispari. Soltanto a questo punto scegli una partenza compatibile e costruisci il percorso. Infine riscrivi ogni passaggio come arco non orientato: AB e BA sono lo stesso arco.
Il criterio garantisce che una soluzione esista, non che ogni scelta casuale la trovi senza ripensamenti. Nella rete dell’esempio 1, fermarsi dopo A–B–C–A dà un circuito, ma non un circuito euleriano: manca l’altro triangolo. Occorre inserire il giro rimanente, non dichiarare che il teorema è falso.
Un percorso che usa tutti gli archi esattamente una volta ha tanti passaggi quanti sono gli archi, quindi nella sua scrittura compaiono un vertice in più rispetto ai passaggi. Questo controllo di lunghezza è necessario, ma non sufficiente: un elenco della lunghezza giusta può comunque ripetere un arco e ometterne un altro.
6. Esercizi
Tutti gli archi sono non orientati. I vertici sono esattamente le lettere che compaiono negli elenchi. Non si possono compiere salti tra vertici non collegati.
1. Un primo circuito. Gli archi sono PQ, QR, RP. Calcola i gradi, verifica la connessione e scrivi un circuito euleriano. Quanti passaggi contiene?
2. Da dove partire? Gli archi sono AB, BC, CD, DE, EA, BD. Stabilisci se esiste un percorso aperto o un circuito, indica gli estremi necessari e scrivi una soluzione.
3. Una falsa scorciatoia. Per la rete AB, AC, AD uno studente propone B–A–C–A–D. Perché non è un percorso euleriano? Spiega anche perché nessun altro tentativo può riuscire.
4. Tutti pari: basta? Gli archi sono AB, BC, CA, DE, EF, FD. Tutti i gradi sono pari. Esiste un circuito euleriano che attraversi tutti e sei gli archi? Motiva la risposta senza aggiungere collegamenti.
5. Il controllo delle omissioni. Per la rete AB, BC, CA, AD, DE, EA viene proposto A–B–C–A. Spiega perché non è una soluzione completa e correggila inserendo gli archi mancanti.
6. Aggiungere un collegamento. Alla rete dell’esercizio 5 aggiungiamo BD. Calcola i nuovi gradi e trova un percorso euleriano. È ancora possibile tornare al punto di partenza usando ogni arco una volta?
7. Una partenza diversa. Nella rete dell’esercizio 5, senza BD, si può partire da B e terminare in B? Se sì, scrivi un circuito e verifica tutti i passaggi.
8. Sfida facoltativa — Modificare una rete. Un grafo ha tutti i collegamenti tra quattro vertici: AB, AC, AD, BC, BD, CD. (a) Perché non ha un percorso euleriano? (b) Elimina il minor numero possibile di archi per ottenere un percorso euleriano aperto: indica una scelta e una soluzione. (c) Elimina il minor numero possibile di archi per ottenere un grafo connesso, sugli stessi quattro vertici, con circuito euleriano. Giustifica la minimalità in entrambi i casi.
7. Soluzioni commentate
1. Un primo circuito
I tre vertici hanno tutti grado 2; il grafo è connesso perché ciascuno è collegato agli altri due. Un circuito è P–Q–R–P. Usa PQ, QR, RP e contiene 3 passaggi. La somma dei gradi è 6, il doppio dei 3 archi.
2. Da dove partire?
I gradi sono A = 2, B = 3, C = 2, D = 3, E = 2; la somma è 12, coerente con 6 archi. Il grafo è connesso grazie al ciclo A–B–C–D–E–A. I due dispari sono B e D: esiste soltanto un percorso euleriano aperto tra questi estremi. Una soluzione è B–A–E–D–C–B–D. Gli archi percorsi sono BA, AE, ED, DC, CB, BD: corrispondono, una volta ciascuno, ai sei dell’elenco. Nessun circuito può esistere perché B e D sono dispari.
3. Una falsa scorciatoia
La successione proposta usa BA, AC, CA, AD: AC e CA sono lo stesso arco, percorso due volte. La rete ha soltanto 3 archi, mentre il tentativo fa 4 passaggi. Soprattutto, i gradi sono 3, 1, 1, 1: quattro vertici dispari. Questo impedisce ogni percorso euleriano, indipendentemente dall’ordine scelto.
4. Tutti pari: basta?
No. ABC e DEF sono due componenti separate, ciascuna un triangolo con tre archi. Ogni vertice ha grado 2, ma non c’è alcun percorso da un vertice della prima componente a uno della seconda. Ognuna ammette un circuito proprio; non esiste un solo circuito continuo che copra tutti i sei archi. Manca l’ipotesi di connessione.
5. Il controllo delle omissioni
A–B–C–A usa soltanto AB, BC, CA: mancano AD, DE, EA. Inseriamo in A il giro A–D–E–A e otteniamo A–B–C–A–D–E–A. I sei passaggi esauriscono l’elenco e tornano ad A. La ripetizione del vertice A è consentita.
6. Aggiungere un collegamento
Il nuovo arco BD aumenta di uno il grado di B e quello di D. I gradi diventano A = 4, B = 3, C = 2, D = 3, E = 2, con somma 14 per 7 archi. Il grafo resta connesso; i dispari sono B e D. Una soluzione è B–C–A–B–D–E–A–D: gli archi sono BC, CA, AB, BD, DE, EA, AD. Esiste quindi un percorso aperto, ma nessun circuito euleriano. Aggiungere un collegamento non rende automaticamente possibile il ritorno: qui lo impedisce.
7. Una partenza diversa
Sì: nella rete originale tutti i gradi sono pari e B non è isolato. Un circuito è B–C–A–D–E–A–B. I sei passaggi sono BC, CA, AD, DE, EA, AB: tutti e soli gli archi richiesti. Per un circuito euleriano la partenza non è obbligata ad A, anche se A è il vertice di grado maggiore.
8. Modificare una rete
(a) Tutti e quattro i vertici hanno grado 3, quindi ci sono quattro dispari: nessun percorso euleriano.
(b) Eliminiamo AB. Ora A e B hanno grado 2, C e D grado 3; il grafo resta connesso. Il percorso C–A–D–B–C–D usa CA, AD, DB, BC, CD, cioè tutti i 5 archi rimasti. Una rimozione è minima: con zero rimozioni restavano quattro dispari e il percorso era impossibile.
(c) Eliminiamo AB e CD. Rimangono AC, AD, BC, BD, che formano il circuito A–C–B–D–A. Tutti i gradi sono 2 e il grafo è connesso. Due rimozioni sono minime: nessuna rimozione lascia quattro dispari; una sola rimozione cambia la parità soltanto dei suoi due estremi, lasciando gli altri due vertici dispari. Non potrebbe quindi produrre un circuito euleriano. La scelta degli archi conta: rimuovere due archi con un estremo comune non avrebbe lo stesso effetto.
8. Da ricordare
Prima verifica la connessione, poi conta i dispari, infine controlla ogni arco del percorso. Zero dispari: circuito; due dispari: percorso aperto tra loro; più di due: impossibile, sempre sotto l’ipotesi di connessione della parte con archi. Ripetere un vertice è ammesso; ripetere un arco no. Il test stabilisce l’esistenza, ma una risposta completa deve anche rispettare l’elenco dei collegamenti.
Fonti per approfondire
[1] OpenStax, Contemporary Mathematics, §12.5 “Euler Circuits”. Locatori: “Connectedness” per la connessione; “Origin of Euler Circuits” per l’argomento dei gradi pari; “Steps to Find an Euler Circuit in an Eulerian Graph”, passi 1–3, per l’inserimento di circuiti; Example 12.27 “Finding an Euler Circuit”, soluzione, per il procedimento costruttivo. Leggi la fonte.
[2] Oscar Levin, Discrete Mathematics: An Open Introduction, 2ª edizione, §4.4 “Euler Paths and Circuits”. Locatori: paragrafi iniziali che assumono grafi connessi; paragrafi “You run into a similar problem whenever…” e “What all this says is…” per l’accoppiamento entrata/uscita; riquadro “Euler Paths and Circuits” per il criterio zero/due dispari; paragrafo “The converse is also true…” per l’inserimento di circuiti. Leggi la fonte.
L’esposizione, le reti degli esempi e la sequenza degli esercizi sono state redatte per questa lezione; non riproducono figure o testi delle fonti. Revisione docente e sperimentazione in classe restano aperte.
Scarica la lezione completa, gli esercizi e le soluzioni (PDF)
Revisione docente: APERTA. Prova in classe: APERTA.