Grafi orientati e problemi risolti con i grafi
Leggi i grafi orientati, conta le strette di mano e le partite di un torneo e trova il percorso più breve trasformando il problema in un grafo.
📖 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 fanno parte dei programmi italiani di matematica del primo ciclo né del liceo: questo percorso è un ampliamento, utile per i giochi logici e le gare matematiche. Un grafo è un modello comodo: i vertici sono persone, città o squadre e i lati sono relazioni (amicizia, strade, partite). Se la relazione ha un verso («A ha superato B») il lato si disegna con una freccia: è un grafo orientato. Da un vertice partono alcune frecce e ne arrivano altre.
Problemi classici: le strette di mano in un gruppo di n persone (ognuno con ognuno una volta sola), le partite di un girone all'italiana (ogni squadra gioca contro tutte le altre). La somma dei gradi è il doppio del numero dei lati, quindi i lati sono la metà della somma dei gradi; con n vertici tutti collegati otteniamo n·(n − 1) : 2.
Un errore frequente è contare ogni lato due volte. Un altro è confondere le frecce uscenti con quelle entranti. Un problema di percorso si risolve contando i lati della catena più breve.