Este es una demostración de grafos:Sea P (m): Dado un grafo G = (V, A) con |A| = m.
Sea P (m): Dado un grafo G = (V, A) con |A| = m.
Si G es conexo y todos los vértices de G son de grado par, entonces G contiene un circuito Euleriano.
1 respuesta
No se si es 'matemáticamente correcto', pero veamos. Voy a hacer una especie de algoritmo
Paso 1: Como todos los nodos son de grado par, y el grafo es conexo, entonces agarro uno (digamos que el número 1).
Paso 2: 'Marco' ese nodo y por una arista llego a otro nodo (digamos el 2)
Paso 3: 'Marco' el nodo, y salgo por una arista no utilizada (como el grado es par, puedo hacerlo)
Paso 4: Cuando llego al otro nodo, me fijo si el nodo ya está marcado o no, si está marcado el procedimiento encontró un ciclo euleriano (porque llegó a un nodo marcado, por lo que recorrió un ciclo) y termina
Paso 5: Si no está marcado, entonces le asigno al nodo un nuevo número y vuelvo al paso 3
Y listo, como el grafo es conexo y todos los nodos son pares, el algoritmo anterior termina seguro (que es lo que se puede objetar para asegurar que el procedimiento haga la demostración)
Salu2