Condición necesaria y suficiente para que un grafo dirigido sea un circuito euleriano y un ciclo de Hamilton

Question

Conozco la condición necesaria y suficiente para que un grafo no dirigido contenga un ciclo hamiltoniano y un circuito euleriano, pero ¿existe una condición necesaria y suficiente para los grafos dirigidos?

el sentido común me dice que el grado de entrada menos el grado de salida de cada vértice debe ser cero, pero no sé si estoy en lo cierto (esto es para el circuito de euler)

Answer 1

Si se pueden encontrar ciclos hamiltonianos en un grafo no dirigido, también se pueden encontrar en grafos dirigidos sustituyendo cada vértice por una secuencia lineal de tres vértices *---*---* y conectar todos los entrando en aristas a uno de los nodos finales y todos los saliente aristas al otro nodo final. Después de eso no es necesario recordar la dirección de las aristas.

Para un circuito euleriano, es necesario que cada vértice tenga igual indegree y outdegree, y también que el gráfico sea finito y conectado y tenga al menos una arista. Entonces deberías ser capaz de demostrar que

• un paseo de longitud máxima que no utilice aristas debe ser un circuito (y, por tanto, que tales circuitos existen), y
• un circuito que no utiliza todas las aristas siempre puede ser ampliado, y por lo tanto que tal circuito de longitud máxima debe contener necesariamente todas las aristas.