Primi elementi della teoria dei grafi

Grafo ad albero con radice

Se in un grafo ad albero scegliamo arbitrariamente un vertice detto radice e ordiniamo gerarchicamente i restante vertici su differenti livelli a seconda della loro distanza dalla radice otteniamo una struttura ad albero con radice detto grafo ad albero radicato. Ad esempio, consideriamo il seguente grafo ad albero

se scegliamo come radice il vertice 8 la struttura del grafo assumerà la seguente forma

dove i vertici 5 e 3 avendo distanza 1 dal vertice 8 sono posti al livello 1, i vertici 7, 2, 1, 9 e 4 avendo distanza 2 dal vertice 8 sono posti al livello 2, i vertici 10 e 6 avendo distanza 3 dal vertice 8 sono posti al livello 3. Per i grafi ad albero radicato si utilizza la stessa terminologia degli alberi genealogici. Ad esempio, nel grafo precedente il vertice 8 è l'antenato dei restanti vertici ed è il padre dei vertici posti al livello 1 e quindi i vertici 5 e 3 sono i figli del vertice 8. Il vertice 5 è a sua volta il padre dei vertici 7, 2, 1 e quest'ultimi non hanno figli. Il vertice 3 è il padre dei vertici 9 e 4. Il vertice 9 è il padre dei vertici 10 e 6 che a loro volta non hanno figli. Un vertice senza figli è detto foglia. Questi tipi di grafi sono frequentemente utilizzati per rappresentare una classificazione di un insieme di elementi (piante, animali, libri, ecc.) secondo determinate caratteristiche comuni. Ecco ad esempio, una parziale classificazione degli organismi viventi.

Altri esempi dell'utilizzo dei grafi ad albero radicato si trovano in tutte le discipline scientifiche per rappresentare situazioni più varie. Ad esempio, nel calcolo delle probabilità è più semplice analizzare tutte le situazioni possibili di un fenomeno aleatorio e le probabilità dei vari eventi utilizzando un grafo di questo tipo. Se nel lancio di tre monete, si vuole conoscere qual è probabilità che si presentano due croce e una testa si può costruire un grafo dove i vertici rappresentano i risultati del lancio delle monete e gli spigoli rappresentano le relative probabilità.

Come si vede dal grafo i casi possibili sono otto, cioè tutti i possibili cammini che congiungono la radice con le foglie, di questi solo tre casi (o cammini) sono favorevoli alla nostra condizione: due croce e una testa.

e quindi è facile stabilire qual è la probabilità dell'evento: 3 su 8 cioè 0,375.