Es una trayectoria (camino sin
repetir nodos) que empieza y termina en el mismo vértice, no tiene aristas
repetidas y pasa por cada vértice una sola vez.
No admite circuitos Hamiltonianos. El
razonamiento es el siguiente: Si se empieza en v1, v3, v2, v4 y si se está en
los demás vértices, en el v5 se estará dos veces.
Si se empieza en v5, para luego ir a los
vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por
v5.
Para completar el circuito, se debe regresar
a v5, por lo que se pasa tres veces por él.
Teorema
Sea m el número de aristas, sea n el número
de vértices
Tiene un circuito hamiltoniano si 𝑚≥1/2(𝑛^2−3𝑛+6)
Ejemplo:
Todo grafo completo con al menos dos vértices
tiene un circuito de Hamilton.
En un grafo completo podemos encontrar
distintos circuitos de Hamilton; a este respecto tenemos el siguiente
resultado:
El número de circuitos de Hamilton distintos
que se pueden encontrar en un grafo completo de n vértices se calcula mediante:
EJEMPLO:
Un grafo tiene un numero de vértices n=5,
¿Cuántos circuitos de Hamilton se pueden determinar?
En este caso n=5, por tanto
0 comentarios:
Publicar un comentario