Loading AI tools
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.
Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.
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.
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.
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.
Per semplice esclusione, si trova che un multidigrafo connesso non possiede cammini euleriani se e solo se è di tipo 2.
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
