I digrafi

Un digrafo è un grafo orientato. E' composto da N nodi e A archi. $$ D=(N,A) $$

Ecco un esempio pratico di digrafo.

Qual è la differenza tra grafo e digrafo? Nel digrafo i vertici (nodi) sono collegati tra loro da archi orientati con una direzione e un verso. Nel grafo semplice, invece, gli archi non hanno un verso.

Ogni arco a_k è indicato nel seguente modo:

$$ a_k=(i,j) $$

Dove k è il numero indice che individua l'arco nel grafo in modo univoco.

I parametri i e j sono invece gli estremi dell'arco, rispettivamente il nodo di origine (i) e di destinazione (j).

Pertanto, il k-esimo arco del grafo è sia uscente dal nodo i e sia entrante nel nodo nodo j.

Nota. La coppia (a,b) che indica un arco è una coppia orientata. Quindi, le coppie (a,b) e (b,a) indicano archi diversi con gli stessi estremi ma verso opposto.

Differenza tra cammino e percorso

I termini cammino ottimale e percorso ottimale non sono sinonimi.

• Il cammino dal nodo di origine al nodo di destinazione è una sequenza di nodi adiacenti senza nodi ripetuti.
  

  Nota. Se soltanto il nodo di origine e di destinazione coincidono, il cammino è detto ciclo orientato. In caso contrario è detto aciclico.

• Il percorso dal nodo di origine al nodo di destinazione è una sequenza di nodi adiacenti con alcuni nodi ripetuti.
  

  Nota. Se il nodo di origine e di destinazione coincidono, il percorso è detto circuito orientato.

In entrambi i casi si parla di lunghezza ( o cardinalità ) per intendere il numero degli archi nella sequenza.

Si parla di distanza per intendere il numero di nodi nella sequenza.

Il cammino o percorso ottimale da un nodo a un altro, è quello con il costo più basso.

Esistono diversi algoritmi per cercare il cammino ottimale in un digrafo.