CIRCUITOS DE EULER Y DE HAMILTON
CIRCUITO DE EULER
Sea G un grafo sin vértices aislados, un circuito que tiene todas las aristas de G recibe el nombre de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.
Teorema: Si G es un grafo, G contiene un circuito euleriano si y solo si:
-G es un conexo
-Cada vértice de G es de grado par
Entonces si G (un grafo) tiene un vértice de grado 1 no puede tener
circuitos (x-x no se repite arista). Tampoco tiene grado impar porque no se
puede salir y entrar en n par de veces.
*Trayectoria de Euler debe comenzar en un vértice de grado impar y
terminar en otro.
Hamilton (1805-1865) inventó (y patentó) un
juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del
mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30
aristas, formando el grafo de un icosaedro.
Un circuito hamiltoniano, o de Hamilton, es un
grafo G es un camino que comienza y termina en un mismo vértice, pasando
exactamente una vez por cada vértice.
CICLO DE HAMILTO
Hamilton (1805-1865) inventó (y patentó) un
juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del
mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30
aristas, formando el grafo de un icosaedro.
Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.
No hay comentarios.:
Publicar un comentario