Primi elementi della teoria dei grafi

Grafi con direzione

Una strada a senso unico può essere percorsa con un'auto solo in un dato verso, quando ci vestiamo mettiamo prima le calze e poi le scarpe, quando eseguiamo un prelievo a uno sportello automatico dobbiamo prima inserire il bancomat. Situazioni come queste in cui le relazioni sono orientate solo in un dato verso sono molto comuni nella nostra vita quotidiana e per rappresentarle si utilizzano grafi con spigoli orientati mediante una freccia per indicare il verso. Questi tipi di grafi sono detti digrafi o grafi diretti o grafi con direzione e gli spigoli sono detti archi.

Come si vede in un grafo con direzione ogni arco ha un vertice iniziale e un vertice finale pertanto in un vertice entrano o escono degli archi e i vertici hanno quindi un grado in entrata e un grado in uscita. Si può facilmente verificare che in un digrafo la somma dei gradi in entrata di tutti i nodi è uguale alla somma dei loro gradi in uscita.

Un vertice che ha solo archi in uscita è detto sorgente mentre un vertice che ha solo archi in entrata è detto pozzo.

Molti concetti che derivano dai grafi non orientati si possono estendere, con le dovute modifiche ai digrafi. Ad esempio, un digrafo connesso è detto euleriano se contiene un cammino orientato chiuso che include tutti i sui archi oppure ò detto hamiltoniano se contiene un ciclo orientato che passa per ogni suo nodo.

Affinchè un digrafo connesso sia euleriano il grado in entrata deve essere uguale al grado in uscita per ogni nodo. Ovviamente un digrafo non può essere euleriano o hamiltoniano se contiene un nodo sorgente o un nodo pozzo perchè non è possibile raggiungere una sorgente da un altro nodo e non è possibile uscire da un pozzo.