Multigrafo euleriano: differenze tra le versioni

Versione delle 02:48, 18 feb 2013

Versione delle 10:50, 10 mar 2013

Riga 17:

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 costuizionecostruzione 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.