Primi elementi della teoria dei grafi

Circuito euleriano

Un grafo è stato utilizzato per la prima volta, in modo consapevole, dal matematico svizzero Eulero (1707-1783) nel 1736 per risolvere un enigma noto come problema dei sette ponti di Konigberg. All'epoca di Eulero la città di Konigberg (l'attuale kalingrado) era divisa, dal fiume Pregel e dai suoi affluenti, in quattro zone collegate da sette ponti. In figura le quattro zone sono indicate con le lettere A, B, C, D e i sette ponti con le lettere a, b, c, d, e, f, g.

Da tempo i cittadini di Konigberg si chiedevono se era possibile con una passeggiata partire da una qualsiasi delle quattro zone della città attraversare ciascun ponte una e una sola volta e tornare al punto di partenza. Molti tentarono di risolvere il quesito percorrendo i sette ponti in tutti i modi possibili ma nessuno riuscí nell'impresa. Si iniziò a dubitare la fattibilità di un tale percorso ma nessuno era in grado di darne una giustificazione logica. Eulero venuto a conoscenza del quesito dimostrò che effettivamente la passeggiata non era possibile. Nella sua dimostrazione indicò con un punto ogni zona della città e con uno spigolo un collegamento tra due zone passando per un solo ponte.

Ottenne cosí una semplice rappresentazione geometrica che riassume in sè tutte le informazioni essenziali del problema cioè, un grafo.

Il problema dei sette ponti divenne cosí equivalente al problema se parto da uno dei quattro punti è possibile eseguire un circuito passando per ogni spigolo una volta sola? I vertici possono essere ripercorsi, gli spigoli no. Eulero fece il seguente ragionamento: all'inizio se parto da un dato punto devo prima "uscire" e poi "entrare" invece, dopo per ogni punto devo prima entrare e poi uscire pertanto il numero degli spigoli che si dipartono da ogni punto deve essere pari perchè si suddividono in coppie uscita-entrata e entrata-uscita.

Ora, il grafo tracciato da Eulero ha tutti i vertici di grado dispari e quindi non è possibile eseguire un circuito che passa per tutti gli spigoli una sola volta. In generale:

un grafo possiede un circuito che attraversa tutti gli spigoli senza interruzione e senza ripetizione, se e solo se è connesso e tutti i vertici hanno grado pari.

Un cammino che soddisfa queste condizioni è detto circuito euleriano in onore a Eulero e un grafo che abbia un circuito euleriano è detto grafo di Eulero.

In altre parole, un circuito è euleriano se:

• tutti gli archi del grafo sono percorsi senza ripetizioni;
• è un ciclo chiuso, quindi inizia e termina nello stesso vertice;
• nel cammino si possono ripetere i vertici, ma non si possono ripetere gli archi.

Queste tre proprietà permettono di analizzare la percorribilità completa di una rete senza passare due volte dallo stesso collegamento.

Se un grafo è connesso e ha esattamente solo due vertici dispari, allora è possibile effettuare un cammino euleriano non chiuso che attraversa tutti gli spigoli una sola volta, ma deve necessariamente iniziare da uno dei due vertici di grado dispari e terminare nell'altro.

E se il grafo ha 2n vertici dispari (ricordiamoci che in un grafo il numero dei vertici dispari è sempre pari) qual è minimo numero di cammini necessari per attraversare tutti gli spigoli una e una sola volta? Ad esempio, in figura il primo grafo ha quattro spigoli dispari e il secondo grafo ha otto spigoli dispari; qual è il più piccolo numero di cammini che permette di attraversare ciascun grafo?

Nel primo occorrono due cammini e nel secondo quattro cammini.

In generale:

se un grafo ha 2n vertici dispari allora il minimo numero di cammini necessari per attraversare tutti gli spigoli una e una sola volta è 2n:2=n.

Da queste considerazioni emerge che un grafo completo k_n, che è regolare di grado n-1, è un grafo euleriano solo se n è dispari.

I circuiti euleriani trovano applicazione in diversi contesti pratici:

• pianificazione di percorsi: come nei servizi di pulizia stradale o raccolta rifiuti, dove si vuole percorrere ogni strada una sola volta;

• ispezione di reti: controllo di linee elettriche, tubature o infrastrutture;
• problemi di routing (instradamento): ottimizzazione dei percorsi in reti informatiche;
• puzzle e giochi logici: come il classico problema dei ponti di Königsberg.

Questi esempi mostrano come un concetto matematico possa modellare problemi reali di efficienza e ottimizzazione.