CIRCUITO DE EULER Y CIRCUITO DE HAMILTON

CIRCUITO DE EULER Y CIRCUITO DE HAMILTON

Sea G un Grafo  sin vertices aislados  un circuito que tienen 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

EJEMPLO

TEOREMA :Si G es un Grafo  g contiene un circuito Euleriano si y solo si :

+G es conexo

+Cada vértice de G es de grado por

Entonces si G (un grafo ) tiene un vértice  de grado no puede tener  circuito (x-x) no se repite arista  tampoco tiene grado  impar porque no se puede salir y entrar  en N par de veces

Aristas  E-D :Grado      E=i una entrada  y7o salida

D=3 entrada  y/o salida

TEOREMA DE GRAFOS

 *Trayectoria  de Euler debe comenzar  en una vértice de grado  impar y terminar en otro

TEOREMA DE EULER

a) Si unoa grafica tiene mas de dos vertices de grado sin par  ,entonces no puede tener una trayectoria de Euler

b)Si una grafica convexa  tiene exactamente  dos vértice

s de grado par ,entonces tiene por lo menos una trayectoria de Euler.Cualquier circuito de Euler debe de iniciar  en uno de los vertices de grados par y terminar en el otro.

GRADO DE UN VERTICE

a) El grado de un vértice es el numero de aristas que se encuentra en ese mismo vértice

b) Un circuito  es una trayectoria que inicia y termina  en el mismo vértice

c) Una grafica  es conexa cualquiera  de sus vertices  se puede unir por una trayectoria .Si una grafica no es conexa se le denomina es disconexa , a los pedazos de una grafica se les llamara componentes