In teoria dei grafi si dice multidigrafo euleriano un multidigrafo
connesso, privo di cappi e dotato di un cammino euleriano, cioè di un
cammino che tocca tutti i suoi archi una e una sola volta.
Problema dell'individuazione di cammini euleriani
Si pone il problema di stabilire se un multidigrafo possiede un cammino
euleriano o meno. Questo problema può risolversi abbastanza agevolmente attraverso un algoritmo
che costituisce una variante dell'algoritmo individuato da Eulero per individuare
cammini euleriani sui multigrafi (v. Multigrafo euleriano e Problema dei ponti di Königsberg).
Ricordiamo preliminarmente che per un qualsiasi multidigrafo la somma dei gradi uscenti
dei suoi nodi coincide con la somma dei loro gradi entranti.
Infatti ogni arco contribuisce con l'aggiunta di una unità a ciascuna di queste somme.
Conviene inoltre distinguere tre tipi di multidigrafi connessi:
- Tipo 0: multidigrafi aventi tutti i nodi con grado entrante e grado uscente uguali.
- Tipo 1: multidigrafi aventi tutti i nodi con grado entrante e grado uscente uguali, con l'eccezione di due: il primo di questi, che denotiamo con s (sorgente), ha il grado uscente uguale al grado entrante aumentato di 1; il secondo, che denotiamo con i (inghiottitoio), ha il grado uscente uguale al grado entrante diminuito di 1.
- Tipo 2: multidigrafi rimanenti caratterizzati da maggiori differenze fra gradi entranti e uscenti.
![]()
Multidigrafi di tipo 0
Proposizione 1 Un multidigrafo che possiede un circuito euleriano ha
tutti i nodi con grado entrante e grado uscente uguali.
Dimostrazione Consideriamo un multidigrafo M ed un suo circuito euleriano
che consideriamo inizi e termini nel nodo q. I gradi entranti e uscenti dei nodi di M
si possono ottenere sommando i contributi dei nodi che si incontrano percorrendo
il circuito a partire da q, nodi che si possono incontrare più volte.
Il contributo di ogni nodo aumenta di uno sia il suo grado uscente che il suo grado entrante.
QED
Proposizione 2 Un multidigrafo che
ha tutti i nodi con grado entrante e grado uscente uguali possiede un circuito euleriano.
La dimostrazione di questo fatto è costruttiva e viene fornita dal
seguente algoritmo.
Algoritmo Dato un multigrafo M i cui nodi presentano grado entrante e grado
uscente uguali, costruire un suo circuito euleriano.
Procedimento
In una prima fase si sceglie un nodo di partenza s qualsiasi e da questo si costruisce
un circuito iniettivo sugli archi tenendo conto di tutti gli archi utilizzati.
Dal nodo di partenza s si sceglie ad arbitrio un arco uscente.
Giunti in un nodo, se questo coincide con s la prima fase è conclusa; in caso contrario
vi è sicuramente almeno un arco uscente non ancora utilizzato per l'uguaglianza dei suoi gradi
e per il fatto che si sono utilizzati k dei suoi archi uscenti e k+1 degli entranti:
quindi si può estendere il cammino iniettivo sugli archi.
Si possono poi avere fasi successive nelle quali il circuito individuato C viene esteso.
Queste fasi di estensione si concludono quando i nodi del circuito C non hanno più archi
entranti o uscenti inutilizzati. Se un nodo p presenta un arco uscente si inizia
con questo ad individuare un nuovo circuito C' costituito dagli archi rimanenti. Si procede
come nella prima fase giungendo in qualche passo ad un nodo toccato da C: se questo è il
nodo di ripartenza p C' è concluso, in caso contrario il cammino iniettivo può proseguire
con un arco uscente che deve essere ancora disponibile. Quando accanto a C è stato individuato
il circuito C' con almeno un nodo in comune con C, si ottiene un circuito iniettivo più
esteso percorrendo a partire dal nodo in comune prima un circuito poi l'altro.
Questi processi di estensione possono procedere fino alla individuazione di un intero circuito
euleriano. QED
- A questo punto si può affermare che i multidigrafi con circuiti euleriani sono tutti e soli i multidigrafi connessi i cui nodi hanno grado entrante e grado uscente uguali.
Multidigrafi di tipo 1
Proposizione 3 Un multidigrafo di tipo 1 possiede un cammino euleriano.
Dimostrazione costruttiva Consideriamo un multidigrafo con un nodo sorgente s
e un nodo inghiottitoio i. Si osserva che aggiungendogli un arco da i ad s lo si trasforma
in un multidigrafo di tipo 0. Su di esso quindi si riesce ad individuare un circuito euleriano
che comprende l'arco (i,s). Si individua quindi un cammino euleriano sul multidigrafo dato
il quale, come prevedibile con considerazione sui gradi, inizia nel nodo sorgente e
finisce nel nodo inghiottitoio. QED
Proposizione 4 Un multidigrafo che possiede un cammino euleriano è di tipo 1.
Dimostrazione Se si calcolano le sequenze dei semigradi entrante e uscente
relative ai nodi disposti in un qualche ordine procedendo sugli archi del cammino
si ottengono gradi entranti e uscenti uguali ad eccezione del nodo iniziale con grado uscente
maggiore di 1 del grado entrante e del nodo finale con grado uscente inferiore di 1
del grado entrante. QED
- A questo punto si può affermare che i multidigrafi con cammini euleriani non chiusi sono tutti e soli i multidigrafi connessi di tipo 1.
Multidigrafi di tipo 2
Per semplice esclusione, si trova che un multidigrafo connesso non possiede cammini euleriani
se e solo se è di tipo 2.
Osservazioni
Le proprietà che si sono dimostrate caratteristiche rispettivamente dei multidigrafi
con circuiti euleriani, con cammini euleriani non chiusi e privi di cammini euleriani
sono facilmente ottenibili per ogni definizione dei multidigrafi che risulti
praticabile. Anche i procedimenti costruttivi dei circuiti e dei cammini euleriani
sono implementabili in modo efficiente, sostanzialmente con tempi di elaborazione
proporzionali al numero degli archi dei multidigrafi.
Il problema della individuazione di circuiti o di cammini euleriani di un multigrafo
riguarda configurazioni globali che risulta facile individuare: infatti per questo
si sono rivelati sufficienti calcoli e scelte riguardanti i singoli nodi e gli archi
che li riguardano, cioè elaborazioni puntuali.
È utile osservare anche che i problemi riguardanti i cammini hamiltoniani, cioè
configurazioni globali relative a grafi o digrafi (e non multigrafi e multidigrafi) a prima vista simili ai cammini euleriani, in effetti
sono molto più impegnativi dal punto di vista delle elaborazioni e molto meno definiti
dal punto di vista delle caratterizzazioni generali.
Voci correlate
