Ejercicio · ZW-CICLO-HAMILTONIANO-008 · ★★☆ Intermedio
En el cubo \(Q_3\) (vértices: cadenas de 3 bits; aristas: cadenas que difieren en un bit), ¿cuál lista es un ciclo hamiltoniano ?
Elige una opción.
A 000, 001, 011, 111, 110, 010, 100, 101 B 000, 001, 010, 011, 100, 101, 110, 111 C 000, 001, 011, 010, 110, 111, 101, 001 D 000, 001, 011, 010, 110, 111, 101, 100 Ver respuesta D. 000, 001, 011, 010, 110, 111, 101, 100← Volver a la pregunta
Explicación Cada término debe diferir del anterior en un bit, sin repetir, y el último del primero. Solo la lista 000, 001, 011, 010, 110, 111, 101, 100 (código Gray) lo cumple; las otras tienen saltos de dos bits o repiten un vértice.
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