Ejercicio · ZW-CICLO-HAMILTONIANO-009 · ★★★ Avanzado
Un grafo bipartito tiene partes de 4 y 5 vértices. ¿Puede tener un ciclo hamiltoniano?
Elige una opción.
Ver respuesta
- C. No: el ciclo alterna entre partes y exige que tengan igual tamaño
Explicación
Los ciclos de un grafo bipartito alternan partes, luego usan igual cantidad de cada una. La afirmación «9 es impar y los ciclos son pares» es falsa: un triángulo es un ciclo impar (aunque no es bipartito).
Repasa el concepto: Ciclo hamiltoniano
Un ciclo hamiltoniano de un grafo \(G\) con \(n\ge 3\) vértices es un ciclo que pasa por cada vértice de \(G\) exactamente una vez.
\[\deg(v)\ge \tfrac n2\ \forall v\ \Longrightarrow\ \text{hay ciclo hamiltoniano}\]
Más ejercicios de ciclo hamiltoniano
- ZW-CICLO-HAMILTONIANO-001 ¿Cuántos ciclos hamiltonianos distintos tiene K_5, sin contar el vértice de partida ni el sentido d…
- ZW-CICLO-HAMILTONIANO-002 ¿Cuál de estos grafos tiene un ciclo hamiltoniano?
- ZW-CICLO-HAMILTONIANO-003 ¿Cuál de estos grafos bipartitos completos tiene un ciclo hamiltoniano?
- ZW-CICLO-HAMILTONIANO-004 Un grafo simple tiene 8 vértices y cada uno tiene grado al menos 4. ¿Qué se puede asegurar?
- ZW-CICLO-HAMILTONIANO-005 Un ciclo hamiltoniano de un grafo con 9 vértices, ¿cuántas aristas usa?
- ZW-CICLO-HAMILTONIANO-006 El corbatín son dos triángulos que comparten un vértice (5 vértices). ¿Qué es cierto?
- ZW-CICLO-HAMILTONIANO-007 ¿Cuál condición impide que un grafo tenga un ciclo hamiltoniano?
- ZW-CICLO-HAMILTONIANO-008 En el cubo Q_3 (vértices: cadenas de 3 bits; aristas: cadenas que difieren en un bit), ¿cuál lista…