Autor Tema: ¿Grafo con ciclo/camino hamiltoniano y no conexo al mismo tiempo?

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

17 Enero, 2023, 10:42 pm
Leído 2890 veces

Maribrevas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 35
  • Karma: +0/-1
  • Sexo: Femenino
¿Puede un grafo contener un ciclo hamiltoniano y no ser conexo al mismo tiempo? Gracias.

18 Enero, 2023, 12:53 am
Respuesta #1

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿Puede un grafo contener un ciclo hamiltoniano y no ser conexo al mismo tiempo?

Por favor muestra lo que has intentado.

Pues si con "contener" te refieres a "puede no ser el propio grafo", entonces el grafo \( K_n\cup\{v\} \) con \( v \) aislado, es un ejemplo.

Saludos

18 Enero, 2023, 08:17 am
Respuesta #2

Maribrevas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 35
  • Karma: +0/-1
  • Sexo: Femenino
¿Puede un grafo no ser conexo pero contener un camino Hamiltoniano? Sí, es así por favor, ayuda con el dibujo. Gracias!

18 Enero, 2023, 08:50 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

He unido los dos temas donde planteabas prácticamente la misma cuestión.

¿Puede un grafo no ser conexo pero contener un camino Hamiltoniano? Sí, es así por favor, ayuda con el dibujo. Gracias!

No. Si contiene un camino o un ciclo Hamiltoniano el grafo tiene que ser conexo, porque por definición el camino o ciclo Hamiltoniano conecta todos los vértices.

Pues si con "contener" te refieres a "puede no ser el propio grafo", entonces el grafo \( K_n\cup\{v\} \) con \( v \) aislado, es un ejemplo.

Pero si el ciclo deja fuera un vértice entonces YA no es un ciclo hamiltoniano.

Saludos.