Grafo
right|esempio di grafo
Nella matematica moderna, si dice grafo (da non confondere con grafico) una figura costituita da punti, detti vertici o nodi, e da linee che li uniscono, dette lati o spigoli o archi. Più formalmente, dato un insieme A di nodi, un grafo è un sottoinsieme G ⊆ A × A del prodotto cartesiano. I grafi sono oggetto della Teoria dei grafi.
Si distinguono due tipi basilari di grafi, i grafi non orientati e i grafi orientati.
Per grafo non orientato si intende una coppia (V, E), dove V è un insieme finito i cui elementi si dicono vertici ed E è una collezione di singoletti e doppietti di nodi che vengono chiamati spigoli.
Per grafo orientato o grafo diretto o digrafo si intende una coppia (Q, A) dove Q è un insieme finito i cui elementi si dicono nodi ed A ⊆ Q×Q, cioè è una collezione di coppie di nodi dette archi.
Vi sono inoltre varie specie di grafi arricchiti. Si studiano anche grafi con un insieme numerabile di nodi o vertici.
Un caso estremo di grafo è un grafo costituito da un solo nodo, detto grafo nullo.
Tipi di grafi
Implementazioni dei grafi
Ci sono due modi generali per rappresentare un grafo con una struttura di dati utilizzabile da un programma: la lista delle adiacenze e la matrice delle adiacenze. In una lista di adiacenze, una lista mantiene un elenco di nodi, ed ad ogni nodo è collegata una lista di puntatori ai nodi collegati da un arco. In una matrice di adiacenze, una matrice N per N, dove N è il numero dei nodi, mantiene un valore vero in una cella (a,b) se il nodo a è collegato al nodo b. La matrice è simmetrica solo se il grafo non è orientato.
Ognuna delle due rappresentazioni ha alcuni vantaggi: con una lista di adiacenze è facile trovare tutti i nodi adiacenti ad un nodo dato e verificare l'esistenza di connessioni tra nodi; con una matrice di adiacenze è più facile invertire i grafi e individuarne sottografi.