Multigrafo euleriano

Da Wikipedia, l'enciclopedia libera.

In teoria dei grafi si dice multigrafo euleriano un multigrafo connesso, privo di cappi e dotato di un cammino euleriano, cioè di un cammino che tocca tutti i suoi spigoli una e una sola volta.

Si pone il problema di stabilire se un multigrafo possiede un cammino euleriano o meno. Questo problema può risolversi piuttosto agevolmente attraverso un algoritmo individuato da Eulero (v. Problema dei ponti di Königsberg) che è in grado per ogni multigrafo di costruire rapidamente tale cammino se esiste e di segnalare la sua inesistenza in caso contrario.

Ricordiamo preliminarmente che un qualsiasi multigrafo possiede un numero pari di vertici di grado dispari. Infatti la somma dei gradi di tutti i vertici del multigrafo deve essere un numero uguale al doppio del numero degli spigoli, e quindi un numero pari.

Conviene allora distinguere tre tipi di multigrafi connessi: quelli aventi tutti i vertici di grado pari, quelli aventi due vertici di grado dispari e quelli con più di due vertici di grado dispari. Questa distinzione si può effettuare con una semplice ispezione degli spigoli. Si dimostra che i primi sono dotati di un circuito euleriano, i secondi posseggono un cammino euleriano ma non un circuito euleriano, i terzi non sono multigrafi euleriani.

Algoritmo Consideriamo un multigrafo connesso qualsiasi M; se questo non possiede vertici di grado dispari, allora costruisce un suo circuito euleriano; se M possiede esattamente due nodi di grado dispari, allora individua un cammino euleriano che li collega; se possiede quattro o più vertici dispari, allora segnala che non è un multigrafo euleriano.

Procedimento

Se M possiede un nodo dispari si inizia da quello; in caso contrario si può iniziare da un qualsiasi nodo.

Si procede a una prima fase di costuizione di un cammino euleriano aggiungendo via via nuovi spigoli e segnando quelli che risultano utilizzati. Questa manovra si può concludere con l'esaurimento di tutti gli spigoli. Nel primo caso si deve terminare il cammino nel vertice di partenza, nel secondo nel secondo vertice di grado dispari, nel terzo caso la cosa è impossibile.

Se rimangono altri spigoli ci cerca di ampliare il cammino a partire da un vertice rimasto con un numero pari di spigoli non utilizzati. Questo è possibile per i grafi dei primi due tipi i quali potranno essere effettivamente ampliati fino ad esaurire i loro spigoli ed a giungere al vertice di partenza o al vertice rimasto di grado dispari. Non può invece proseguire indefinitamente nel terzo caso. Ogni ampliamento del cammino lascia tutti i vertici con grado rimanente pari nei primi due casi e lo stesso numero di vertici di grado dispari nel terzo.

QED