Circuito de Euler y Circuito de amilton

CIRCUITO DE EULER Y CIRCUITO DE HAMILTON

Sea G un Grafo  sin vértices 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
Ej.


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=1 una entrada  y/o salida

    D=3 entrada  y/o salida

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

TEOREMA DE EULER

Si una gráfica tiene más de dos vértices de grado sin par, entonces no puede tener una trayectoria de Euler.

Si una gráfica convexa  tiene exactamente 2 vértices de grado par, entonces tiene por lo menos una trayectoria de Euler. Cualquier circuito de Euler debe de iniciar en uno de los vértices de grados par y terminar en el otro.

a)    El grado de un vértice es el número 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 gráfica  es conexa cualquiera  de sus vértices  se puede unir por una trayectoria .Si una gráfica no es conexa se le denomina es discoteca, a los pedazos de una gráfica se les llamara componentes.