|
|
Un grafo orientato è una coppia G = (N,A) con N insieme finito di elementi detti nodi o vertici ed A insieme finito di coppie ordinate di nodi, detti archi. I grafi orientati possono essere rappresentati graficamente disegnando ogni nodo con un cerchietto e ogni arco (i,j) con una freccia che esce dal nodo i ed entra del nodo j. Indicando con n il numero di nodi ed m il numero di archi, abbiamo che 0 <= m <= n(n-1) visto che da ogni nodo possono uscire al più n-1 archi. Vediamo di seguito la rappresentazione grafica di un grafo orientato:
Dato un grafo orientato G, un cammino è una sequenza di nodi u0,…,uk tali che:
Se non ci sono nodi ripetuti il cammino è detto semplice. Se u0=uk allora il cammino è detto chiuso. Un cammino semplice e chiuso, con unica ripetizione u0=uk, è detto ciclo.
Un grafo orientato è fortemente connesso se per ogni coppia di nodi u e v, esiste almeno un cammino da u a v ed almeno un cammino da v a u. Per esempio il primo grafo analizzato non è fortemente connesso in quanto esiste il cammino 1->4 ma non da 4->1. Se l’insieme A è composto da coppie non ordinate [i,j], allora si parla di grafo non orientato. Si noti quindi che la coppia di archi “non orientati” [i,j] ed [j,i] individua lo stesso arco mentre la coppia di archi “orientati” (i,j) ed (j,i) individua due archi diversi. Dato un grafo non orientato G, una catena è una sequenza di nodi u0,…,uk tali che:
Se non ci sono nodi ripetuti la catena è detta semplice. Se u0=uk allora la catena è detta chiusa. Una catena semplice e chiusa con gli archi tutti distinti e con unica ripetizione u0=uk, è detta circuito.
Per esempio nel grafo non ordinato, sopra rappresentato, la sequenza 1,2,4,2,3,1 è una catena chiusa, 2,4,3,2 è un circuito e 1,2,1 è una catena chiusa ma non un circuito. Un grafo non orientato è connesso se per ogni coppia di nodi distinti u e v esiste una catena tra u e v. Il grafo sopra indicato è connesso. Un grafo non orientato è detto albero libero (albero in cui non è individuato un nodo come radice) se è connesso e per ogni coppia di nodi esiste una ed una sola catena semplice. Si può quindi affermare che un albero libero è un grafo connesso con minimo numero di archi, cioè n-1, oppure un grafo in cui non esiste un circuito. Quindi il grafo sopra non è un albero libero perché ha 4 nodi e più di 3 archi. Un albero libero avrà per esempio il seguente aspetto:
Nelle specifiche sui grafi, saranno considerati solo grafi orientati visto che possiamo ottenere un grafo non orientato con archi [i,j] come un grafo orientato con archi (i,j) e (j,i). Le operazioni fondamentali sui grafi sono:
creagrafo: restituisce un grafo vuoto , cioè senza nodi e senza archi.
grafovuoto: vernicia se il grafo è vuoto oppure no.
insnodo: aggiunge al grafo un nuovo nodo “isolato”, cioè non collegato a nessun altro nodo.
insarco: aggiunge un nuovo arco tra una coppia di nodi
cancnodo: cancella un nodo isolato.
cancarco: cancella una arco esistente tra una coppia di nodi.
adiacenti: restituisce l’ insieme di tutti i nodi adiacenti ad un certo nodo (insieme A).
La specifica sintattica di queste operazioni è la seguente:
La specifica semantica con post e precondizioni sarà invece:
In molte applicazioni possono essere associate ai nodi e/o agli archi una serie di informazioni aggiuntive, dette etichette o pesi. In tal caso, la specifica data dovrà essere estesa con gli operatori adatti a manipolare tali informazioni. Le due tipologie di grafo introdotte permettono di modellare una vastissima serie di problemi complessi con estrema facilità.. Per saperne di più consulta i seguenti approfondimenti:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.