Introducción a la Teoría de Grafos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué estudia realmente la teoría de grafos

La teoría de grafos estudia una sola idea, muy pequeña: una colección de objetos y un registro de qué pares de ellos están conectados. Esa es toda la materia. Lo que la hace merecedora de siglo y medio de matemáticas es que una cantidad enorme de preguntas prácticas resultan ser preguntas exactamente sobre eso, y sobre nada más.

Piensa en cuatro problemas que parecen no tener relación. Una empresa de reparto quiere la ruta más corta entre dos almacenes. Un compilador necesita el orden en que debe construir los módulos de un proyecto. Una bióloga quiere saber qué proteínas interactúan, directamente o a través de intermediarias. Un operador de red quiere saber qué cable, si se corta, dejaría aislada una región. Como historias no tienen nada en común. Estructuralmente son el mismo puñado de problemas planteados sobre el mismo tipo de objeto, y los algoritmos que los resuelven son intercambiables. Esa transferibilidad es la razón por la que la materia se enseña pronto y se usa en todas partes: en cuanto una situación se escribe como un grafo, un amplio catálogo de resultados queda disponible de golpe, y a ninguno le importa qué representaban originalmente los vértices.

Fíjate en lo que la imagen de la derecha no contiene. Los pueblos se han movido, las carreteras son rectas y nada registra que una sea el doble de larga que otra. Si esos datos importan para tu pregunta, debes volver a añadirlos explícitamente, como números sobre las aristas. Si no importan, desecharlos es precisamente lo que hace que el problema sea tratable.

Este artículo es un primer curso en una sola página: las definiciones en orden, los pequeños resultados sobre los que descansa todo lo demás, cómo se almacenan y recorren los grafos en código real, los problemas clásicos y un mapa honesto de qué preguntas puede responder un ordenador en segundos y cuáles no puede responder en absoluto. Cada sección enlaza con un artículo más profundo por si quieres saber más sobre ese tema en particular.

2. La definición, y lo que deja fuera a propósito

Casi todas las explicaciones divulgativas dicen que un grafo son «puntos unidos por líneas». Esa imagen es útil, y también es la razón por la que mucha gente se atasca unas semanas después: los puntos y las líneas son un dibujo del objeto, no el objeto. El objeto es un par de conjuntos. El libro de Diestel Graph Theory, la referencia estándar de posgrado, lo enuncia en su forma más limpia:

Un grafo es un par G = (V, E) de conjuntos tal que E ⊆ [V]², donde [V]² es el conjunto de todos los subconjuntos de 2 elementos de V.

Desglosado, eso dice cuatro cosas:

• V es un conjunto de objetos, llamados vértices (o nodos). No se supone absolutamente nada sobre ellos. Pueden ser ciudades, personas, átomos, páginas web o números enteros. La teoría nunca mira dentro de un vértice; solo necesita poder distinguir dos de ellos.
• E es un conjunto de subconjuntos de 2 elementos de V. Una arista es literalmente el conjunto {u, v}. No es una flecha ni una curva, y no lleva más información que el par que une.
• Como E es un conjunto, una arista está presente o ausente. No puede aparecer dos veces.
• Como cada arista tiene dos elementos distintos, ninguna arista une un vértice consigo mismo.

Esas dos últimas consecuencias no son reglas extra que alguien añadió; se desprenden directamente de la teoría de conjuntos, y un grafo que las cumple se llama simple. Permitir aristas repetidas o bucles significa cambiar la propia definición, que es lo que hacen los multigrafos en la sección 5.

Hay dos notaciones más que aparecen por todas partes. Se escribe V(G) y E(G) cuando hay varios grafos en juego. Y las dos medidas de tamaño tienen nombre: el número de vértices es el orden del grafo, y el número de aristas es su tamaño, abreviados en casi todos los textos de algoritmos como n = |V| y m = |E|.

Lo que la definición deja fuera es tan revelador como lo que incluye. No hay geometría, así que dos dibujos del mismo grafo son el mismo grafo aunque uno parezca una espiral y el otro una cuadrícula. No hay orden entre los vértices. No hay distancias, capacidades ni costes; eso viene de una función adicional, normalmente escrita w: E → ℝ, que se añade cuando un problema la necesita. El objeto desnudo está empobrecido a propósito, y esa pobreza es lo que hace que los teoremas sobre él se apliquen tan ampliamente. La guía complementaria sobre vértices y aristas desarrolla esta misma definición con más detalle.

3. Dónde empezó todo: siete puentes y un paseo imposible

La materia tiene fecha de nacimiento. En 1736 Leonhard Euler, entonces en la Academia de San Petersburgo, presentó un artículo titulado Solutio problematis ad geometriam situs pertinentis, «la solución de un problema relativo a la geometría de posición». El problema venía de la ciudad prusiana de Königsberg, hoy Kaliningrado. El río Pregel dividía la ciudad en cuatro masas de tierra, unidas por siete puentes, y los ciudadanos se entretenían con una pregunta: ¿se puede recorrer la ciudad cruzando cada puente exactamente una vez?

El primer movimiento de Euler es el movimiento del que trata todo este artículo. El tamaño y la forma de las masas de tierra son irrelevantes, la longitud de los puentes es irrelevante, y lo único que importa es qué masa de tierra se conecta con cuál, y cuántas veces. Quita el resto y te quedan cuatro objetos y siete conexiones, que los libros de texto modernos dibujan como un multigrafo con cuatro vértices y siete aristas.

Su argumento es lo bastante corto como para darlo completo. Supón que el paseo existe y toma cualquier masa de tierra que no sea ni su inicio ni su final. Cada vez que el paseo llega allí también debe salir, así que los puentes de esa masa de tierra se usan por parejas y su número debe ser par. En Königsberg las cuatro masas de tierra tenían 5, 3, 3 y 3 puentes, todos impares. Un paseo solo tiene dos extremos, así que como mucho dos masas de tierra pueden tener una cantidad impar. Cuatro son demasiadas, y tal paseo no existe.

Euler enunció también el recíproco, pero no lo demostró; esa laguna siguió abierta hasta que Carl Hierholzer dio una demostración constructiva, publicada póstumamente en 1873. El enunciado moderno es limpio: un grafo conexo tiene un paseo cerrado que usa cada arista exactamente una vez, un circuito euleriano, si y solo si todos los vértices tienen grado par, y uno abierto, un sendero euleriano, si y solo si exactamente dos vértices tienen grado impar. La historia completa está en la guía sobre el camino y circuito euleriano.

El siglo siguiente completó los fundamentos, desde los árboles generadores de Kirchhoff en 1847 hasta Sylvester tomando prestada de la química la palabra «grafo» en 1878 y el primer libro de texto de Kőnig en 1936. Esa historia se cuenta en la historia de la teoría de grafos.

4. El vocabulario y el primer teorema

El resto de este artículo usa un único ejemplo recurrente, un grafo con siete vértices y ocho aristas. Es lo bastante pequeño como para comprobar cada afirmación a mano y lo bastante grande como para resultar interesante.

V = {A, B, C, D, E, F, G}                          n = 7
E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,E},
      {D,E}, {D,F}, {F,G} }                        m = 8

Estos son los términos, cada uno definido solo a partir de los dos conjuntos:

• Adyacentes. Dos vértices unidos por una arista. B y D son adyacentes, A y D no.
• Incidente. Una arista es incidente a cada uno de sus dos extremos. La adyacencia relaciona un vértice con un vértice, la incidencia relaciona un vértice con una arista, y los principiantes confunden las dos continuamente.
• Vecindad. N(v), el conjunto de vértices adyacentes a v. Aquí N(D) = {B, E, F}.
• Grado. deg(v), el número de extremos de arista que se encuentran en v, que en un grafo simple es sencillamente |N(v)|. Aquí deg(B) = 3 y deg(G) = 1.
• Hoja y vértice aislado. Grado 1, como G, y grado 0. Los vértices aislados son legales, y son el dato que más a menudo se pierde cuando un grafo se construye a partir de una lista de aristas, porque una lista de aristas no tiene forma de mencionarlos.
• Grado mínimo y máximo. δ(G) y Δ(G), aquí 1 en G y 3 en B, C y D.

Con el grado definido, el primer teorema está a una línea de distancia. Los siete grados suman 2 + 3 + 3 + 3 + 2 + 2 + 1 = 16, exactamente el doble de las ocho aristas, y eso no es una casualidad de este grafo.

Esa técnica, contar una misma colección de dos maneras, se llama doble conteo, y es la herramienta de trabajo de la combinatoria elemental. El lema tiene un corolario que sorprende la primera vez: el número de vértices de grado impar es siempre par. Aquí son B, C, D y G, es decir, cuatro. La razón es aritmética: el total es par y los vértices de grado par aportan una cantidad par, así que los de grado impar deben aportar entre todos una cantidad par, lo que exige que sean un número par. En términos cotidianos, el número de personas en una sala que han estrechado la mano un número impar de veces es par. El argumento de Euler sobre Königsberg es este corolario aplicado a un paseo.

5. Las familias de grafos

La definición desnuda de la sección 2 es la más restrictiva. Todo problema real de modelado acaba necesitando una variación, y cada variación es un cambio concreto y con nombre en lo que se permite que sea una arista. Saber en qué familia estás decide qué algoritmos son siquiera aplicables, así que esto no es vocabulario por el vocabulario.

Los grafos simples son el caso por defecto: sin bucles, sin aristas repetidas, y todo resultado sin más matices de un libro de texto trata sobre ellos. Los multigrafos permiten aristas paralelas y los pseudografos permiten además bucles. Königsberg necesita de verdad un multigrafo, ya que dos de sus masas de tierra estaban unidas por dos puentes, y un bucle suma 2 al grado de su vértice porque ambos extremos se conectan allí. Consulta grafos simples frente a multigrafos.

Los grafos dirigidos, o dígrafos, sustituyen el par no ordenado {u, v} por el par ordenado (u, v), llamado arco, de modo que un dígrafo puede contener una dirección, ambas o ninguna, y el grado se divide en grado de entrada y grado de salida. Es el modelo correcto siempre que la relación no sea simétrica: calles de sentido único, «A sigue a B», «el módulo A importa el módulo B», «la tarea A debe terminar antes que la tarea B». Consulta grafos dirigidos frente a no dirigidos.

Los grafos ponderados añaden una función w que asigna un número a cada arista: kilómetros, minutos, precio, capacidad, similitud. Los algoritmos tienen opiniones firmes sobre esos números. El algoritmo de Dijkstra exige que no sean negativos, Bellman-Ford tolera los negativos pero no los ciclos negativos, y la búsqueda en anchura los ignora por completo, por eso ejecutar BFS sobre un grafo ponderado y llamar al resultado camino más corto es uno de los errores más comunes del código de principiante. Consulta grafos ponderados frente a no ponderados.

Los grafos bipartitos dividen el conjunto de vértices en dos partes y todas las aristas van de una a otra. Estudiantes y asignaturas, candidatos y empleos, compradores y productos: cualquier situación de emparejamiento a dos lados es bipartita. Un grafo es bipartito exactamente cuando no contiene ningún ciclo impar, y una sola búsqueda en anchura que colorea los vértices con dos colores lo decide en tiempo lineal.

Los grafos completos, escritos Kn, tienen todas las aristas posibles. Como una arista es una elección de 2 vértices entre n, el total es n(n-1)/2, así que K5 tiene 10 aristas y K100 tiene 4950. Ese es también el techo de cualquier grafo simple con n vértices, y es la referencia con la que se mide la densidad de un grafo.

Los árboles son grafos conexos sin ciclos, el tema de la sección 8. Los DAG, grafos acíclicos dirigidos, son dígrafos sin ciclos dirigidos, y tienen la forma de toda dependencia y todo calendario: las fórmulas de una hoja de cálculo, los objetivos de compilación, los commits de Git y las operaciones de una red neuronal son todos DAG, y el algoritmo que los pone en un orden válido es la ordenación topológica.

Hay una familia más que conviene conocer por su nombre: los grafos planares se pueden dibujar sin que se crucen aristas, lo que importa en el diseño de circuitos y en la coloración de mapas, y la sección 12 vuelve sobre ellos.

6. Paseos, senderos, caminos y ciclos

Cuatro palabras describen el movimiento a través de un grafo; en el habla cotidiana se usan indistintamente, pero significan cuatro cosas diferentes. Tenerlas claras evita una cantidad sorprendente de confusión más adelante, porque los teoremas se enuncian con la palabra precisa y la diferencia entre ellas suele ser todo el contenido del resultado.

• Un paseo es cualquier sucesión de vértices en la que los consecutivos son adyacentes. No hay nada prohibido. Un paseo puede cruzar la misma arista y volver al mismo vértice tantas veces como quiera.
• Un sendero es un paseo sin ninguna aristarepetida. Los vértices todavía pueden repetirse. El problema de los puentes de Euler pide un sendero que use todas las aristas, y por eso es un sendero euleriano y no un camino euleriano.
• Un camino es un paseo sin ningún vérticerepetido, lo que automáticamente prohíbe también las aristas repetidas. Cuando alguien dice «la ruta de A a G», se refiere a esto.
• Un ciclo es un camino cerrado: empieza y termina en el mismo vértice y no repite nada más. En el ejemplo, B, C, E, D, B es un ciclo de longitud 4, y A, B, C, A es un triángulo, un ciclo de longitud 3.

La longitud de cualquiera de ellos es su número de aristas, no su número de vértices, un error de uno en uno a punto de ocurrir. La distancia d(u, v) es la longitud de un camino más corto. Aquí d(A, G) = 4, a lo largo de A, B, D, F, G; la ruta A, C, E, D, F, G también llega pero usa cinco aristas, así que es un camino pero no uno de los más cortos. El diámetro es la mayor distancia entre cualquier par de vértices, una forma compacta de decir cuán extendida está una red.

Hay un hecho que se deduce de inmediato y se usa constantemente: si hay un paseo de u a v, hay un camino de u a v. Recorta el bucle entre dos visitas cualesquiera al mismo vértice y el resultado es un paseo más corto, así que la cirugía termina en uno sin vértices repetidos. Por eso los algoritmos de alcanzabilidad nunca consideran paseos.

7. Conectividad, componentes y las aristas que no puedes perder

Un grafo es conexo cuando cada vértice se puede alcanzar desde todos los demás. Cuando no lo es, se descompone en componentes conexas, que son los trozos maximales conexos internamente. La conectividad es lo primero que conviene comprobar en cualquier grafo que no hayas construido tú, porque una cantidad sorprendente de conjuntos de datos reales llegan en varios trozos, y la mayoría de los errores del tipo «el algoritmo devolvió infinito» son ese hecho descubierto por las malas.

Dentro de un grafo conexo, algunas partes de la estructura son más críticas que otras. Un puente es una arista cuya eliminación aumenta el número de componentes, y un vértice de corte, o punto de articulación, es un vértice cuya eliminación hace lo mismo. Son los puntos únicos de fallo, y encontrarlos es el primer análisis estándar de cualquier red cuya fiabilidad importe.

En el ejemplo recurrente las aristas DF y FG son puentes, y D y F son vértices de corte. Fíjate en lo que no es un puente: ninguna de las cinco aristas que están en un ciclo, porque un ciclo siempre ofrece un desvío. Esa es la regla general, y merece enunciarse como un hecho y no como una observación. Una arista es un puente exactamente cuando no está en ningún ciclo. La misma intuición explica por qué la redundancia de las redes reales se mide en ciclos: una segunda ruta es un ciclo que pasa por la primera.

En los grafos dirigidos la noción se divide en dos: un dígrafo es débilmente conexo si al ignorar la dirección de los arcos queda un grafo conexo, y fuertemente conexo si cada vértice alcanza a todos los demás siguiendo los arcos en el sentido correcto. El algoritmo de Tarjan de 1972 encuentra las componentes fuertemente conexas en tiempo lineal, y en un grafo de dependencias una de ellas con más de un vértice es precisamente una dependencia circular.

Computacionalmente, todo esto es barato. Un solo barrido en anchura o en profundidad etiqueta cada componente en O(n + m), y los puentes y vértices de corte salen de una única búsqueda en profundidad ampliada con los valores low-link de Tarjan, también en O(n + m). Rara vez hay motivo para no comprobar la conectividad antes de hacer cualquier otra cosa.

8. Árboles: el caso particular más útil

Un árbol es un grafo conexo sin ciclos. Es, con diferencia, el caso particular más importante de la materia, en parte porque los árboles aparecen por todas partes en informática y en parte porque muchísimos problemas difíciles se vuelven fáciles cuando la entrada resulta ser uno.

Lo notable de los árboles es cuántas descripciones que suenan distintas señalan los mismos objetos. Para un grafo G con n vértices, todas las siguientes afirmaciones son equivalentes, y cualquiera puede servir de definición:

1. G es conexo y no tiene ciclos.
2. G es conexo y tiene exactamente n - 1 aristas.
3. G no tiene ciclos y tiene exactamente n - 1 aristas.
4. Entre cada par de vértices hay exactamente un camino.
5. G es conexo, y eliminar cualquier arista lo desconecta, así que toda arista es un puente.
6. G no tiene ciclos, y añadir cualquier arista nueva crea exactamente un ciclo.

La equivalencia se demuestra como una cadena circular de implicaciones, desarrollada en la guía sobre los árboles en teoría de grafos. Hay dos consecuencias que conviene llevar siempre encima. El número de aristas está forzado, así que un «árbol» con 100 vértices y 120 aristas no es un árbol y algo anterior está mal. Y la unicidad de los caminos es la razón por la que los problemas sobre árboles son fáciles: no hay nada que buscar, porque solo existe una ruta.

Un bosque es un grafo acíclico que no tiene por qué ser conexo, es decir, una unión disjunta de árboles, y uno con n vértices y c componentes tiene exactamente n - c aristas. Un árbol generador de un grafo conexo es un subgrafo que es un árbol y contiene todos los vértices, el esqueleto más barato que mantiene el grafo de una pieza. Ambos recorridos producen uno gratis como efecto secundario, y cuando las aristas tienen pesos, encontrar el más ligero es el problema del árbol de expansión mínima .

Los árboles también existen en versión con raíz, en la que se distingue un vértice y quedan disponibles las palabras padre, hijo, antecesor, subárbol y profundidad, como en los sistemas de archivos, los árboles sintácticos y los montículos. Elegir la raíz es una decisión que se superpone al grafo, no una propiedad suya, y de eso trata precisamente el artículo sobre árboles con raíz.

9. Cómo se almacena un grafo en un ordenador

Todo lo anterior ha sido matemáticas. En el momento en que una máquina tiene que responder a una pregunta sobre un grafo, debes elegir cómo se dispone en memoria, y esa elección no es un detalle de implementación: cambia qué operaciones son baratas en factores de miles, y una representación mal elegida es la razón más común por la que un algoritmo correcto va demasiado lento. Hay tres disposiciones estándar, y almacenan exactamente la misma información.

La lista de aristas es el conjunto E escrito tal cual. Es compacta, es lo que te entrega un archivo CSV o una API, y es lo que quiere el algoritmo de Kruskal, ya que ordena las aristas por peso y nunca pregunta por un vértice concreto. Su debilidad es que «¿quiénes son los vecinos de D?» obliga a recorrer las m filas.

La matriz de adyacencia es una cuadrícula de n por n en la que la celda (u, v) vale 1 cuando la arista está presente. Comprobar si dos vértices dados son adyacentes es una sola consulta, y en los grafos no dirigidos la matriz es simétrica, así que almacena cada dato dos veces. El coste es el espacio: n al cuadrado celdas haya o no aristas. Es también la puerta de entrada a los métodos espectrales, en los que los valores propios de la matriz, o del laplaciano, estrechamente relacionado, revelan agrupamientos y conectividad, el tema de la teoría espectral de grafos en el aprendizaje automático.

La lista de adyacencia guarda, para cada vértice, la lista de sus vecinos. Iterar sobre los vecinos de v cuesta O(deg v), que es óptimo, y el espacio total es O(n + m). Es la opción por defecto en la práctica, y la disposición que suponen todos los recorridos que siguen.

Lo que decide la cuestión en la práctica es que las redes reales son dispersas: el número medio de vecinos se mantiene en las decenas por mucho que crezca la red, ya que los cruces tienen tres o cuatro calles y las personas tienen un número limitado de amigos. Para un grafo con un millón de vértices y cinco millones de aristas, la lista de adyacencia guarda unos diez millones de entradas, mientras que la matriz necesitaría un billón de celdas, varios terabytes para un grafo que por lo demás cabe holgadamente en memoria. Usa la matriz cuando el grafo sea pequeño, realmente denso o esté destinado al álgebra lineal; en otro caso, usa la lista de adyacencia. El tratamiento más profundo, incluidos los formatos de fila dispersa comprimida (CSR), está en representación de grafos.

Construir una lista de adyacencia a partir de una lista de aristas lleva cuatro líneas, y el comentario del medio es la parte en la que se equivocan los principiantes:

edges = [('A','B'), ('A','C'), ('B','C'), ('B','D'),
         ('C','E'), ('D','E'), ('D','F'), ('F','G')]

graph = {v: [] for v in 'ABCDEFG'}   # partir de V, para que sobrevivan los vértices aislados
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)               # omite esta línea en un grafo dirigido

Partir del conjunto de vértices y no de las aristas es lo que mantiene los vértices aislados dentro del grafo. Si construyes el diccionario sobre la marcha a partir de la lista de aristas, cualquier vértice sin aristas desaparece en silencio, n cambia y se rompe todo cálculo que divida por él.

10. Recorrido: en anchura y en profundidad

Casi todo algoritmo de grafos es un recorrido con algo de contabilidad añadida. Hay dos, se diferencian en una sola estructura de datos, y entender esa diferencia es la hora más rentable que un principiante puede dedicar a la materia. Ambos empiezan en un vértice, mantienen una colección de vértices descubiertos pero aún no procesados y repiten: sacar uno, mirar sus vecinos, añadir los nuevos. La búsqueda en anchura los saca en el orden en que entraron, usando una cola. La búsqueda en profundidad saca el añadido más recientemente, usando una pila o la pila de llamadas de una función recursiva. Esa única elección produce dos formas de exploración completamente distintas.

Aquí está la búsqueda en anchura completa, que devuelve el orden de visita, la distancia desde el inicio y el árbol de padres que permite reconstruir las rutas reales:

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()          # una cola: primero en entrar, primero en salir
        order.append(u)
        for v in graph[u]:
            if v not in dist:        # aún no descubierto
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return order, dist, parent

order, dist, parent = bfs(graph, 'A')
# order  ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# dist   {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}

La propiedad importante está en el diccionario dist . Como BFS termina una capa entera antes de empezar la siguiente, la primera vez que alcanza un vértice lo ha hecho con el menor número posible de aristas, así que BFS resuelve el problema del camino más corto en grafos no ponderados en O(n + m). Recurrir a Dijkstra cuando todas las aristas cuestan lo mismo es trabajo desperdiciado.

La búsqueda en profundidad es el mismo esqueleto con una pila en lugar de una cola:

def dfs(graph, start):
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()              # una pila: último en entrar, primero en salir
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]): # invertido, para que el primer vecino se tome primero
            if v not in seen:
                stack.append(v)
    return order

dfs(graph, 'A')   # ['A', 'B', 'C', 'E', 'D', 'F', 'G']

DFS no te da distancias, y la salida útil es el orden en que termina los vértices, no el orden en que los empieza. Ese orden de finalización es la base sobre la que se construyen la ordenación topológica, la detección de ciclos, las componentes fuertemente conexas y la búsqueda de puentes, siguiendo el artículo de Tarjan de 1972 que convirtió la búsqueda en profundidad de una técnica en una caja de herramientas.

Una comparación más completa de las dos, incluidos los errores a los que invita cada una, está en BFS frente a DFS.

11. Los problemas clásicos y sus algoritmos

Con el recorrido dominado, el catálogo estándar queda al alcance. Cada uno de estos es una pregunta que la gente se hace de verdad sobre redes reales, y cada uno tiene un algoritmo con nombre propio.

Caminos más cortos. Sin pesos, BFS lo resuelve. Con pesos no negativos, el algoritmo de Dijkstra, publicado en una nota de tres páginas en 1959, fija los vértices en orden creciente de distancia y se ejecuta en O(m + n log n) con una buena cola de prioridad. Con pesos negativos, la suposición central de Dijkstra falla y necesitas Bellman-Ford, que relaja cada arista n-1 veces en O(nm) y, de regalo, detecta ciclos negativos. Para todos los pares a la vez, Floyd-Warshall lo hace en O(n3) con tres bucles anidados, y cuando tienes un objetivo y una estimación razonable de la distancia restante, la búsqueda A* la usa para examinar solo una fracción del grafo. El árbol de decisión completo está en algoritmos de caminos más cortos.

Árboles de expansión mínima. Encuentra el conjunto de aristas más barato que mantiene conexo un grafo ponderado. El algoritmo de Kruskal ordena las aristas y añade cualquiera que no cierre un ciclo, usando una estructura union-find para comprobarlo en tiempo casi constante; el de Prim hace crecer un único árbol hacia fuera, tomando siempre la arista más barata que sale de él. Ambos son voraces, ambos son demostrablemente óptimos y ambos se ejecutan en O(m log n). Es el algoritmo que hay detrás de tender cable y fibra al mínimo coste, y aparece también dentro de los métodos de agrupamiento.

Orden y flujo. Dado un DAG de dependencias, la ordenación topológica produce un orden en el que cada tarea va después de aquello de lo que depende, en O(n + m), y falla exactamente cuando existe un ciclo. Dadas unas tuberías con capacidades, el flujo máximo pregunta cuánto puede moverse de una fuente a un sumidero; formalizado por Ford y Fulkerson en 1956, modela el tráfico, el ancho de banda, las cadenas de suministro y, mediante una reducción estándar, el emparejamiento bipartito. Consulta flujo en redes, flujo máximo y corte mínimo.

Coloración. Etiqueta los vértices de modo que ningún par de adyacentes comparta etiqueta, usando el menor número de etiquetas posible. Ese número es el número cromático, y modela los calendarios de exámenes, la asignación de frecuencias y la asignación de registros. A diferencia de todo lo anterior, este problema es NP-difícil y en la práctica se recurre a heurísticas. Consulta el problema de coloración de grafos.

Recorridos completos. Un ciclo hamiltoniano visita cada vértice exactamente una vez, y el problema del viajante pide el más barato. Parece una pequeña variación de la pregunta de Euler de 1736, que se resuelve en tiempo lineal, y es uno de los problemas más difíciles del catálogo. Su primo práctico, enrutar una flota desde un depósito con límites de capacidad, es el problema de enrutamiento de vehículos.

12. Cinco resultados que conviene conocer por su nombre

Un primer curso es en parte un conjunto de algoritmos y en parte un conjunto de resultados que moldean la forma de pensar sobre los objetos. El lema del apretón de manos de la sección 4 es el primero de ellos. Estos cinco aparecen con la misma frecuencia, en entrevistas, en artículos y en la conversación, y cada uno se puede enunciar en una frase.

El criterio de Euler para recorrer todas las aristas (1736, completado por Hierholzer en 1873)

Un grafo conexo tiene un sendero cerrado que usa cada arista exactamente una vez si y solo si todos los vértices tienen grado par, y uno abierto si y solo si exactamente dos vértices tienen grado impar. Es el tipo de teorema valioso: convierte una búsqueda sobre un espacio enorme de rutas en una comprobación que puedes hacer contando, en tiempo lineal.

La fórmula de Euler para grafos planares (1758)

Dibuja un grafo planar conexo sin cruces y sea f el número de caras, contando la región exterior no acotada. Entonces

n - m + f = 2

El ejemplo recurrente, dibujado como en las figuras, tiene n = 7, m = 8 y tres caras: el triángulo ABC, el cuadrilátero BCED y la región exterior, y en efecto 7 - 8 + 3 = 2. El corolario tiene consecuencias reales: todo grafo planar simple con al menos tres vértices cumple m ≤ 3n - 6, así que los grafos planares siempre son dispersos, y K5 , con sus 5 vértices y 10 aristas, no puede ser planar, ya que 3n - 6 vale 9. El teorema de Kuratowski de 1930 completa el cuadro: un grafo es planar exactamente cuando no contiene ninguna subdivisión de K5 ni de K3,3. Hopcroft y Tarjan demostraron en 1974 que la planaridad se puede comprobar en tiempo lineal.

El teorema de los cuatro colores (Appel y Haken, 1976)

Todo grafo planar se puede colorear correctamente con cuatro colores como máximo, así que ningún mapa necesita más de cuatro colores para que los países que comparten frontera se distingan. Francis Guthrie planteó la pregunta en 1852 y resistió todo intento de demostración durante 124 años. El argumento final redujo el problema a un conjunto finito de configuraciones y las comprobó por ordenador, lo que desató un auténtico debate filosófico sobre qué es una demostración; fue simplificado en 1997 por Robertson, Sanders, Seymour y Thomas, y verificado formalmente en Coq por Georges Gonthier en 2005. Fíjate en la asimetría: cuatro colores bastan siempre, pero decidir si bastan tres es NP-completo.

El teorema de Kőnig (1931)

En un grafo bipartito, el tamaño de un emparejamiento máximo es igual al tamaño de un recubrimiento mínimo por vértices. Un emparejamiento es un conjunto de aristas sin extremos compartidos, una forma de asignar personas a empleos; un recubrimiento por vértices es un conjunto de vértices que toca todas las aristas. Dos problemas de optimización aparentemente sin relación tienen la misma respuesta, que es la primera dualidad que conocen la mayoría de los estudiantes, y es lo que hace que el emparejamiento máximo sea computable en tiempo polinómico. En grafos generales la igualdad falla y el recubrimiento mínimo por vértices es NP-difícil.

El teorema de flujo máximo y corte mínimo (Ford y Fulkerson, 1956)

En cualquier red de flujo, el flujo máximo de la fuente al sumidero es igual a la capacidad total del corte más pequeño que los separa: lo máximo que puedes hacer pasar es exactamente lo que permite el cuello de botella más estrecho. Es de nuevo la dualidad, en su forma más citable, que convierte una maximización sobre todos los flujos en una minimización sobre todos los cortes. Está en la base de la segmentación de imágenes, la selección de proyectos y el análisis de fiabilidad, y el teorema de Kőnig se obtiene de él como caso particular.

13. Qué es fácil, qué es difícil y por qué importa

Lo más importante en la práctica que un principiante puede aprender sobre los grafos no es un algoritmo. Es que dos problemas pueden enunciarse casi con las mismas palabras y estar a lados opuestos de una enorme brecha computacional. Encontrar el camino más corto entre dos vértices lleva milisegundos en un grafo con millones de vértices; encontrar el camino simple más largo entre esos mismos dos es NP-difícil y desesperado a partir de unas pocas docenas. Decidir si un grafo tiene un sendero cerrado que use cada arista una vez es una comprobación de grados en tiempo lineal; decidir si tiene un ciclo que pase una vez por cada vértice es NP-completo. Decidir si bastan dos colores es un solo BFS; decidir si bastan tres es NP-completo.

El enunciado formal es que una gran familia de problemas de grafos es NP-completa, una noción introducida por Cook en 1971 y a la que Richard Karp dio su primer catálogo sustancial en 1972, cuya famosa lista de 21 problemas está dominada por problemas de grafos: clique, recubrimiento por vértices, circuito hamiltoniano, número cromático, conjunto de arcos de retroalimentación y más. No se conoce ningún algoritmo de tiempo polinómico para ninguno de ellos, y uno para cualquiera de ellos daría uno para todos. Nadie espera que eso ocurra.

La consecuencia práctica no es la desesperación, sino un cambio de pregunta. Cuando un problema cae en la columna de la derecha, dejas de pedir el óptimo y eliges entre cuatro estrategias honestas:

• Aceptar una aproximación. Para el TSP métrico, el algoritmo de Christofides de 1976 garantiza en tiempo polinómico un recorrido de como mucho 1,5 veces el óptimo.
• Usar una heurística y medirla. La búsqueda local, como 2-opt o el recocido simulado, suele quedarse a un par de puntos porcentuales del óptimo con miles de ciudades, sin ninguna garantía.
• Aprovechar la estructura de tus instancias. Difícil en general no significa difícil para ti: la coloración es fácil en grafos cordales, muchos problemas son fáciles en árboles y en grafos de anchura de árbol pequeña, y las redes de carreteras tienen una geometría que los algoritmos de enrutamiento especializados explotan sin piedad.
• Resolver instancias más pequeñas de forma exacta. Los resolvedores de programación entera demuestran de forma rutinaria la optimalidad de instancias del TSP con miles de ciudades. Exponencial no significa imposible, significa que el techo llega rápido.

Una advertencia: «NP-difícil» describe los peores casos a medida que crece la entrada, no es un veredicto sobre tu problema concreto. Un tratamiento más completo del coste de cada algoritmo está en algoritmos de grafos y complejidad.

14. Dónde aparecen realmente los grafos

Afirmar que la teoría de grafos está en todas partes es fácil y merece la pena demostrarlo. Aquí está dónde el material de este artículo está trabajando ahora mismo, en el dispositivo en el que lo estás leyendo.

Navegación. Toda app de rutas modela la red de carreteras como un grafo dirigido ponderado, con los cruces como vértices y los tramos de carretera como arcos ponderados por el tiempo de viaje previsto. La consulta es un camino más corto y el algoritmo es un descendiente muy afinado de Dijkstra y A*, que usa jerarquías precalculadas para que una ruta continental toque unos pocos miles de vértices en lugar de decenas de millones. Las calles de sentido único son la razón de que el grafo deba ser dirigido; el tráfico en directo es la razón de que los pesos cambien minuto a minuto.

Búsqueda y plataformas sociales. La web es un grafo dirigido de páginas y enlaces, y PageRank, descrito por Brin y Page en 1998, puntúa una página según la probabilidad de que un navegante aleatorio que sigue enlaces acabe en ella, lo que es un cálculo de vectores propios sobre la estructura de adyacencia. En las plataformas sociales las personas son vértices y las relaciones son aristas: el estudio de las cartas de Milgram de 1967 dio lugar a los populares «seis grados de separación», y un análisis de 2012 del grafo completo de Facebook situó la distancia media entre dos usuarios en 4,74. La detección de comunidades, la recomendación de amigos y la estimación de influencia son todos cálculos estándar de grafos ejecutados a gran escala.

Ingeniería de software. Los sistemas de compilación, los gestores de paquetes y los motores de hojas de cálculo mantienen un DAG y lo ordenan topológicamente. El historial de control de versiones es un DAG de commits, y una fusión es una pregunta sobre antecesores comunes. Los compiladores construyen grafos de flujo de control para optimizar y grafos de interferencia para asignar registros, donde asignar registros es literalmente colorear un grafo, y la eliminación de código muerto es una consulta de alcanzabilidad. Consulta la teoría de grafos en la ingeniería de software.

Logística. El enrutamiento de repartos es el problema de enrutamiento de vehículos, la ubicación de almacenes es localización de instalaciones y las cadenas de suministro son redes de flujo con capacidades. Aquí la diferencia entre un algoritmo bueno y uno malo se mide en combustible y nóminas, y el campo que la estudia es la investigación operativa.

Ciencia y aprendizaje automático. Una molécula es un grafo de átomos y enlaces, y buscar en una base de datos química es isomorfismo de subgrafos. El ensamblaje de genomas reconstruye una secuencia encontrando un camino euleriano en un grafo de De Bruijn, con lo que el criterio de Euler de 1736 se gana el sueldo 280 años después. El agrupamiento espectral divide los datos usando los vectores propios de un laplaciano de grafo, y las redes neuronales de grafos generalizan la convolución a estructuras irregulares pasando mensajes a lo largo de las aristas. Las redes eléctricas y de telecomunicaciones se analizan en busca de puentes y vértices de corte porque es ahí donde empiezan los fallos en cascada. Un panorama más amplio está en aplicaciones de la teoría de grafos.

15. Errores que los principiantes cometen sin falta

Estos son los errores que aparecen una y otra vez en el código de estudiantes, en entrevistas y en fallos en producción. Todos son fáciles de evitar una vez que los has visto con nombre.

• Perder los vértices aislados. Construir el grafo a partir de una lista de aristas significa que cualquier vértice sin aristas nunca aparece. El orden n cambia en silencio, las medias salen mal y el recuento de componentes se queda corto. Construye primero el conjunto de vértices.
• Marcar como visitado demasiado tarde en BFS. Marca un vértice cuando lo metes en la cola, no cuando lo sacas. Marcarlo al sacarlo permite que el mismo vértice entre en la cola una vez por cada arista incidente, lo que convierte un algoritmo lineal en un problema de memoria.
• Ejecutar BFS sobre un grafo ponderado. BFS minimiza el número de aristas, no su peso total. En un grafo donde una ruta de dos aristas cuesta 100 y una de cinco aristas cuesta 5, BFS devuelve con toda seguridad la cara. Los grafos ponderados necesitan Dijkstra.
• Ejecutar Dijkstra con pesos negativos. Dijkstra supone que, una vez fijado un vértice, no puede aparecer más tarde una ruta más barata hasta él. Una arista negativa rompe esa suposición y la salida es incorrecta en silencio, en lugar de dar un error. Usa Bellman-Ford.
• Contar la longitud de un camino en vértices. La longitud es el número de aristas, así que un camino que pasa por cinco vértices tiene longitud 4. Esta es la fuente de buena parte de los errores de uno en uno en el código de caminos más cortos.
• Ignorar a qué familia pertenece el grafo. Un algoritmo correcto en grafos no dirigidos puede ser incorrecto en silencio en los dirigidos, y un resultado demostrado para grafos simples puede fallar en un multigrafo. Comprueba la familia antes de recurrir al algoritmo.
• Suponer que el grafo es conexo. Los datos reales llegan en trozos. Comprueba el número de componentes antes de fiarte de cualquier distancia, diámetro o media.
• Recurrir demasiado hondo en DFS. Un DFS recursivo sobre un camino de un millón de vértices necesita un millón de marcos de pila. Escribe la versión iterativa cuando la entrada pueda ser grande.
• Añadir solo una dirección en un grafo no dirigido. Una arista no dirigida debe aparecer en ambas listas de adyacencia. Omitir el segundo append produce un grafo que parece correcto en un dibujo y se comporta como un dígrafo en todos los recorridos.
• Creerse el dibujo. Dos aristas que se cruzan en una imagen no significan nada. Solo importan los conjuntos, y por eso «¿es planar este grafo?» es una pregunta real y no algo que se resuelve entornando los ojos ante un diagrama.
• Suponer que n - 1 aristas significa árbol. Solo lo significa junto con la conexión, o con la aciclicidad. Un triángulo más un vértice aislado tiene 4 vértices y 3 aristas y no es un árbol.

16. Hacia dónde seguir

El siguiente paso útil es construir un grafo y ejecutar algo sobre él, en vez de leer más definiciones. Introduce el ejemplo recurrente en el visualizador interactivo, ejecuta la búsqueda en anchura desde A y observa cómo se llenan las capas, luego ejecuta la búsqueda en profundidad desde el mismo vértice y compara el orden. Noventa segundos de eso hacen lo que ninguna cantidad de prosa consigue.

Después, la secuencia natural es el orden de este artículo: vocabulario, recorrido, caminos más cortos ponderados, árboles de expansión y luego los problemas más difíciles. La hoja de ruta de teoría de grafos expone ese camino con un calendario, y las lecciones estructuradas lo siguen de forma interactiva. Para las entrevistas técnicas, la guía de teoría de grafos para entrevistas de programación cubre los patrones que realmente aparecen, junto con la chuleta de algoritmos.

En cuanto a libros de texto: el Introduction to Graph Theory de West es el curso de grado estándar en forma de libro, el Graph Theory de Diestel es la referencia de posgrado y la fuente de la definición de la sección 2, y los capítulos de grafos de Cormen, Leiserson, Rivest y Stein siguen siendo el tratamiento más claro de las implementaciones. Una comparación más completa, incluidos cursos y series de vídeo, está en los mejores recursos para aprender teoría de grafos.

17. Glosario

Todos los términos usados arriba, en un solo lugar.

19. Referencias

Las definiciones, teoremas, fechas y cotas de complejidad anteriores proceden de estas fuentes, enumeradas en orden cronológico.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publicado en 1741), 128 a 140. El artículo de los puentes de Königsberg.
2. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4, 109 a 140. La fórmula de los poliedros detrás de n - m + f = 2.
3. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 a 508.
4. Hierholzer, C. (1873). "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 a 32.
5. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. El primer uso moderno de la palabra «grafo».
6. Cayley, A. (1889). "A theorem on trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 a 378.
7. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 a 283.
8. König, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 a 119.
9. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
10. Ford, L. R. y Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 a 404.
11. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society 7(1), 48 a 50.
12. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal 36(6), 1389 a 1401.
13. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269 a 271.
14. Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM 5(6), 345.
15. Held, M. y Karp, R. M. (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 a 210.
16. Milgram, S. (1967). "The small world problem." Psychology Today 2(1), 60 a 67.
17. Cook, S. A. (1971). "The complexity of theorem-proving procedures." Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151 a 158.
18. Karp, R. M. (1972). "Reducibility among combinatorial problems." En Complexity of Computer Computations, 85 a 103. Nueva York: Plenum Press.
19. Tarjan, R. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 a 160.
20. Hopcroft, J. y Tarjan, R. (1974). "Efficient planarity testing." Journal of the ACM 21(4), 549 a 568.
21. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Informe 388, Carnegie Mellon University.
22. Appel, K. y Haken, W. (1977). "Every planar map is four colorable." Illinois Journal of Mathematics 21(3). Parte I, 429 a 490; Parte II, con J. Koch, 491 a 567.
23. Fredman, M. L. y Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM 34(3), 596 a 615.
24. Brin, S. y Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 a 7), 107 a 117.
25. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall.
26. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
27. Gonthier, G. (2008). "Formal proof: the four-color theorem." Notices of the American Mathematical Society 55(11), 1382 a 1393.
28. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, Massachusetts: MIT Press.
29. Backstrom, L., Boldi, P., Rosa, M., Ugander, J. y Vigna, S. (2012). "Four degrees of separation." Proceedings of the 4th Annual ACM Web Science Conference, 33 a 42.
30. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. Fuente de la definición citada en la sección 2.