Hola, tengo una consulta. El Teorema de Bondy-Chvátal dice que un grafo tiene un ciclo Hamiltoniano si y solo si su cerradura tiene un ciclo Hamiltoniano, y la cerradura se define como: para todo vértices a y b no adyacente, si el gr(a) +gr(b) ≥ n, siendo n la cantidad de vértices, entonces se agrega la arista {a,b}, lo que pregunto es lo siguiente: Las aristas agregadas por este método "cuentan" en la suma de los grados resultantes? o se sigue manejando los grados con el grafo original?
Gracias.
En respuesta a Matías Nicolás Leal Baceda
Re: Teorema de Bondy-Chvátal para ciclos H
de Pablo Romero -
Buenas Nicolás:
En el nuevo grafo puedes aplicar la condición suficiente de existencia de ciclos Hamiltonianos.
El agregado de esas aristas es un invariante en Hamiltonianos (es decir, tanto el grafo anterior como el original son los dos o ninguno Hamiltoniano).
Cordiales saludos,
Pablo.