Grafos, grados y recorridos eulerianos
Definición y alcance HECHO
Un multigrafo finito no dirigido G=(V,E) consta de un conjunto finito de vértices V y una colección finita de aristas E. Cada arista une dos vértices sin imponer un sentido de recorrido. Varias aristas pueden unir el mismo par de vértices; un lazo también puede unir un vértice consigo mismo. Un grafo simple es el caso particular sin lazos ni aristas paralelas.
Se elige este marco porque varios puentes de Königsberg conectaban las mismas zonas terrestres: representarlos exige aristas paralelas. El artículo no trata ni los grafos dirigidos, cuyas aristas tienen una dirección, ni los grafos ponderados, en los que a cada arista se le asigna, por ejemplo, una distancia o un coste.
Por tanto, el multigrafo subyacente solo conserva la relación de incidencia: qué vértices une cada arista. Las posiciones dibujadas, las longitudes y los ángulos no forman parte de su definición. Estos datos pueden añadirse al modelo cuando sean útiles, pero no son necesarios para el problema estudiado aquí.
El vocabulario mínimo HECHO
| Término | Definición en un multigrafo no dirigido |
|---|---|
| Grado de un vértice | Número de extremos de aristas incidentes en el vértice; un lazo cuenta como 2 |
| Paseo | Sucesión de vértices y aristas incidentes; los vértices y las aristas pueden repetirse |
| Recorrido | Paseo que no repite ninguna arista |
| Camino | Paseo que no repite ningún vértice |
| Circuito | Recorrido cerrado: el inicio y el final coinciden |
| Ciclo | Circuito que no repite ningún vértice, salvo el vértice común de inicio y final |
| Conexo | Un camino une cada par de vértices |
Un recorrido euleriano utiliza cada arista exactamente una vez. Es abierto si sus extremos son distintos y se convierte en un circuito euleriano si regresa a su vértice inicial. Aquí, la palabra «euleriano» se refiere a las aristas, no a los vértices.
El lema del apretón de manos HECHO
Cada arista ordinaria tiene dos extremos y añade 1 al grado de cada uno de sus vértices. Un lazo también tiene dos extremos, ambos en el mismo vértice, y por tanto añade 2 a su grado. Al contar con multiplicidad, cada arista contribuye exactamente 2 a la suma total:
v∈V∑deg(v)=2∣E∣
El miembro derecho es par. Los vértices de grado par aportan una suma par; por tanto, la suma de los grados impares también debe ser par. Ahora bien, una suma de enteros impares es par si y solo si contiene un número par de términos. En consecuencia, siempre hay un número par de vértices de grado impar.
En un grafo simple que representa una asamblea, una arista significa que dos personas se dieron la mano. El lema afirma entonces que el número de personas que participaron en un número impar de apretones de manos es par. Esta imagen explica su nombre, pero la demostración también es válida para los multigrafos y los lazos con la convención de grado anterior.
Los puentes de Königsberg HECHO
El problema histórico describe cuatro zonas terrestres unidas por siete puentes. La pregunta consistía en encontrar un paseo que cruzara cada puente exactamente una vez, sin exigir el regreso al punto de partida.
Euler designó las zonas con letras y representó los cruces sucesivos mediante sucesiones de letras. En la reformulación moderna de la teoría de grafos, cada zona se convierte en un vértice y cada puente en una arista. El multigrafo resultante tiene cuatro vértices de grados 5, 3, 3 y 3. Su suma es 14, es decir, el doble del número de aristas (siete), de acuerdo con el lema.
En un recorrido euleriano se utilizan todas las aristas incidentes. Cada paso por un vértice intermedio las consume por pares: una para entrar y otra para salir. Por tanto, solo el inicio y el final de un recorrido euleriano abierto tienen grado impar, mientras que un circuito euleriano no tiene ninguno.
Königsberg tiene cuatro. No existe ningún recorrido que utilice exactamente una vez cada uno de los siete puentes. Euler estableció esta imposibilidad y formuló las reglas generales de paridad; el teorema moderno ofrece la caracterización completa.
El teorema euleriano moderno HECHO
Consideremos un multigrafo finito no dirigido en el que todos los vértices de grado distinto de cero pertenecen a una misma componente conexa.
- Admite un circuito euleriano si y solo si todos sus vértices tienen grado par.
- Admite un recorrido euleriano abierto si y solo si exactamente dos vértices tienen grado impar; son necesariamente su inicio y su final.
La necesidad se deriva del emparejamiento entrada–salida. La suficiencia es constructiva. Cuando todos los grados son pares, se parte de un vértice incidente en una arista y se siguen aristas que aún no se hayan utilizado. No es posible quedar bloqueado en otro vértice: por paridad, cada llegada deja allí una arista no utilizada por la que volver a salir. Por tanto, el recorrido acaba regresando al punto de partida y forma un circuito.
Si quedan aristas, la conexidad garantiza que un vértice del circuito toca una parte aún no utilizada. Desde ese vértice se construye un nuevo circuito y después se inserta en el primero. Al repetir la operación se obtiene un circuito que contiene todas las aristas: este es el principio del algoritmo de Hierholzer.
Si existen exactamente dos vértices de grado impar, se añade temporalmente una arista entre ellos. Todos los grados pasan a ser pares; se construye un circuito euleriano y después se retira la arista añadida. El circuito se abre entonces en un recorrido cuyos extremos son precisamente los dos vértices de grado impar.
Modelizar exige elegir la estructura adecuada HECHO
Las carreteras, las dependencias de software, las moléculas y los circuitos eléctricos pueden representarse mediante grafos, pero no mediante el mismo modelo sin matices.
- Una red de carreteras puede ser no dirigida o dirigida y suele incluir distancias o tiempos de viaje.
- Un grafo de dependencias suele ser dirigido: un ciclo expresa en él una dependencia circular.
- Un grafo molecular lleva etiquetas en los átomos y los enlaces.
- Una red eléctrica añade magnitudes físicas y leyes que no están contenidas en la mera incidencia.
La ventaja de la abstracción no consiste, por tanto, en que un único algoritmo sirva para todo. Consiste en separar la estructura común —vértices y aristas— de la información propia del dominio, y después elegir un teorema o un algoritmo cuyas hipótesis correspondan exactamente al grafo construido.
Resumen
En un multigrafo finito no dirigido cuyas aristas pertenecen a una misma componente, la paridad de los grados determina si cada arista puede recorrerse exactamente una vez: cero vértices de grado impar para un circuito y exactamente dos para un recorrido abierto.