Alberi e grafi planari
Riconosci gli alberi, conta i lati di un albero e di un albero di copertura, e conta le facce di un grafo planare con la formula di Eulero.
📖 Parti da qui: leggi i passi della «Lezione» in ordine (1, 2, 3 …) e rispondi a ogni domanda. Poi continua con «Esercizi».
- Russia: classe 8
Guida
Gli alberi e i grafi sono un argomento di matematica discreta che nelle Indicazioni nazionali compare soprattutto come approfondimento (secondaria di primo grado e biennio del liceo scientifico, in relazione alla teoria dei grafi e ai diagrammi ad albero); non fa parte del programma di base. Un albero è un grafo connesso senza cicli. Proprietà: tra due vertici qualsiasi c'è un solo cammino; un albero con n vertici ha esattamente n − 1 lati; un albero con più di un vertice ha una foglia (un vertice di grado 1). Gli alberi descrivono alberi genealogici, indici di un libro e tornei a eliminazione diretta.
Un albero di copertura di un grafo connesso è una parte che contiene tutti i vertici ed è un albero. Per ottenerlo da un grafo con V vertici e L lati si tolgono L − (V − 1) lati, uno da ogni ciclo.
Un grafo è planare se si può disegnare senza che i lati si incrocino. Per un grafo planare connesso vale la formula di Eulero: V − L + F = 2, dove F è il numero delle facce, compresa quella esterna. Questo è materiale di approfondimento.