Matemticas Discretas Tc1003 Teora de Grafos
7.2 Circuitos de Euler y Circuitos de Hamilton
EULER Definicin. Sea G un grafo sin vrtices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vrtice y recorre cada arista exactamente una vez. Ejemplos:
(a) No lo admite porque v4 es un vrtice aislado. (b) No lo admite porque cualquier ciclo utilizar la arista e1 dos veces. (c) El circuito v1 e1 v2 e2 v1 es euleriano. (d) El circuito v3 e3 v1 e1 v2 e2 v3 es euleriano. (e) No admite ningn circuito euleriano. (f) v1 e1 v2 e2 v3 e3 v4 e4 v2 e5 v5 e6 v1 es un circuito euleriano. Existe un criterio preciso para saber cuando un grafo admite un circuito euleriano. Este criterio lo proporciona el siguiente teorema. Teorema. Sea G un grafo. G contiene un circuito euleriano s y slo s: G es conexo. Cada vrtice de G es de grado par.
Ejemplos: Ngj/v2008 1
7.2 Circuitos de Euler y Hamilton
Matemticas Discretas Tc1003 Teora de Grafos
Cmo recorres todas las calles de una sola vez? Iniciar y terminar en la Terminal de reciclado
Figura 2
Figura 3
No hay circuito Por qu? Figura 4
Hay circuito Por qu?
w w?
Figura 5
Figura 6
Ngj/v2008
7.2 Circuitos de Euler y Hamilton
Matemticas Discretas Tc1003 Teora de Grafos La pregunta: Es posible determinar si existe una trayectoria o un circuito de Euler sin encontrar una forma explcita? En Figura 2 Arista E D : grado de E = 1 una entrada y/o salida D = 3 entrada y/o salida
Entonces si G (un grafo) tiene un vrtice de grado 1 no puede tener circuitos ( x x : no se repite arista) tampoco se tiene grado impar porque no se puede salir y entrar en n par de veces. Teorema 1 a) Si una grfica G tiene un vrtice de grado impar entonces no puede existir un circuito de Euler ( x x : no se repite arista) b) Si G es conexa (todos los vrtices tienen un camino para llegar) y todos los vrtices tienen grado par, entonces existe circuito de Euler ( x x : no se repite arista)
No existe circuito Euler trayectoria si
Figura 4? Figura 6?
no existe
Si existe circuito Euler
circuito Euler no existe circuito Euler
Teorema 2 a) Si una grfica G tiene raz de dos vectores (3, 4, 5) de grado impar, entonces no puede existir una Trayectoria de Euler en G. b) Si G es conexa y tiene exactamente dos vrtices de grado impar, entonces existe una Trayectoria de Euler en G. Cualquier Trayectoria de Euler debe comenzar en un vrtice de grado impar, terminar en otro. Figura 2 si hay trayectoria Figura 3 no hay trayectoria Figura 4 no hay trayectoria Figura 6 si hay trayectoria Ngj/v2008 3
7.2 Circuitos de Euler y Hamilton
Matemticas Discretas Tc1003 Teora de Grafos Ejercicio: Figura A Figura B
Figura C
Cules de las tres grficas tienen de circuito de Euler, una trayectoria de Euler pero no circuito, o ninguno de estos? Figura A No es circuito No es trayectoria Figura B No es circuito Es trayectoria Figura C Es circuito Es trayectoria Puente: U1 U 2 es un puente si al eliminarlo se crea una grfica disconexa Ejemplo: B D
Ngj/v2008
7.2 Circuitos de Euler y Hamilton
Matemticas Discretas Tc1003 Teora de Grafos HAMILTON Definicin: Un circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los vrtices de G. Un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vrtice y pasa por cada vrtice una sola vez. Ejemplos: Cul de los grafos siguientes admite un circuito hamiltoniano?
Solucin (a) No admite circuitos hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se est en los dems vrtices, en el v5 se estar dos veces. Si se empieza en v5, para luego ir a los vrtices v1 o v4 a v3 o v2 respectivamente, se tendr que pasar de nuevo por v5 (puesto que se empezar en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por l. (b) Un ciclo hamiltoniano es: v1 e1 v2 e2 v3 e3 v4 e4 v1 Teorema. Sea G un grafo conexo con n vrtices, donde n3. Si la suma de los grados de cada par de vrtices no adyacentes es mayor o igual a n, entonces G tiene un circuito hamiltoniano. Ejemplos:
A B C D E : Trayectoria Hamiltoniana, no es trayectoria de Euler pero no circuito
A B C D A:
Circuito hamiltoniano, no es circuito de Euler
Ngj/v2008
7.2 Circuitos de Euler y Hamilton
Matemticas Discretas Tc1003 Teora de Grafos Teorema 2 Sea m el nmero de aristas Sea n el nmero de vrtices
G
es un circuito hamiltoniano si m
1 2 n 3n + 6 2
Ejemplo:
m = 5, n = 5
5 1 (25 15 + 6 ) 2
no tiene Circuito hamiltoniano
m = 6, n = 4
6 1 (16 12 + 6 ) 2
si tiene Circuito Hamiltoniano
Ngj/v2008
7.2 Circuitos de Euler y Hamilton
