Es este grafo Hamiltoniano?

Question

Yo sé que un grafo Hamiltoniano tiene un camino que visita cada vértice una vez. Pero no estoy seguro de cómo averiguar si este no. Obviamente no se puede probar y seguimiento de las distintas rutas de acceso para ver si funciona, pero que es muy poco fiable.

Así que mi pregunta es, si este grafo es Hamiltoniano, ¿dónde estaría el ciclo de Hamilton? Y si no es Hamiltoniano, ¿cómo podemos demostrarlo?

Gracias!

Answer 1

Este es un gráfico bipartito. El color del medio de tres vértices rojo y los otros cuatro vértices azul. Cada camino en el grafo tiene los vértices de la alternancia de la imagen en color. Por lo que cualquier ciclo Hamiltoniano un número igual de rojo y azul vértices...

Answer 2

Una más detallada explicación de las observaciones formuladas por el Señor Tiburón a lo Desconocido de la respuesta:

Este es un gráfico bipartito (dos conjuntos de vértices que forman un gráfico de tal manera que ningún borde lugares de los dos vértices de un mismo conjunto adyacente). El color del medio de tres vértices de color rojo y los otros cuatro vértices azul (indicando los dos conjuntos).

Todos los bordes del gráfico se conecta un rojo y un azul vértice. Por lo tanto, todos los caminos en el gráfico de visita de vértices se alternan en el color.

Desde cualquier ciclo tiene que terminar en el mismo vértice como empezó, el camino ha de visitar un número par de vértices. De lo contrario, el camino requiere la conexión de una red a una red de vértices azules o blue vértice, que sabemos que no podemos hacer ya que este es un bipartito gráfico. Esto significa que cada ciclo se contienen una cantidad igual de rojo y azul de los vértices.

Desde cualquier ciclo Hamiltoniano tiene que contener todos los vértices y este gráfico no tiene una cantidad igual de rojo y azul vértices, es imposible, en este gráfico para crear un ciclo Hamiltoniano.

Tenga en cuenta que el argumento no funciona de la otra manera; bipartito gráficos con la misma cantidad de puntos en ambos conjuntos, donde los ciclos Hamiltonianos no son posibles. Imagina un gráfico como el que se proporciona en la pregunta, pero con cuatro grupos de vértices: 2 (rojo) - 1 (azul) - 1 (rojo) - 2 (azul). Aquí es imposible crear un ciclo Hamiltoniano ya que requeriría de cruzar el medio vértices dos veces.

Answer 3

Uno nunca puede trazar un ciclo Hamiltoniano en un grafo con vértices tener impar borde número. Nunca se puede encontrar un camino Hamiltoniano en un grafo con más de dos vértices tener impar borde número.