Multigrafo euleriano: differenze tra le versioni

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.

 

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.

 

 

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

 

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.

 

== Voci correlate ==