Connessione, cammini, cicli e disegni senza staccare la penna
Conta le componenti connesse, trova i vertici di grado dispari e decidi se un grafo si può tracciare senza staccare la penna.
📖 Parti da qui: leggi i passi della «Lezione» in ordine (1, 2, 3 …) e rispondi a ogni domanda. Poi continua con «Esercizi».
- Russia: classe 7
Guida
I grafi non sono nei programmi italiani del primo ciclo né dei licei: questo percorso è un ampliamento, che si incontra nei giochi matematici e nella matematica discreta. Dopo vertici, lati e grado arrivano: il cammino (ogni lato inizia dove finisce il precedente), il ciclo (un cammino che torna al punto di partenza) e la connessione (due vertici qualsiasi sono uniti da un cammino). Ogni grafo si divide in componenti connesse.
Un cammino euleriano usa ogni lato esattamente una volta. Esiste quando il grafo è connesso e ha zero oppure due vertici di grado dispari. Con zero esiste un percorso chiuso (ciclo euleriano); con due, il cammino parte da uno e finisce nell'altro. Questo risolve il problema dei ponti di Königsberg (quattro vertici dispari) e la domanda «si può disegnare la figura senza staccare la penna?».
Errori frequenti: non contare un vertice isolato come componente; contare i vertici invece dei lati per il grado; pensare che ogni figura si possa disegnare con un solo tratto.