Anónimo
Condición necesaria para que una gráfica o multígrafo admita un camino de Euler
Demuestre que una condición necesaria para que una gráfica o multígrafo admita un camino de Euler es que el número de vértices de grado impar sea 2 o ninguno
1 respuesta
·
·
¡Hola Anónimo!
El gafo comenzará en un vértice y terminará en otro distinto o en el mismo. En todos los vértices intermedios el grafo entra y sale creando dos aristas nuevas por ser un camino Euleriano. Luego cada vez que se pasa por un vertice intermedio se le añaden dos aristas. Todo vértice intermedio que no sea el primero o el último tendrá un número par de aristas, sera de grado par.
Si el primero y último son distintos, ambos tendrán un numero par por las veces que se haya podido pasar entre medias más una arista única por el comienzo o final, luego habrá dos vértices de grado impar.
Y si se comienza y termina en el mismo vertice habrá un número par por los pasos intermedios más la arista de comienzo y la de final, luego será par. Y entonces todos son de grado par.
:
;