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.

Respuesta
1

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

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas