Autor Tema: Grafo por ciclo de Hamilton

0 Usuarios y 1 Visitante están viendo este tema.

02 Noviembre, 2018, 05:08 pm
Leído 1358 veces

janumet

  • Nuevo Usuario
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
hola
seria un placer para mi, recibir su ayuda.
tengo problemas para encontrar el ciclo de hamilton al grafo que adjunto en la imagen, me gustaría que me ayuden a encontrarlo, y en caso que no se pueda dar una explicacion del mismo.
muchas gracias 

el grafo esta adjuntado


02 Noviembre, 2018, 06:59 pm
Respuesta #1

Abdulai

  • Moderador Global
  • Mensajes: 2,363
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
...., y en caso que no se pueda dar una explicacion del mismo.

No existe ciclo hamiltoniano.

Explicación modo coloquial:
- Entre los vértices a y e  existen dos caminos --> elimino uno.
- Existe entre c,a y e  un solo camino posible, por lo tanto de existir un ciclo hamiltoniano debe existir un camino hamiltoniano entre los demás vértices que comience en c y termine en e.
- Pero si eliminamos c,a,e y sus correspondientes aristas queda formado un árbol --> imposible un CH.

02 Noviembre, 2018, 07:03 pm
Respuesta #2

janumet

  • Nuevo Usuario
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino