Multigrafo euleriano: differenze tra le versioni

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.