Digrafo
Un grafo orientato, o digrafo, è un diagramma composto da punti (chiamati "nodi" o "vertici") e frecce (chiamate "archi") che collegano questi punti.
All'apparenza un digrafo è simile a un grafo ma, in questo caso, le linee che collegano i punti hanno una direzione. Del resto "digrafo" è l'abbreviazione di "grafo diretto".
In un digrafo ogni freccia ha una direzione: parte da un punto e punta verso un altro.
Questo indica che c'è una relazione unidirezionale tra i due punti.
Ad esempio, se hai una freccia che va dal punto A al punto C, puoi dire che c'è un percorso che parte da A e arriva a C, ma non il contrario.
Nel caso particolare di un grafo misto puoi vedere sia linee che non hanno una direzione specifica, sia frecce con una direzione definita.
Questo significa che alcune relazioni tra i punti sono bidirezionali, come nei grafi, e altre unidirezionali.
Se prendi un digrafo e cambi tutte le sue frecce in linee, ottieni un grafo sottostante ( underlying graph ).
Questo processo trasforma tutte le relazioni unidirezionali in relazioni bidirezionali, eliminando la direzione delle relazioni.
Al contrario, se parti da un grafo semplice e sostituisci tutte le sue linee con frecce, crei un nuovo digrafo. Questo nuovo digrafo è chiamato un'orientazione del grafo semplice, perché hai definito una direzione per ogni relazione.