RECORRIDO
DE GRAFOS
Su
objetivo es recorrer entre vértices y encontrar una trayectoria.Su camino es la sucesión de repetir las vértices y los lados en un camino simple a la longitud n solamente en cada ciclo en la ruta que sigue.
Los circuitos o ciclos pueden pasar dos veces por la misma arista
GRAFO
CONEXO
Es
aquel que para cualquier paro de vértices distintos entre si existe un proyecto
para ir de un vértice
GRAFO
NO CONEXO
Es
aquel en el que no existen vértices conectados
Ejemplo:
imagen:http://www.cimat.mx/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm
CAMINO
DE EULER
Es
aquel que el camino que recorre todas las vertices pasando por todas las ramas solamente
una vez
imagen: manzanita newt
CIRCUITO DE EULER
Es
aquel ciclo que recorre todos los vértices pasando por todos los lados
solamente una vez
GRAFO
Tiene
un circuito de Euler si y solo si es conexo y todas esas vértices tienen
valencia par
CIRCUITO
DE HAMILTON
Es similar al circuito de Euler con la
diferencia de que en lugar de parar por todos los grafos solamente una vez.
En el circuito de Hamilton se pasa
solamente una vez.
Respecto de un grafo que tiene un
circuito de Euler
si es conexo y todas sus vertices
tienen valencia par, sin embargo no hay forma de saber con anticipacion si
un grafo tiene o no un circuito de Hamilton


No entendi muy bien lo de haminton segun yo si el de Euler tiene que pasar por todos los vertices.
ResponderEliminarEl de Haminton tiene que pasar por todas las aristas.
ResponderEliminar