Teoría de gráficas
La teoría de gráficas se inicia con ideas geométricas muy simples y tiene muchas aplicaciones importantes. Una gráfica G consta de un conjunto finito V de objetos llamados vértices y un conjunto finito E de objetos llamados aristas y una función γ que asigna a cada arista un subconjunto {v, w}, donde v y w son vértices (que podrían ser iguales). Se escribe G = (V,E, γ ) cuando se deba enfatizar los vértices de G.
Si e es una arista, y γ(e) = {v, w}, se dice que e es una arista entre v y w y que e está determinada por v y w. Los vértices v y w son los extremos de e. Si sólo existe una arista entre v y w, con frecuencia se identifica a e con el conjunto {v, w}.
Ejemplo.
Sean V = {1, 2, 3, 4} y E = {e1, e2, e3, e4, e5}. Sea γ dada por
γ(e1) = γ(e5) = {1, 2}, γ(e2) = {4, 3}, γ(e3) = {1, 3}, γ (e4) = {2, 4}
Entonces G = (V, E, γ) es una gráfica.
Cualquiera de las siguientes figuras representa la gráfica dada en el ejemplo anterior.
El grado de un vértice es el número de aristas que tienen a ese vértice como extremo. Una gráfica puede contener a una arista de un vértice a sí mismo; tal arista es un bucle cerrado (o lazo). Un bucle cerrado contribuye en 2 unidades al grado de un vértice.
Ejemplo.
En la gráfica a, el vértice 1 tiene grado 2, el vértice 2 tiene grado 4, el vértice 3 tiene grado 2 y el vértice 5 tiene grado 3.
En la figura b, el vértice 1 tiene grado 3, el vértice 2 tiene grado 3, los vértices 3 y 4 tienen grado 2 y el vértice 5 tiene grado 0.
Cada vértice de la figura c tiene grado 2.
Un vértice de grado 0 es un vértice aislado. Dos vértices que determinan una arista son vértices adyacentes.
Definición: Una trayectoria (o camino) en una gráfica es una sucesión π: v1, v2, . . . ,vk de vértices, cada uno adyacente al siguiente, y una elección de una arista entre vi y vi+1, de modo que ninguna arista es elegida más de una vez. En términos geométricos, esto significa que es posible iniciar en v1 y viajar a través de las aristas hasta vk y nunca utilizar la misma arista dos veces.
Un circuito es una trayectoria que inicia y termina en el mismo vértice. En el tema anterior llamamos a esto un ciclo de trayectoria, sin embargo la palabra circuito es más común en teoría general de grafos. Una trayectoria v1, v2, . . . ,vk es simple si ningún vértice aparece más de una vez. De manera análoga un circuito v1, v2, . . . ,vk-1, vk es simple si los vértices v1, v2, . . . ,vk-1, vk son todos distintos.
Ejemplo.
Las trayectorias de la figura a incluyen a π1: 1, 2, 1, π2: 1, 2, 3, 5,5, π3: 4, 2, 3, 5 y π4: 4, 2, 1
Algunos ejemplos de trayectorias en la gráfica de la figura b son: π1: 1, 2, 3, 4, 2 y π2: 1, 1, 2, 3. La trayectoria π3: 2, 3, 4, 2 es un circuito.
En la figura c, la sucesión 3, 4, 5,4 no es una trayectoria, pues la única arista existente entre 4 y 5 tendría que recorrerse dos veces.
La trayectoria π6: 2, 3, 4, 2, 1 de la figura 5 no es simple. ¿Por qué?
Definición: Una gráfica es conexa si existe una trayectoria de cualquier vértice a otro de la gráfica. En caso contrario, la gráfica es disconexa. Si la gráfica es disconexa, las diversas partes conexas son las componentes de la gráfica.
Ejemplo.
La gráfica a es conexa. Las gráficas de las figuras b y c son disconexas. La gráfica de la figura c tiene dos componentes.
Trayectorias y circuitos de Euler
Una trayectoria en una gráfica G es una trayectoria de Euler si incluye a cada una de las aristas sólo una vez. Un circuito de Euler es una trayectoria de Euler que es a la vez un circuito.
Ejemplo.
Una trayectoria de Euler en la figura a es π: E, C, B, A, D, C.
Un circuito de Euler en la figura b es π: 5, 3, 2, 1, 3, 4, 5
Teorema 1
Si una gráfica G tiene un vértice de grado impar, entonces no puede existir un circuito de Euler en G. Si G es una gráfica conexa y todos los vértices tiene grado par, entonces existe un circuito de Euler en G.
Teorema 2
Si una gráfica G tiene más de dos vértices de grado impar, entonces no puede existir una trayectoria de Euler en G.
Si G es conexa y tiene exactamente dos vértices de grado impar, entonces existe una trayectoria de Euler en G. Cualquier trayectoria de Euler debe comenzar en un vértice de grado impar y terminar en el otro.
Ejemplo.
¿Cuáles de las gráficas de las figuras a, b y c tienen un circuito de Euler, una trayectoria de Euler pero no un circuito de Euler, o ninguno de éstos?
En la figura a, cada uno de los cuatro vértices tiene grado 3, de manera que no existe un circuito o trayectoria de Euler.
La gráfica de la figura b tiene exactamente dos vértices de grado impar. No existe un circuito pero si una trayectoria de Euler.
En la figura c, todos los vértices tienen grado par; así, la gráfica debe tener un Circuito de Euler.
Definición: Una arista {vi, vj} es un puente en una gráfica conexa de G si al eliminar {vi, vj} se crea una gráfica disconexa.
Por ejemplo en la gráfica de la derecha {B, E} es un puente.
Algoritmo de Fleury
Sea G = (V, E, γ ) una gráfica conexa con todos sus vértices de grado par.
Paso 1. Se elige un miembro v de V como vértice inicial para el circuito. Sea π: v el inicio de la trayectoria por construir.
Paso 2. Suponga que ya se ha construido π: v, u, . . ., w. Si en w sólo existe una arista {w, z}, se extiende π a π: v, u, . . ., w, z. Se elimina {w, z} de E y w de V. Si en w existen varias aristas, se elige una que no sea un puente {w, z}. Extienda π a π: v, u, . . ., w, z y se elimina {w, z} de E.
Paso 3. Repita el paso 2 hasta que no sobren aristas en E.
Fin del algoritmo.
Ejemplo.
Utilice el algoritmo de Fleury para construir un circuito de Euler para la gráfica siguiente:
Ejercicios
Para cada una de las siguientes gráficas, indique si tiene un circuito de Euler, una trayectoria de Euler o ninguno de éstos. Justifique su respuesta.
1.
2.
3.
4.
5.
6.
7.
8.
9.