Teoria dei grafi
Punti e linee che li uniscono: un grafo non è altro. Eppure lo stesso disegno descrive una mappa stradale, una rete di amici, una molecola e Internet, e le domande che ci si può porre, dal numero di colori che servono alla possibilità di disegnarlo in un solo tratto, tengono occupati i matematici dal 1736.
Vertici e archi
Un grafo ha dei vertici, detti anche nodi, e degli archi, ciascuno dei quali collega due vertici. Non importa dove si disegnano i vertici, ma solo quali coppie sono collegate, quindi lo stesso grafo può apparire molto diverso sulla carta. I grafi del laboratorio sono semplici: nessun arco da un vertice a sé stesso e al massimo un arco tra due vertici. Con n vertici ci possono essere al massimo n(n − 1) / 2 archi; un grafo che li ha tutti si dice completo, e K5 è il grafo completo su cinque vertici.
I gradi e il lemma delle strette di mano
Il grado di un vertice è il numero di archi che vi incidono. Sommando tutti i gradi si ottiene esattamente il doppio del numero di archi, perché ogni arco ha due estremi e viene contato una volta in ciascuno. È il lemma delle strette di mano: in qualsiasi gruppo, le strette di mano contate persona per persona danno in totale il doppio del numero di strette di mano. Ne segue anche che il numero di vertici di grado dispari è sempre pari. Un grafo in cui ogni vertice ha lo stesso grado k si dice k-regolare.
Grafi connessi, alberi e cicli
Un grafo è connesso quando da ogni vertice si può arrivare a ogni altro seguendo gli archi; altrimenti si divide in pezzi, chiamati componenti connesse. Un ciclo è un giro che torna al punto di partenza senza passare due volte per lo stesso vertice, e la lunghezza del più corto si chiama calibro. Un grafo connesso senza cicli è un albero, e un albero con n vertici ha sempre esattamente n − 1 archi: con uno in meno si spezza, con uno in più contiene un ciclo. Ogni grafo connesso contiene un albero ricoprente, cioè un albero che raggiunge ogni vertice usando solo una parte degli archi.
Grafi bipartiti e colorazione
Colora i vertici in modo che nessun arco unisca due vertici dello stesso colore. Il minimo numero di colori con cui ci si riesce è il numero cromatico. Un solo colore basta solo se non ci sono archi. Due colori bastano esattamente quando il grafo è bipartito: i suoi vertici si dividono in due lati e ogni arco passa dall'uno all'altro. Dénes Kőnig dimostrò nel 1936 che questo equivale a non avere cicli di lunghezza dispari, perché in un ciclo dispari due colori non possono alternarsi. Per tre o più colori non si conosce un test altrettanto semplice: decidere se tre colori bastano è NP-completo, perciò i programmi cercano, come fa il laboratorio.
Un esempio: il grafo di Petersen
Prendi un pentagono A–B–C–D–E e, al suo interno, una stella a cinque punte F–H–J–G–I, poi collega ogni vertice del pentagono a una punta della stella: A–F, B–G, C–H, D–I ed E–J. Ecco il grafo di Petersen, con 10 vertici e 15 archi. Ogni vertice ha grado 3, quindi la somma dei gradi è 30, il doppio di 15. Il suo ciclo più corto ha lunghezza 5, quindi non ha triangoli, ma il pentagono è un ciclo dispari, quindi non è bipartito e servono 3 colori. Due vertici qualsiasi distano al massimo 2 archi, quindi il suo diametro è 2. Tutti e dieci i gradi sono dispari, quindi non ha cammini euleriani, e non si può disegnare senza incroci.
I cammini euleriani e i ponti di Königsberg
La città di Königsberg aveva sette ponti che collegavano quattro zone di terra, e ci si chiedeva se fosse possibile attraversare ogni ponte esattamente una volta. Nel 1736 Leonhard Euler dimostrò che non si poteva, e nacque la teoria dei grafi. Ogni volta che una passeggiata attraversa una zona usa due ponti, quindi solo la partenza e l'arrivo possono averne un numero dispari, e invece tutte e quattro le zone di Königsberg ne avevano un numero dispari. Un percorso che usa ogni arco una volta oggi si chiama cammino euleriano, o circuito euleriano quando finisce dove è iniziato. Carl Hierholzer dimostrò nel 1873 che la condizione è anche sufficiente: se tutti gli archi formano un unico pezzo e al massimo due gradi sono dispari, il cammino esiste, e il suo metodo, che unisce tra loro dei giri chiusi, lo trova ancora oggi.
Distanza, diametro e complementare
La distanza tra due vertici è il minimo numero di archi di un cammino che li collega, e il diametro è la massima distanza nel grafo; in un grafo non connesso è infinito. I social network hanno diametri piccoli, l'idea alla base dei sei gradi di separazione. Il complementare di un grafo ha gli stessi vertici e collega esattamente le coppie che non erano collegate. Tra un grafo e il suo complementare, almeno uno è sempre connesso.
Esploralo
Il laboratorio si apre con il grafo di Petersen colorato con tre colori. Fai clic su Gradi e verifica il lemma delle strette di mano, fai clic su Bipartito per vedere un ciclo dispari, poi carica il cubo e guarda comparire i due lati. Carica la casetta e fai clic su Cammino euleriano per vedere da dove deve partire il tratto. Disegna un grafo tutto tuo e aggiungi un arco alla volta: guarda il ciclo più corto accorciarsi, il diametro scendere e il numero cromatico salire quando entra l'ultimo arco di un K4.
Domande frequenti
Qual è la differenza tra passeggiata, traccia e cammino?
Una passeggiata è una qualsiasi sequenza di vertici uniti da archi, e può ripetere sia gli uni sia gli altri. Una traccia può ripetere i vertici ma non gli archi: per questo un cammino euleriano, che in senso stretto è una traccia, può passare più volte per lo stesso vertice. Un cammino non ripete né vertici né archi.
Che cos'è il teorema dei quattro colori?
Afferma che ogni grafo che si può disegnare su un foglio senza incroci tra gli archi si può colorare con al massimo quattro colori, quindi a qualsiasi carta geografica ne bastano quattro. Fu dimostrato nel 1976 da Kenneth Appel e Wolfgang Haken con l'aiuto di un computer, il primo grande teorema dimostrato in questo modo.
Che cos'è un ciclo hamiltoniano?
Un ciclo che visita ogni vertice esattamente una volta, invece di ogni arco. Sembra la domanda di Euler, ma non se ne conosce un test semplice: decidere se un grafo ne ha uno è NP-completo. Il grafo di Petersen ha un cammino hamiltoniano ma nessun ciclo hamiltoniano.
Dove si usa la teoria dei grafi?
I navigatori esplorano grafi stradali, i motori di ricerca ordinano le pagine web in base ai loro link, i compilatori colorano grafi per condividere i registri del processore, gli orari evitano sovrapposizioni colorando un grafo dei conflitti, i chimici contano le molecole come grafi, e le reti di computer, di linee elettriche e di amici si studiano come grafi.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il Laboratorio di teoria dei grafi