miércoles, 28 de marzo de 2012

TEORIA DE GRAFOS


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
 


 
 
 

2 comentarios:

  1. No entendi muy bien lo de haminton segun yo si el de Euler tiene que pasar por todos los vertices.

    ResponderEliminar
  2. El de Haminton tiene que pasar por todas las aristas.

    ResponderEliminar