Grafico diretto e non diretto
Un grafo è una struttura matematica composta da un insieme di vertici e spigoli. Un grafico rappresenta un insieme di oggetti (rappresentati da vertici) che sono collegati tramite alcuni collegamenti (rappresentati da spigoli). Usando le notazioni matematiche, un grafo può essere rappresentato da G, dove G=(V, E) e V è l'insieme dei vertici ed E è l'insieme degli spigoli. In un grafo non orientato non c'è direzione associata agli spigoli che collegano i vertici. In un grafo orientato c'è una direzione associata agli archi che collegano i vertici.
Grafico non orientato
Come accennato in precedenza, un grafo non orientato è un grafo in cui non c'è direzione negli archi che collegano i vertici nel grafo. La Figura 1 mostra un grafico non orientato con un insieme di vertici V={V1, V2, V3}. L'insieme degli archi nel grafico sopra può essere scritto come V={(V1, V2), (V2, V3), (V1, V3)}. Si può anche notare che non c'è nulla che impedisca di scrivere l'insieme degli archi come V={(V2, V1), (V3, V2), (V3, V1)} poiché gli archi non hanno una direzione. Pertanto gli archi in un grafo non orientato non sono coppie ordinate. Questa è la caratteristica principale di un grafo non orientato. I grafici non orientati possono essere utilizzati per rappresentare relazioni simmetriche tra oggetti rappresentati da vertici. Ad esempio, una rete stradale a doppio senso che collega un insieme di città può essere rappresentata utilizzando un grafico non orientato. Le città possono essere rappresentate dai vertici nel grafico e gli spigoli rappresentano le strade a doppio senso che collegano le città.
Grafico diretto
Un grafo orientato è un grafo in cui gli archi nel grafo che collegano i vertici hanno una direzione. La Figura 2 mostra un grafo orientato con un insieme di vertici V={V1, V2, V3}. L'insieme degli archi nel grafico sopra può essere scritto come V={(V1, V2), (V2, V3), (V1, V3)}. Gli archi in un grafo non orientato sono coppie ordinate. Formalmente, lo spigolo e in un grafo orientato può essere rappresentato dalla coppia ordinata e=(x, y) dove x è il vertice chiamato origine, sorgente o punto iniziale dello spigolo e, e il vertice y è chiamato capolinea, vertice di terminazione o punto terminale. Ad esempio, una rete stradale che collega un insieme di città utilizzando strade a senso unico può essere rappresentata utilizzando un grafico non orientato. Le città possono essere rappresentate dai vertici nel grafico e gli spigoli diretti rappresentano le strade che collegano le città considerando la direzione in cui scorre il traffico nella strada.
Qual è la differenza tra grafico diretto e grafico non orientato?
In un grafo orientato uno spigolo è una coppia ordinata, dove la coppia ordinata rappresenta la direzione dello spigolo che collega i due vertici. D' altra parte, in un grafo non orientato, un arco è una coppia non ordinata, poiché non esiste una direzione associata a un arco. I grafici non orientati possono essere utilizzati per rappresentare relazioni simmetriche tra oggetti. Il grado di ingresso e quello di uscita di ciascun nodo in un grafo non orientato sono uguali, ma questo non è vero per un grafo orientato. Quando si utilizza una matrice per rappresentare un grafo non orientato, la matrice diventa sempre un grafo simmetrico, ma questo non è vero per un grafo orientato. Un grafo non orientato può essere convertito in un grafo orientato sostituendo ciascun bordo con due archi diretti che vanno in direzione opposta. Tuttavia, non è possibile convertire un grafo orientato in un grafo non orientato.
