grafos

Semana 12: CAMINOS Y CICLOS HAMILTONIANOS

Caminos Hamiltonianos: Si es un grafo o multígrafo con , un camino Hamiltoniano es un camino simple de que contiene todos los vértices.

CiclosHamiltonianos: Si es un grafo o multígrafo con , decimos que tiene un ciclo Hamiltoniano si existe un ciclo en que contenga cada vértice de .

Definición: Diremos que un grafo dirigido escompleto, al cual denotaremos por , si tiene vértices y para cualquier par de vértices distintos, exactamente una de las aristas están en .

Teorema 1: Un grafo dirigido completo contiene siempre uncamino Hamiltoniano dirigido.

EJEMPLO ILUSTRATIVO: En un torneo de ajedrez, cada jugador se enfrenta con cada uno de los demás jugadores exactamente una vez. Queremos clasificar a los jugadoressegún el resultado en el torneo ¿es posible hacerlo?
Solución: Supongamos que para tres de estos jugadores, digamos: , puede ocurrir que derrote a y derrote a y derrote a , no siempre esposible tener una clasificación en la que un jugador que este en cierta posición haya derrotado a todos los jugadores que han quedado por debajo de dicha posición. Si representamos a los jugadores por mediode vértices, construimos un grafo dirigido con estos vértices, trazando la arista si derrota a , luego es un grafo dirigido completo y por teorema 1, tiene un camino Hamiltoniano, es decirpodemos enumerar a todos los jugadores de modo que cada uno haya derrotado al siguiente jugador de la lista.

Teorema 2: Sea un grafo sin lazos, con . Si entonces contiene un camino Hamiltoniano.Corolario 2.1: Sea un grafo sin lazos, con vértices. Si entonces contiene un camino Hamiltoniano.
Teorema 3: Sea un grafo no dirigido sin lazos, con . Si no adyacentes entonces contiene unciclo Hamiltoniano.
Corolario 3.1: Si un grafo no dirigido sin lazos, con y si entonces contiene un ciclo Hamiltoniano.
Corolario 3.2: Si un grafo no dirigido sin lazos, con entonces contiene...