Grafico diretto e non orientato
Un grafo è una struttura matematica composta da un insieme di vertici e bordi. Un grafico rappresenta un insieme di oggetti (rappresentati da vertici) che sono collegati tramite alcuni collegamenti (rappresentati da bordi). 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 archi. In un grafo non orientato non esiste una direzione associata ai bordi che collegano i vertici. In un grafo orientato c'è una direzione associata ai bordi che collegano i vertici.
Grafico non diretto
Come accennato in precedenza, un grafo non orientato è un grafo in cui non c'è alcuna direzione nei bordi che collegano i vertici nel grafo. La Figura 1 mostra un grafo non orientato con un insieme di vertici V = {V1, V2, V3}. L'insieme di archi nel grafico sopra può essere scritto come V = {(V1, V2), (V2, V3), (V1, V3)}. Si può anche notare che nulla impedisce di scrivere l'insieme di 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 i bordi rappresentano le strade a doppio senso che collegano le città.
Grafico diretto
Un grafo orientato è un grafo in cui i bordi 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 di archi nel grafico sopra può essere scritto come V = {(V1, V2), (V2, V3), (V1, V3)}. I bordi in un grafico non orientato sono coppie ordinate. Formalmente, il bordo e in un grafo orientato può essere rappresentato dalla coppia ordinata e = (x, y) dove x è il vertice chiamato origine, sorgente o punto iniziale del bordo e, e il vertice y è chiamato il termine, vertice terminale 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 i bordi orientati rappresentano le strade che collegano le città considerando la direzione che scorre il traffico nella strada.
Qual è la differenza tra Grafico diretto e Grafico non diretto?
In un grafo orientato un bordo è una coppia ordinata, dove la coppia ordinata rappresenta la direzione del bordo che collega i due vertici. D'altra parte, in un grafo non orientato, un arco è una coppia non ordinata, poiché non vi è alcuna direzione associata a un arco. I grafici non orientati possono essere utilizzati per rappresentare relazioni simmetriche tra gli oggetti. In-degree e out-degree 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 grafico non orientato può essere convertito in un grafico orientato sostituendo ciascun bordo con due bordi diretti che vanno nella direzione opposta. Tuttavia, non è possibile convertire un grafico orientato in un grafico non orientato.
