Primi elementi della teoria dei grafi

Grafi e numeri

Un grafo semplice può essere definito anche con dei numeri tramite una tabella a doppia entrata detta matrice. La matrice contenente, sotto forma di numeri, le relazioni presenti in un grafo può essere facilmente memorizzata su un computer e quindi i problemi sui grafi possono essere risolti con gli strumenti informatici utilizzando appositi programmi. Possiamo descrivere un grafo con due tipi di matrici:

• Matrice di adiacenza.

  Con questa tabella si mettono in evidenza le relazioni di adiacenza tra i vertici inserendo 1 per indicare se sono adiacenti e 0 se non sono adiacenti. Se un grafo ha n vertici la matrice di adiacenza avrà n righe e n colonne, dove ogni riga ed ogni colonna corrisponde ai vertici del grafo.

  

  La matrice di adiacenzaè simmetrica rispetto alla diagonale principale.

  

  Naturalmente, è possibile descrivere anche un grafo orientato con una matrice di adiacenza che però non è simmetrica rispetto alla diagonale principale.

  

  Osservate che nella matrice di adiacenza di un grafo orientato si possono individuare sia i vertici sorgente che i vertici pozzo. Ai vertici sorgente corrisponde una colonna costituita da tutti zeri, e ai vertici pozzo corrisponde a una riga costituita da tutti zeri.

• Matrice di incidenza.

  Con questa tabella si mettono in evidenza le relazioni di incidenza tra gli spigoli e i vertici inserendo 1 per indicare se sono incidenti e 0 se non sono incidenti. Se un grafo ha n vertici e m spigoli la matrice di adiacenza avrà n righe e m colonne, dove ogni riga è associata a un vertice e ogni colonna è associata a uno spigolo del grafo.

  

Possiamo esprimere anche un grafo orientato con una matrice di incidenza inserendo +1 se l'arco ha verso uscente dal vertice, -1 se l'arco ha verso entrante dal vertice e 0 se l'arco non è incidente nel vertice.