Ciclos en grafos y detección de ciclos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Paseos, senderos, caminos y ciclos

Un ciclo es una ruta por un grafo que vuelve a donde empezó sin reutilizar nada por el camino. Parece sencillo, pero «ruta» puede significar cuatro cosas distintas, y la mayor parte de la confusión sobre los ciclos viene de mezclarlas. Solo se diferencian en lo que puede repetirse.

• Un paseo es una secuencia de vértices en la que cada par consecutivo está unido por una arista. Tanto los vértices como las aristas pueden repetirse. Su longitud es el número de aristas que usa, contadas con repetición.
• Un sendero es un paseo que nunca usa dos veces la misma arista. Los vértices sí pueden repetirse.
• Un camino es un paseo que nunca visita dos veces el mismo vértice, así que tampoco puede repetir una arista.
• Un paseo es cerrado cuando termina donde empezó. Un sendero cerrado también se llama circuito, y un ciclo es un sendero cerrado de longitud positiva cuyo único vértice repetido es aquel en el que empieza y termina.

No todos los libros de texto usan estas palabras del mismo modo. Algunos dicen «camino» para lo que aquí se llama paseo, y otros dicen «circuito» para lo que aquí se llama ciclo. Las ideas son estables aunque los nombres no lo sean, así que cuando leas un teorema, comprueba a cuál se refiere. En un grafo simple un ciclo necesita al menos tres vértices. En un multigrafo, un lazo es un ciclo de longitud 1 y dos aristas paralelas forman un ciclo de longitud 2.

Un solo grafo no dirigido sostiene la mayor parte del artículo. Tiene ocho vértices y diez aristas: un triángulo A, B, C arriba, dos cuadrados B, C, E, D y D, E, G, F apilados debajo y un vértice H que cuelga de G.

V = {A, B, C, D, E, F, G, H}                          8 vértices
E = {AB, BC, CA, BD, CE, DE, DF, EG, FG, GH}          10 aristas

Dos hechos sobre los paseos cerrados se usan una y otra vez. Primero, un paseo cerrado no tiene por qué contener un ciclo: A, B, A es cerrado, pero solo sale por una arista y vuelve por esa misma arista. Segundo, un sendero cerrado de longitud positiva siempre contiene un ciclo. Si repite algún vértice en medio, córtalo ahí en dos senderos cerrados más cortos y repite el argumento con cualquiera de ellos; el proceso termina en un sendero cerrado sin vértices repetidos, que es un ciclo. La sección 8 necesita una variante del mismo argumento para paseos de longitud impar.

2. Cintura, circunferencia y grafos sin ciclos

La cintura de un grafo es la longitud de su ciclo más corto, y la circunferencia es la longitud del más largo. El ejemplo tiene seis ciclos en total, de longitudes 3, 4, 4, 5, 6 y 7, así que su cintura es 3 y su circunferencia es 7. El ciclo más largo, A, B, D, F, G, E, C, pasa por todos los vértices excepto H, que solo tiene una arista y por tanto no puede estar en ningún ciclo.

Un grafo sin ciclos se llama acíclico. Un grafo no dirigido acíclico es un bosque, y un bosque conexo es un árbol. Un bosque con n vértices y k componentes tiene exactamente n − k aristas, así que contar aristas da la prueba de ciclos más rápida que existe:

Un grafo con n vértices, m aristas y k componentes contiene un ciclo si y solo si m > n − k. En particular, todo grafo con al menos tantas aristas como vértices tiene un ciclo.

En el ejemplo se cumple 10 > 8 − 1, así que debe contener un ciclo antes de que nadie lo busque. También funciona una condición de grado: si todo vértice tiene grado al menos 2, el grafo tiene un ciclo, y de hecho uno de longitud al menos δ + 1, donde δ es el grado mínimo. La demostración es un clásico. Toma un camino lo más largo posible v0, v1, …, vℓ. Todo vecino de v0 está en el camino, porque de lo contrario el camino podría alargarse. v0 tiene al menos δ vecinos en él, así que el más lejano es como mínimo vδ, y la arista de vuelta hasta él cierra un ciclo de longitud al menos δ + 1, una observación que aparece en el artículo de Dirac de 1952. Esto se comprobó por fuerza bruta en todos los grafos de hasta seis vértices.

En un grafo dirigido, un ciclo debe seguir las flechas, y un grafo dirigido acíclico se llama DAG. Los DAG son exactamente los grafos dirigidos cuyos vértices pueden ponerse en fila con todas las flechas apuntando hacia delante, que es lo que produce una ordenación topológica. Ten en cuenta que un DAG puede tener muchas aristas: la prueba de conteo de aristas anterior solo vale para grafos no dirigidos.

Encontrar la cintura es más difícil que encontrar algún ciclo. Ejecutar una búsqueda en anchura desde cada vértice y examinar cada arista fuera del árbol que encuentre da la cintura en tiempo O(nm) y el artículo de 1978 de Itai y Rodeh sobre circuitos mínimos da esta cota, junto con un método más rápido para obtener un ciclo como mucho una arista más largo que el más corto.

3. Detectar un ciclo en un grafo no dirigido

Si solo necesitas un sí o un no, el conteo de aristas lo resuelve: calcula las componentes y compara m con n − k. Normalmente quieres más, es decir, un ciclo concreto que puedas mostrar a alguien. Un ciclo es un certificado: cualquiera puede comprobarlo arista por arista, y demuestra la respuesta sin pedirle a nadie que confíe en tu programa. La búsqueda en profundidad produce uno casi gratis.

El hecho clave es que una búsqueda en profundidad en un grafo no dirigido clasifica cada arista en uno de dos tipos. Una arista del árbol lleva a un vértice visto por primera vez. Una arista de retroceso lleva a un vértice que ya está en el camino de bajada, un ancestro del actual. No hay otros tipos, así que el grafo tiene un ciclo exactamente cuando la búsqueda encuentra una arista de retroceso, y el ciclo es esa arista de retroceso más el camino del árbol sobre el que salta.

def find_cycle_undirected(vertices, edges):
    """Devuelve los vértices de un ciclo, en orden, o None si el grafo es un bosque."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent = {}                                   # vértice -> (vértice padre, id de la arista)
    for root in vertices:                         # una búsqueda por componente
        if root in parent:
            continue
        parent[root] = (None, None)
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i == parent[u][1]:             # la arista por la que llegamos, no es un ciclo
                    continue
                if v in parent:                   # arista de retroceso u-v: sube de u hasta v
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]][0])
                    return cycle[::-1]
                parent[v] = (u, i)
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return None

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
print(find_cycle_undirected(V, E))
# ['A', 'B', 'C']
print(find_cycle_undirected(V, ['AB', 'BC', 'CE', 'DE', 'DF', 'FG', 'GH']))
# None
print(find_cycle_undirected('xy', ['xy', 'xy']))
# ['x', 'y']

Tres detalles hacen que esto sea correcto y no casi correcto. La búsqueda recuerda la arista por la que llegó y salta solo esa arista; sin ese salto, cada arista parecería un ciclo de longitud 2, de ida y vuelta inmediata. Saltar por identidad de arista en lugar de por «el vecino que es mi padre» mantiene el código correcto en multigrafos, donde una arista doble sí es un ciclo de longitud 2, como muestra la tercera llamada. El bucle exterior inicia una búsqueda por componente, porque un ciclo puede estar en cualquiera de ellas. Y la pila es explícita, así que un camino largo no puede desbordar el límite de recursión de Python.

Tomando los vecinos en orden alfabético, la búsqueda desde A baja por A, B, C y en C encuentra la arista de vuelta a A. A ya está visitado y la arista no es aquella por la que llegó la búsqueda, así que el código sube por los punteros al padre desde C hasta A y devuelve el triángulo. Si hubiera seguido, la búsqueda habría continuado por E, D, F, G, H, un único camino por los ocho vértices, y habría encontrado dos aristas de retroceso más, D–B y G–E. Siete aristas del árbol más tres aristas de retroceso suman las diez.

El tiempo de ejecución trae una agradable ventaja. Antes de la primera arista de retroceso, cada entrada de adyacencia que lee la búsqueda es o bien una arista del árbol, y de esas hay como mucho n − 1, o bien la arista de vuelta a un padre, y de esas hay como mucho n − 1 también. Así que la búsqueda en sí lee como mucho 2n − 1 entradas antes de encontrar un ciclo o terminar, tenga el grafo las aristas que tenga. Esa cota se comprobó contando en 4.000 grafos aleatorios. Leer la entrada para construir las listas de adyacencia sigue costando O(V + E), pero la búsqueda no.

4. Union-find: ciclos arista a arista

A veces las aristas llegan una a una y la pregunta es qué arista crea el primer ciclo. Una estructura union-find responde a eso sin ninguna búsqueda. Mantiene los vértices en grupos, un grupo por cada componente construida hasta el momento. Una arista entre dos grupos distintos los fusiona. Una arista cuyos dos extremos ya están en el mismo grupo une dos vértices que ya estaban conectados, así que, junto con el camino que ya existía entre ellos, cierra un ciclo.

def first_cycle_edge(vertices, edges):
    """Añade las aristas de una en una; devuelve la primera que cierra un ciclo, o None."""
    root = {v: v for v in vertices}
    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]               # reducción del camino a la mitad
            x = root[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                              # u y v ya estaban conectados
            return u + v
        root[ru] = rv
    return None

print(first_cycle_edge('ABCDEFGH', ['AB', 'BD', 'DF', 'FG', 'GH', 'BC', 'CE', 'EG', 'DE', 'CA']))
# EG

En este orden, las cinco primeras aristas forman el camino A, B, D, F, G, H, y luego B–C y C–E le cuelgan dos vértices más. Cuando E–G llega, E y G ya comparten raíz, y el ciclo que cierra es B, C, E, G, F, D, de seis aristas. Es exactamente la prueba que el algoritmo de Kruskal aplica a cada arista antes de añadirla a un árbol de expansión mínima.

Union-find te dice qué arista cierra un ciclo, no por dónde pasa el ciclo. Para producir el ciclo aún necesitas el camino entre los dos extremos en el bosque construido hasta el momento, que se encuentra con una búsqueda corta sobre las aristas aceptadas. Y union-find solo funciona con grafos no dirigidos. En el grafo dirigido con las flechas A→B, B→C y A→C, la tercera flecha une dos vértices que ya están en un mismo grupo, y sin embargo no hay ningún ciclo dirigido: seguir las flechas nunca lleva de vuelta a A.

5. Grafos dirigidos: tres colores

En un grafo dirigido la prueba no dirigida da respuestas incorrectas. Toma seis tareas con estas dependencias:

A → B    A → C    B → D    C → D    C → E    E → F

Una búsqueda en profundidad desde A llega a D a través de B. Más tarde, al explorar C, encuentra la flecha C→D y halla D ya visitado. Una simple comprobación de «ya visitado» lo considera un ciclo, pero no lo hay: A→B→D y A→C→D son dos rutas al mismo lugar, no una ruta que vuelve. En 6.000 grafos dirigidos aleatorios, la comprobación simple informó de un ciclo en 1.320 grafos que no tenían ninguno.

La solución es recordar no solo si un vértice fue visitado, sino si su búsqueda sigue en curso. Cada vértice recibe uno de tres colores:

• BLANCO: aún no alcanzado.
• GRIS: alcanzado, y su búsqueda no ha terminado. Los vértices grises son exactamente el camino actual desde la raíz hasta el vértice que se está explorando.
• NEGRO: terminado. Todo lo alcanzable desde él ya se ha explorado, y ahí no se encontró ningún ciclo.

Una búsqueda en profundidad dirigida clasifica las aristas en cuatro tipos: aristas del árbol hacia vértices blancos, aristas de retroceso hacia ancestros grises, aristas de avance hacia descendientes negros y aristas cruzadas hacia vértices negros de otra rama o de una búsqueda anterior. Solo una arista de retroceso cierra un ciclo, porque solo un vértice gris tiene garantizado alcanzar el actual. Eso da el teorema clásico: un grafo dirigido tiene un ciclo si y solo si una búsqueda en profundidad encuentra una arista de retroceso, lo que equivale a encontrar una flecha hacia un vértice gris. El propio camino gris es el certificado.

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle_directed(graph):
    """Devuelve un ciclo dirigido como lista de vértices, o None si el grafo es un DAG."""
    color = {v: WHITE for v in graph}
    for root in graph:
        if color[root] != WHITE:
            continue
        color[root] = GRAY
        path = [root]                             # los vértices GRAY (grises), en orden
        stack = [iter(graph[root])]
        while stack:
            for v in stack[-1]:
                if color[v] == GRAY:              # arista de retroceso: v está en el camino actual
                    return path[path.index(v):]
                if color[v] == WHITE:
                    color[v] = GRAY
                    path.append(v)
                    stack.append(iter(graph[v]))
                    break
            else:                                 # aristas salientes agotadas: se termina el vértice
                color[path.pop()] = BLACK
                stack.pop()
    return None

dag = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': []}
print(find_cycle_directed(dag))
# None
dag['F'].append('C')                              # una arista más: F -> C
print(find_cycle_directed(dag))
# ['C', 'E', 'F']

En las seis tareas, D se vuelve negro antes de que se explore C, así que C→D es una arista cruzada y se ignora correctamente. Añade una flecha, F→C, y el panorama cambia: la búsqueda recorre C, E, F, todos grises, y la nueva flecha apunta de vuelta a C, que sigue gris. El camino gris de C a F se devuelve como el ciclo. Un lazo v→v también se maneja bien: v está gris cuando se lee su propia flecha, y el ciclo devuelto es simplemente [v].

6. Algoritmo de Kahn: los ciclos como una ordenación topológica atascada

El segundo método estándar no necesita recursión ni colores. Un vértice con grado de entrada 0 no depende de nada, así que puede ir primero sin riesgo. El algoritmo de Kahn, publicado en 1962, elimina repetidamente uno de esos vértices y reduce el grado de entrada de sus sucesores. Si se eliminan todos los vértices, el orden de eliminación es un orden topológico y el grafo es un DAG. Si el proceso se detiene antes, el grafo tiene un ciclo.

from collections import deque

def kahn(graph):
    """Orden topológico si el grafo es un DAG; si no, (None, un ciclo)."""
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    ready = deque(v for v in graph if indeg[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    if len(order) == len(graph):
        return order, None
    left = {v for v in graph if indeg[v] > 0}     # cada uno de ellos tiene un predecesor en left
    pred = {v: u for u in left for v in graph[u] if v in left}
    v, seen = next(iter(sorted(left))), []
    while v not in seen:                          # retrocede hasta que se repita un vértice
        seen.append(v)
        v = pred[v]
    return None, seen[seen.index(v):][::-1]

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': ['C']}
print(kahn(graph))
# (None, ['E', 'F', 'C'])
graph['F'] = []
print(kahn(graph))
# (['A', 'B', 'C', 'D', 'E', 'F'], None)

¿Por qué atascarse demuestra un ciclo? Todo vértice sobrante aún tiene al menos una flecha entrante, y esa flecha viene de un vértice sobrante, porque todo vértice eliminado ya ha restado sus flechas de los contadores. Así que desde cualquier vértice sobrante puedes retroceder por una flecha hasta otro vértice sobrante, indefinidamente. Con un número finito de vértices, el recorrido hacia atrás tiene que repetir un vértice, y el tramo entre las dos visitas es un ciclo. El código hace exactamente ese recorrido e informa de E, F, C, el mismo ciclo de antes leído desde otro punto de partida.

Hay un detalle en el que es fácil equivocarse. En el ejemplo, el algoritmo de Kahn elimina A y B, y luego se atasca con C, D, E y F todavía en su sitio. D no está en ningún ciclo; está atascado solo porque espera a C. Los vértices sobrantes son los ciclos más todo lo que hay aguas abajo de ellos, así que presentar el conjunto sobrante como «el ciclo» es un error. Sin la flecha F→C el mismo código devuelve el orden A, B, C, D, E, F, uno de los nueve órdenes válidos de ese DAG.

Ambos métodos se ejecutan en tiempo O(V + E) y se diferencian en lo que entregan: la versión en profundidad te da directamente un ciclo, mientras que la de Kahn te da un orden topológico siempre que exista, que suele ser lo que un planificador o una herramienta de compilación quería desde el principio.

7. ¿Cuántos ciclos? El espacio de ciclos

Contar los ciclos uno a uno se descontrola enseguida. El grafo completo K4 tiene 7 ciclos, K5 tiene 37, K6 tiene 197 y K10 tiene 556.014. Es posible enumerarlos todos, y el algoritmo de Johnson de 1975 lo hace para grafos dirigidos en tiempo O((n + e)(c + 1)) para c ciclos, pero la salida por sí sola puede ser exponencial en el tamaño del grafo.

Hay un recuento mucho mejor. Piensa en un ciclo como un conjunto de aristas, y combina dos conjuntos de aristas mediante la diferencia simétrica: quédate con las aristas que están exactamente en uno de los dos. Con esta operación, los subgrafos en los que todo vértice tiene grado par forman un espacio vectorial sobre el cuerpo de dos elementos, llamado espacio de ciclos. Todo ciclo está en él, y su dimensión es

el número ciclomático, o rango de circuitos: m − n + k.

Construir una base es fácil. Toma cualquier bosque de expansión, que tiene n − k aristas. Cada una de las m − n + k aristas restantes cierra exactamente un ciclo con el bosque, su ciclo fundamental, y estos ciclos son independientes porque cada uno contiene una arista que ningún otro tiene. La idea se remonta a Kirchhoff, que la usó en 1847 para contar las ecuaciones de malla independientes de una red eléctrica; el nombre de número ciclomático llegó después. Una búsqueda en profundidad entrega la base directamente: modifica el buscador de ciclos para que registre cada arista de retroceso en lugar de detenerse en la primera.

def cycle_basis(vertices, edges):
    """Un ciclo por cada arista fuera del bosque DFS: m - n + k ciclos en total."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent, used, basis = {}, set(), []
    for root in vertices:
        if root in parent:
            continue
        parent[root] = None
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i in used:                     # arista del árbol o arista de retroceso ya contada
                    continue
                used.add(i)
                if v in parent:                   # arista de retroceso: registra su ciclo y sigue
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]])
                    basis.append(cycle[::-1])
                    continue
                parent[v] = u
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return basis

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
basis = cycle_basis(V, E)
print(len(basis), len(E) - len(V) + 1, basis)
# 3 3 [['A', 'B', 'C'], ['B', 'C', 'E', 'D'], ['E', 'D', 'F', 'G']]

def edges_of(cycle):
    return {''.join(sorted(p)) for p in zip(cycle, cycle[1:] + cycle[:1])}
total = edges_of(basis[0]) ^ edges_of(basis[1]) ^ edges_of(basis[2])
print(sorted(total))
# ['AB', 'AC', 'BD', 'CE', 'DF', 'EG', 'FG']

El ejemplo tiene 10 − 8 + 1 = 3 ciclos independientes, y el árbol de búsqueda de la sección 3 produce los tres más naturales: el triángulo y los dos cuadrados. Su diferencia simétrica cancela las aristas compartidas B–C y D–E y deja el ciclo exterior de longitud 7.

El espacio tiene 23 = 8 elementos, y revisarlos todos es instructivo. Uno es el vacío. Seis son los seis ciclos del grafo. El último es el triángulo junto con el cuadrado D, E, G, F: todo vértice tiene grado par, pero los dos ciclos no comparten ningún vértice, así que el conjunto no es un único ciclo. Los elementos del espacio de ciclos son uniones de ciclos disjuntos en aristas, no siempre ciclos. Para K10 la diferencia entre ambos recuentos es enorme: un rango de 45 − 10 + 1 = 36, frente a 556.014 ciclos reales.

El mismo número aparece en la ingeniería de software. La complejidad ciclomática de McCabe, de 1976, mide un programa por el rango de circuitos de su grafo de flujo de control, como E − N + 2P para E aristas, N nodos y P piezas conexas. El término P adicional viene de imaginar una arista más desde cada salida de vuelta a su entrada, lo que convierte cada camino a través del programa en un ciclo.

8. Ciclos impares y grafos bipartitos

La longitud de un ciclo importa tanto como su existencia. Un grafo es bipartito, es decir, sus vértices se dividen en dos lados y todas las aristas cruzan entre ellos, si y solo si no tiene ningún ciclo impar. Una dirección es inmediata: un ciclo alterna de lado, así que vuelve a casa tras un número par de pasos. La otra dirección, demostrada por Kőnig en 1916, se apoya en este lema:

Todo paseo cerrado de longitud impar contiene un ciclo de longitud impar.

Toma un paseo cerrado impar de longitud mínima. Si repite un vértice en medio, córtalo ahí en dos paseos cerrados más cortos. Sus longitudes suman un número impar, así que uno de ellos es impar, lo que contradice la elección del más corto. Por tanto, el paseo cerrado impar más corto no repite nada, y es un ciclo impar. (Su longitud es al menos 3, porque un paseo cerrado de longitud 1 necesitaría un lazo.)

En la práctica, la prueba es una coloración con dos colores mediante búsqueda en anchura: colorea el vértice inicial, da a cada vecino el color opuesto y busca una arista cuyos dos extremos reciban el mismo color. Cuando se encuentra una, los dos caminos del árbol desde sus extremos hasta su ancestro común más cercano, más la propia arista, forman un ciclo impar, que es el certificado de que no existe ninguna coloración con dos colores. El ejemplo no es bipartito: tres de sus seis ciclos, de longitudes 3, 5 y 7, son impares, y basta con el triángulo para verlo.

9. Circuitos eulerianos y ciclos hamiltonianos

Dos problemas famosos piden rutas cerradas especiales, y están en lados opuestos de una profunda división.

• Un circuito euleriano usa cada arista exactamente una vez. Es un sendero cerrado, normalmente no un ciclo, ya que puede pasar muchas veces por un mismo vértice. El artículo de Euler de 1736 sobre los puentes de Königsberg mostró que entonces todo vértice debe tener grado par, y el artículo de Hierholzer de 1873 demostró el recíproco: un grafo conexo, sin contar los vértices aislados, tiene un circuito euleriano exactamente cuando todos sus grados son pares. La historia completa está en la guía de caminos y circuitos eulerianos.
• Un ciclo hamiltoniano visita cada vértice exactamente una vez. No se conoce ninguna prueba comparable. Decidir si existe uno es NP-completo, uno de los 21 problemas de la lista de Karp de 1972. Existen condiciones suficientes, la más conocida de las cuales es el teorema de Dirac de 1952: un grafo simple con n ≥ 3 vértices en el que todo vértice tiene grado al menos n/2 tiene un ciclo hamiltoniano.

El ejemplo no cumple ninguno de los dos, por razones sencillas. Seis de sus vértices, B, C, D, E, G y H, tienen grado impar, así que no tiene circuito euleriano y, como hay más de dos grados impares, ni siquiera un sendero euleriano abierto. Y H tiene grado 1, así que ningún ciclo puede pasar por él; lo mejor posible es el ciclo de longitud 7 que solo deja fuera a H. El problema hamiltoniano con distancias asociadas es el problema del viajante de comercio.

10. Ciclos con pesos: ciclos negativos

Cuando las aristas llevan pesos, un ciclo tiene un peso total, y un ciclo negativo, uno cuyos pesos suman menos de cero, rompe los caminos más cortos. Dar una vuelta más siempre reduce el coste, así que los paseos hacia cualquier vértice alcanzable desde el ciclo no tienen ninguna longitud mínima. El algoritmo de Bellman-Ford lo detecta. Un camino más corto sin ciclos negativos tiene como mucho n − 1 aristas, así que tras n − 1 rondas de relajación de todas las aristas, todas las distancias son definitivas. Si una n-ésima ronda aún mejora algo, existe un ciclo negativo, y seguir los punteros de predecesor hacia atrás desde un vértice mejorado lleva hasta él.

Una aplicación elegante es el arbitraje de divisas. Asigna a la arista de la divisa a a la divisa b el peso −log r, donde r es el tipo de cambio. Una ronda de operaciones multiplica el dinero por el producto de los tipos, y el producto supera 1 exactamente cuando la suma de los pesos es negativa. Un bucle rentable es un ciclo negativo. Cuando la pregunta es el ciclo con el menor peso medio por arista, lo resuelve en tiempo O(nm) la caracterización de Karp de 1978 de la media mínima de ciclo.

11. Ciclos en una secuencia: la tortuga y la liebre

Otro tipo de detección de ciclos funciona en grafos en los que cada vértice tiene exactamente una arista saliente. Seguir los punteros next de una lista enlazada, o aplicar una función f a un valor una y otra vez, recorre un grafo así. En un conjunto finito, el recorrido acabará repitiendo un valor, y a partir de entonces se repite para siempre. La secuencia tiene la forma de la letra griega rho, ρ: una cola de longitud μ que desemboca en un ciclo de longitud λ.

Guardar cada valor visto encontraría la repetición, pero cuesta una memoria proporcional a μ + λ. El método de la tortuga y la liebre usa dos punteros y nada más. La tortuga avanza un paso cada vez y la liebre dos. Una vez que ambas están en el ciclo, la liebre gana un paso por movimiento, así que alcanza a la tortuga en una vuelta como mucho. Knuth atribuyó la idea a Robert W. Floyd en 1969, aunque no se conoce ningún artículo de Floyd que la describa.

def floyd(f, x0):
    """Longitud de la cola mu y del ciclo lam de x0, f(x0), f(f(x0)), ... con memoria O(1)."""
    tortoise, hare = f(x0), f(f(x0))
    while tortoise != hare:                       # 1. encontrarse en algún punto del ciclo
        tortoise, hare = f(tortoise), f(f(hare))
    mu, tortoise = 0, x0
    while tortoise != hare:                       # 2. avanzar a la par hasta la entrada del ciclo
        tortoise, hare = f(tortoise), f(hare)
        mu += 1
    lam, hare = 1, f(tortoise)
    while tortoise != hare:                       # 3. dar una vuelta al ciclo
        hare = f(hare)
        lam += 1
    return mu, lam

f = lambda x: (x * x + 1) % 55
print(floyd(f, 0))
# (4, 6)
seq = [0]
for _ in range(11):
    seq.append(f(seq[-1]))
print(seq)
# [0, 1, 2, 5, 26, 17, 15, 6, 37, 50, 26, 17]

Para f(x) = x2 + 1 mod 55 empezando en 0, los valores son 0, 1, 2, 5 y luego entran en el bucle 26, 17, 15, 6, 37, 50, así que μ = 4 y λ = 6. Los dos punteros se encuentran por primera vez tras seis movimientos de la tortuga. La segunda fase funciona porque, en el punto de encuentro, la tortuga ha dado un cierto número t de pasos y la liebre 2t, así que t es múltiplo de λ. Un puntero que se reinicia en x0 y otro que se deja en el punto de encuentro, ambos avanzando un paso cada vez, llegan por tanto juntos al inicio del ciclo tras exactamente μ pasos.

El método requiere un tiempo O(μ + λ) y memoria constante. La variante de Brent de 1980, que teletransporta la tortuga hasta la liebre en las potencias de dos, suele necesitar menos evaluaciones de f. Ambos se usan en el método rho de Pollard para factorizar enteros, donde f es una aplicación polinómica como x2 + c módulo el número que se factoriza.

12. Dónde importa la detección de ciclos

Siempre que las flechas significan «espera a», «depende de» o «hace referencia a», un ciclo significa que algo no puede terminar, no puede construirse o no puede liberarse.

El interbloqueo es el caso de manual. Coffman, Elphick y Shoshani enumeraron en 1971 cuatro condiciones que deben cumplirse todas para que se produzca un interbloqueo, y la última de ellas, la espera circular, es, en términos de grafos, un ciclo entre las tareas en espera. Un sistema puede prevenir el interbloqueo descartando una de las condiciones, por ejemplo adquiriendo siempre los cerrojos en un único orden global fijo, lo que convierte el grafo de espera en un DAG. O puede dejar que los interbloqueos ocurran, buscar un ciclo de vez en cuando y romperlo abortando a uno de sus miembros.

La gestión de memoria es la misma historia en otra forma. Un contador de referencias baja a cero cuando desaparece el último puntero a un objeto, pero dos objetos que se apuntan mutuamente mantienen sus contadores en 1 aunque nada más pueda alcanzarlos. Por eso CPython complementa el conteo de referencias con un recolector aparte cuyo trabajo es encontrar esos ciclos inalcanzables.

13. Errores comunes

14. Glosario

16. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Euler, L. (1741). "Solutio problematis ad geometriam situs pertinentis." Commentarii academiae scientiarum Petropolitanae 8, 128 a 140. Volumen fechado en 1736. Los puentes de Königsberg y la condición de grado para los circuitos eulerianos.
2. Kirchhoff, G. (1847). "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik und Chemie 72(12), 497 a 508. Árboles de expansión y un ciclo independiente por cada arista restante.
3. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 a 32. Publicado tras la muerte del autor.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 a 465. Un grafo es bipartito exactamente cuando no tiene ningún ciclo impar.
5. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 a 81.
6. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 a 90.
7. Kahn, A. B. (1962). "Topological Sorting of Large Networks." Communications of the ACM 5(11), 558 a 562.
8. Knuth, D. E. (1969). The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, MA: Addison-Wesley. Sección 3.1, ejercicio 6, con el método de búsqueda de ciclos atribuido a Floyd.
9. Coffman, E. G., Elphick, M. J. y Shoshani, A. (1971). "System Deadlocks." Computing Surveys 3(2), 67 a 78.
10. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 a 160.
11. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." En Complexity of Computer Computations, 85 a 103. Nueva York: Plenum. El circuito hamiltoniano dirigido y no dirigido entre los 21 problemas NP-completos.
12. Pollard, J. M. (1975). "A Monte Carlo Method for Factorization." BIT 15(3), 331 a 334.
13. Johnson, D. B. (1975). "Finding All the Elementary Circuits of a Directed Graph." SIAM Journal on Computing 4(1), 77 a 84.
14. McCabe, T. J. (1976). "A Complexity Measure." IEEE Transactions on Software Engineering SE-2(4), 308 a 320.
15. Itai, A. y Rodeh, M. (1978). "Finding a Minimum Circuit in a Graph." SIAM Journal on Computing 7(4), 413 a 423.
16. Karp, R. M. (1978). "A Characterization of the Minimum Cycle Mean in a Digraph." Discrete Mathematics 23(3), 309 a 311.
17. Brent, R. P. (1980). "An Improved Monte Carlo Factorization Algorithm." BIT 20(2), 176 a 184. Un método más rápido de búsqueda de ciclos.
18. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.