Definizione di Grafo in informatica

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).

Definizione di grafo in informatica
grafo informatica

 

Pubblicato da Vito Lavecchia

Lavecchia Vito Ingegnere Informatico (Politecnico di Bari) Email: [email protected] Sito Web: https://vitolavecchia.altervista.org

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *