Primi elementi della teoria dei grafi

Il problema del postino cinese

Un circuito euleriano è la soluzione ideale per i problemi relativi alla pianificazione di un itinerario. Pensate quanto potrebbe risparmiare una società addetta alla raccolta differenziata o alla pulizia delle strade di una città o alla distribuzione della posta se potesse eseguire il lavoro percorrendo tutte le strade una sola volta evitando cosí giri inutili. Un esempio classico è quello del postino che deve effettuare la consegnare delle lettere in una data zona della città percorrendo tutte le strade di sua competenza dovendo partire e tornare alla fine del lavoro nella sede dell'ufficio postale. Come può l'ufficio postale pianificare il lavoro del postino evitandogli di ripercorrere più volte la stessa strada? Potrebbe costruire il grafo della zona mettendo un vertice a ogni incrocio e uno spigolo per il tratto di strada che unisce due incroci adiacenti.

Molto probabilmente il grafo cosí costruito non avrà tutti i vertici di grado pari e quindi non esisterà un circuito euleriano. Possono, però, porsi il problema: è possibile ripetere alcune strade cercando di ridurre al minimo le strade da ripercorrere, affinchè ci sia un circuito euleriano? Questo problema fu risolto per la prima volta dal matematico cinese Meigu Guan nel 1962 ed è noto con il nome: il problema del postino cinese. Vediamo in che modo un problema di questo tipo può essere risolto ragionando su dei grafi.

Se un grafo è connesso e ha solo due vertici con grado dispari, allora è possibile effettuare un percorso 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. Ad esempio, nel grafo in figura si può effettuare un percorso non chiuso che attraversa tutti gli spigoli una sola volta solo se si parte o dal vertice D oppure dal vertice B (in figura si parte dal vertice D e si finisce nel vertice B).

Se i due vertici dispari sono adiacenti si può pensare di introdurre una fittizia connessione tra i due vertici dispari disegnando uno spigolo tratteggiato in questo modo tutti i vertici avranno grado pari e quindi esisterà sicuramente un circuito euleriano. Ogni volta che aggiungiamo al grafo uno spigolo aumenta di 1 il grado dei due vertici adiacenti allo spigolo aggiunto. Ora, essendo il grafo euleriano si può partire e ritornare al vertice di partenza. Nella situazione reale del postino, se il grafo rappresenta la mappa stradale e la sede dell'ufficio postale corrisponde al vertice A il percorso ideale prevederà di passare due volte per la strada che nel grafo corrisponde allo spigolo DB.

Ma se i due vertici di grado dispari non sono adiacenti oppure ci sono più di due vertici di grado dispari come bisogna procedere? Ricordiamo che se in un grafo ci sono spigoli di grado dispari questi sono presenti sempre in un numero pari. In questo caso è necessario aggiungere il numero minimo di connessioni fittizie in modo da duplicare alcuni spigoli per rendere tutti i vertici di grado pari e ottenere cosí un circuito euleriano. Ad esempio, il seguente grafo ha due vertici B e F dispari non adiacenti.

Sapendo che il grafo rappresenta una mappa stradale non possiamo connettere direttamente con uno spigolo i vertici B e F (non possiamo costruire una nuova strada apposta per il postino) bisogna allora connettere anche quei vertici che sono lungo il percorso più breve che permette di passare da B a F. Ad esempio, inserendo i due spigoli fittizi BG e FG tutti i vertici avranno grado pari e quindi esisterà un circuito euleriano. Nella situazione reale del postino, se il grafo rappresenta la mappa stradale e la sede dell'ufficio postale corrisponde al vertice A il percorso ideale prevederà che le due strade BG e FG siano percorse due volte:

A→B→G→B→C→E→G→C→D→E→A→F→G→F→D→G→A

La soluzione del problema del postino cinese consiste quindi nell'individuare tutte le coppie di vertici con grado dispari e congiungere ogni coppia:

• direttamente con uno spigolo fittizio se sono adiacenti;
• indirettamente con il più piccolo percorso di spigoli fittizi se non sono adiacenti.