Definizione di grafo in informatica
Il termine grafo in informatica viene usato per indicare una particolare figura geometrica, costituita da un insieme finito di punti, detti nodi (oppure vertici), e da segmenti o archi, detti lati (o spigoli o anche archi), che congiungono coppie di nodi.
Possiamo subito fare le seguenti considerazioni:
- possiamo supporre, ad esempio, che ciascun nodo del grafo sia il supporto di un dato o di un intero record e possiamo inoltre supporre che ciascun lato dello stesso grafo sia la rappresentazione di una relazione esistente tra i dati contenuti nei nodi che si trovano alle estremità del lato stesso;
- allora, visto in quest’ottica, un grafo può tranquillamente essere visto come la rappresentazione di una particolare struttura astratta di dati.
Sia dato quindi un grafo qualsiasi, con un numero qualsiasi (purché ovviamente finito) di nodi e di lati. Vediamo adesso qualche definizione:
- due nodi del grafo si diranno adiacenti se esiste un lato che li congiunge;
- una successione di nodi sarà perciò costituita da un certo numero di nodi adiacenti a due a due collegati tra loro; in particolare, se la successione data non contiene due volte lo stesso lato, allora si parla di cammino;
- a sua volta un cammino può essere di vari tipi: si parla di cammino semplice se contiene tutti nodi distinti fatta eccezione, al più, per il primo e l’ultimo nodo che potrebbero anche coincidere; inoltre, un cammino che congiunge un nodo con se stesso si dice cammino ciclico. In particolare, un cammino ciclico che è anche semplice viene brevemente chiamato ciclo (oppure circuito);
- un particolare tipo di grafo è il cosiddetto grafo connesso: se, dato un grafo qualsiasi e presi due qualsiasi suoi punti, è sempre possibile congiungere tali nodi mediante un cammino, allora il grafo si definisce appunto connesso.
E’ possibile che ogni lato di un grafo sia dotato di un orientamento, ossia di un “qualcosa” che precisa la relazione logica che intercorre tra i dati contenuti nei due nodi congiunti dal lato stesso. Allora, se i lati di un grafo sono tutti orientati, si parla di grafo orientato: in questo caso, i lati vengono graficamente rappresentati mediante un arco che termina con una freccia.
Per i grafi orientati, così come per i grafi normali, si definiscono le nozioni di cammino orientato (successione di nodi adiacenti contenente ogni lato 1 sola volta) e di cammino ciclico orientato (cammino orientato che congiunge un nodo con se stesso). Si veda infine la figura esempio per avere un’idea più chiara del grafo (grafo informatica).