-
Regolare
-
Completo
Laboratorio di teoria dei grafi
Un grafo è un insieme di punti, chiamati vertici, uniti da linee, chiamate archi. Disegnane uno qui con pochi clic e il laboratorio ti dice che tipo di grafo è: in quanti pezzi è diviso, se è un albero, quanti colori gli bastano, se si può disegnare in un solo tratto e altro ancora. Fai clic su una proprietà per vederla sul tuo grafo, cambia un arco e guarda come cambiano le risposte. Fai clic su un punto vuoto per aggiungere un vertice. Fai clic su un vertice e poi su un altro per collegarli con un arco; ripeti per togliere l'arco. Trascina un vertice per spostarlo. Passa il clic su Cancella e fai clic su un vertice o su un arco per eliminarlo. Con un vertice selezionato, Canc lo elimina ed Esc lo deseleziona. Fai clic su una proprietà per vederla sul grafo. Esempio carica un grafo famoso, Grafo casuale ne crea uno, Riordina distribuisce i vertici e Complementare collega esattamente le coppie che non erano collegate. Ctrl+Z annulla un passo.
Come funziona
- Fai clic su un punto vuoto per aggiungere un vertice. Fai clic su un vertice e poi su un altro per collegarli; ripeti per togliere l'arco. Trascina un vertice per spostarlo.
- Leggi le proprietà sotto il grafo e fai clic su una per mostrarla: una colorazione, i due lati, un cammino euleriano, un albero ricoprente, il ciclo più corto o il diametro.
- Carica un esempio come il grafo di Petersen, crea un grafo casuale, prendi il complementare, oppure passa il clic su Cancella per eliminare vertici e archi.
Che cosa significano le proprietà
Il grado di un vertice è il numero di archi che vi incidono. Un grafo è connesso quando ogni vertice può raggiungere ogni altro seguendo gli archi, ed è un albero quando è connesso e non ha cicli. È bipartito quando i suoi vertici si dividono in due lati e ogni arco passa da un lato all'altro, cosa che accade esattamente quando non ha cicli di lunghezza dispari. Il numero cromatico è il minimo numero di colori che permette di dare colori diversi ai vertici adiacenti. La lunghezza del ciclo più corto si chiama calibro, e il diametro è la massima distanza tra due vertici, contata in archi.
Disegnare in un solo tratto
Un cammino euleriano usa ogni arco esattamente una volta. Nel 1736, con i sette ponti di Königsberg, Leonhard Euler capì qual è l'ostacolo: ogni volta che un cammino passa per un vertice, ne usa due archi. Quindi o tutti i gradi sono pari, e il cammino può finire dove è iniziato, oppure esattamente due gradi sono dispari, e il cammino deve andare da uno di quei vertici all'altro. Carl Hierholzer dimostrò in seguito che questa condizione, con tutti gli archi in un unico pezzo, è anche sufficiente. Carica l'esempio della casetta e scopri da dove deve partire il tratto.
Domande frequenti
Che cos'è un grafo nella teoria dei grafi?
Un insieme di punti, chiamati vertici o nodi, e di linee tra alcune coppie di essi, chiamate archi. Non è il grafico di una funzione: descrive soltanto che cosa è collegato a che cosa. Le mappe stradali, i social network, le molecole e le reti di computer sono tutti grafi.
Come si calcola il numero cromatico?
Il laboratorio prova a colorare il grafo con un colore, poi con due, poi con tre e così via, e per ogni numero esamina tutti i modi che contano, colorando sempre per primo il vertice i cui vicini usano già più colori. Il primo numero che funziona è il numero cromatico. Per i grafi che puoi disegnare qui basta al massimo un attimo; su un grafo molto difficile la ricerca si ferma prima e il valore viene mostrato come limite superiore.
Quando un grafo ha un cammino euleriano?
Quando tutti i suoi archi formano un unico pezzo e non più di due vertici hanno grado dispari. Senza vertici dispari c'è un circuito euleriano che finisce dove inizia; con due, ogni cammino euleriano parte da uno di essi e arriva all'altro. Il numero di vertici dispari è sempre pari, quindi non è mai esattamente uno.
Che cos'è il complementare di un grafo?
Il grafo sugli stessi vertici i cui archi sono esattamente le coppie che prima non erano collegate. Il complementare del complementare è il grafo di partenza. Il complementare del grafo di Petersen, per esempio, è 6-regolare, perché ogni vertice era collegato a 3 degli altri 9.
Perché il grafo di Petersen è famoso?
È un piccolo grafo con 10 vertici e 15 archi che fa da controesempio a molte congetture ottimistiche. Ogni vertice ha grado 3, il suo ciclo più corto ha lunghezza 5, due vertici qualsiasi distano al massimo 2 archi, e non si può disegnare senza che degli archi si incrocino. Il laboratorio parte proprio da lui.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor