Paseos, senderos, caminos, circuitos y ciclos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Seis palabras para recorrer un grafo

La teoría de grafos tiene una pequeña familia de palabras para viajar por las aristas de un grafo: paseo, sendero y camino para los recorridos que pueden terminar en cualquier sitio, y paseo cerrado, circuito y ciclo para los recorridos que vuelven a su punto de partida. Solo se diferencian en tres cosas: si un vértice puede visitarse dos veces, si una arista puede usarse dos veces y si el recorrido termina en su vértice inicial.

• Un paseo es una sucesión de vértices v0, v1, ..., vk en la que cada dos vértices consecutivos están unidos por una arista. Los vértices y las aristas pueden repetirse. La longitud del paseo es k, el número de pasos dados, contando las aristas repetidas cada vez que se usan.
• Un sendero es un paseo que nunca usa dos veces la misma arista. Puede pasar por un vértice más de una vez.
• Un camino es un paseo que nunca visita dos veces el mismo vértice. Una arista usada dos veces haría volver a sus dos extremos, así que un camino tampoco repite nunca una arista.
• Un paseo cerrado es un paseo cuyo último vértice es el primero.
• Un circuito es un sendero cerrado: termina donde empezó y no usa ninguna arista dos veces.
• Un ciclo es un paseo cerrado de longitud al menos 3 en el que no se repite ningún vértice, salvo que el último vértice es el primero.

Estas son las definiciones que usan la mayoría de los libros de texto modernos de teoría de grafos, aunque no todos, y la sección 4 muestra dónde difieren las principales convenciones. El ejemplo que nos acompaña es una franja de cuatro triángulos con 6 vértices y 9 aristas:

edges = {AB, AC, BC, BD, CD, CE, DE, DF, EF}      6 vértices, 9 aristas

fila superior:   B     D     F
fila inferior: A     C     E

deg:   A 2   B 3   C 4   D 4   E 3   F 2

Cada recorrido del dibujo lleva el nombre más específico de los seis que le corresponde:

• A, B, C, A, B, D es un paseo de longitud 5. Usa la arista A-B dos veces, así que no es un sendero.
• A, C, B, D, C, E es un sendero de longitud 5. Visita C dos veces, así que no es un camino, pero sus cinco aristas son todas distintas.
• A, C, D, F es un camino de longitud 3. Sus cuatro vértices son todos distintos.
• A, B, C, D, B, A es un paseo cerrado de longitud 5. Vuelve a A, pero usa A-B dos veces.
• A, B, C, D, E, C, A es un circuito de longitud 6. Vuelve a A con seis aristas distintas, pero pasa por C dos veces.
• A, B, D, F, E, C, A es un ciclo de longitud 6. Recorre el contorno de la franja y no repite nada.

Un vértice por sí solo, como A, también cuenta: es un paseo de longitud 0 y un camino de longitud 0, llamado paseo trivial. Importa sobre todo en los casos límite de las demostraciones y del código, donde "el camino de un vértice a sí mismo" debe existir y tener longitud 0.

2. Cómo encajan las seis

Las definiciones están anidadas. Todo camino es un sendero, porque un recorrido que nunca vuelve a un vértice no puede reutilizar una arista, y todo sendero es un paseo. En el lado cerrado, todo ciclo es un circuito y todo circuito es un paseo cerrado. Ninguna de estas inclusiones se invierte, como muestran los ejemplos de la sección 1. Tres preguntas bastan siempre para encontrar el nombre correcto, y el orden en que se hagan no importa.

Los recuentos del ejemplo muestran lo rápido que se separan las familias. De A a F hay exactamente 13 caminos: 3 de longitud 3, 6 de longitud 4 y 4 de longitud 5. Hay 23 senderos: los 13 caminos más 10 senderos que pasan dos veces por algún vértice, como A, C, B, D, C, E, F. Hay infinitos paseos, porque un paseo puede ir y volver por cualquier arista tantas veces como quiera. Solo cuando se fija la longitud el número de paseos se vuelve finito, y la sección 6 los cuenta exactamente.

Hay dos detalles que confunden a los principiantes:

• La longitud cuenta aristas, no vértices. El camino A, C, D, F tiene cuatro vértices y longitud 3. Un ciclo que pasa por k vértices tiene longitud k, porque su último paso vuelve al inicio.
• Un ciclo se puede escribir de muchas formas. El ciclo A, B, D, F, E, C, A se puede escribir empezando por cualquiera de sus 6 vértices y en cualquiera de los dos sentidos, lo que da 12 sucesiones para un solo ciclo. Del mismo modo, un camino se puede leer desde cualquiera de sus dos extremos. El código que cuenta ciclos listando sucesiones debe dividir entre 2k, o contará cada ciclo de longitud k ese número de veces.

¿Por qué un ciclo necesita longitud al menos 3? En un grafo simple, los paseos cerrados más cortos, como A, B, A, salen por una arista y vuelven de inmediato por la misma. Eso repite una arista, así que no es ni un circuito ni un ciclo. En un multigrafo la situación cambia: dos aristas paralelas entre los mismos dos vértices forman un ciclo de longitud 2, y un lazo forma un ciclo de longitud 1. Por eso también la definición formal de paseo enumera tanto las aristas como los vértices, v0, e1, v1, e2, ..., vk: cuando dos aristas paralelas unen los mismos vértices, la lista de vértices por sí sola no dice qué arista se usó. En un grafo simple los vértices determinan las aristas, y basta con listar los vértices.

3. Comprobar un recorrido con código

Las definiciones se traducen directamente en una función corta. Recibe un grafo simple y una sucesión de vértices, comprueba que cada paso sigue una arista y después hace las tres preguntas de la sección 2.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def classify(adj, seq):
    """Nombra el tipo de paseo más específico que es la sucesión de vértices seq."""
    steps = list(zip(seq, seq[1:]))
    if any(v not in adj[u] for u, v in steps):
        return 'not a walk'
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(step) for step in steps]
    no_repeated_edge = len(set(edges)) == len(edges)
    inner = seq[:-1] if closed else seq          # un paseo cerrado termina donde empezó
    no_repeated_vertex = len(set(inner)) == len(inner)
    if not closed:
        return 'path' if no_repeated_vertex else 'trail' if no_repeated_edge else 'walk'
    if no_repeated_vertex and len(edges) >= 3:
        return 'cycle'
    return 'circuit' if no_repeated_edge else 'closed walk'

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
for seq in ['ABCABD', 'ACBDCE', 'ACDF', 'ABCDBA', 'ABCDECA', 'ABDFECA', 'ABA', 'ABE']:
    print(seq, classify(strip, seq))
# ABCABD walk
# ACBDCE trail
# ACDF path
# ABCDBA closed walk
# ABCDECA circuit
# ABDFECA cycle
# ABA closed walk
# ABE not a walk

La función rechaza primero A, B, E, porque no hay ninguna arista entre B y E. Para un recorrido cerrado compara los vértices sin el último, ya que un paseo cerrado siempre repite su primer vértice al final. La prueba len(edges) >= 3 es lo que impide que A, B, A se considere un ciclo: sus dos vértices son distintos, pero sus dos pasos usan la misma arista. Toda la comprobación lleva un tiempo proporcional a la longitud del recorrido.

4. Por qué los libros de texto no coinciden

Si ya te habías encontrado con estas palabras, puede que fuera con otros significados. La teoría de grafos creció a la vez en varios países y campos, y el vocabulario nunca llegó a normalizarse del todo. La tabla compara las palabras que algunos libros de texto en inglés muy usados dan a las mismas cuatro ideas.

Desde el libro de Harary de 1969, la mayoría de los textos de teoría de grafos coinciden en lo esencial: un walk (paseo) puede repetir cualquier cosa y un path (camino) no repite nada. La obra de Ore Theory of Graphs, de 1962, muestra el uso más antiguo, en el que un path era un recorrido sin aristas repetidas, lo que hoy se llama sendero (trail). El libro de Rosen Discrete Mathematics and Its Applications, un libro de texto habitual en los primeros cursos de matemática discreta, conserva una versión de ese uso: path significa cualquier paseo, y un simple path es un recorrido que no repite ninguna arista. El propio Rosen señala el conflicto y menciona walk, closed walk y trail como las palabras de los otros libros, pero un estudiante que aprende "path" con Rosen y después abre un texto de teoría de grafos encontrará la misma palabra con un significado más estricto.

Las palabras circuit y cycle son las menos estables. West, y también Chartrand y Zhang, usan circuit para un sendero cerrado, como hace este artículo. Ore usaba circuit para lo que hoy es un ciclo, y los ingenieros suelen llamar "circuit" a cualquier lazo cerrado. Los grafos dirigidos añaden otra capa: en los libros clásicos de Berge, escritos primero en francés, un recorrido en un grafo no dirigido es una chaîne (cadena) y uno cerrado un cycle, mientras que un recorrido que sigue las flechas es un chemin (camino) y uno cerrado un circuit.

La costumbre más segura es enunciar la definición que usas la primera vez que aparece una palabra, o sustituir la palabra ambigua por la propiedad: "un recorrido que no repite ningún vértice" no se puede malinterpretar. Al leer, busca la definición en el primer capítulo y cuenta con que difiera de la del último libro que leíste.

La víctima más conocida de esta terminología es el camino euleriano. Usa cada arista de un grafo exactamente una vez y suele pasar varias veces por los vértices, así que en el vocabulario de este artículo es un sendero, no un camino. El nombre sobrevive porque el problema es más antiguo que el vocabulario, y "sendero euleriano" es hoy el nombre más cuidadoso para lo mismo. El camino hamiltoniano, que visita cada vértice exactamente una vez, sí es realmente un camino. La sección 8 vuelve sobre ambos.

5. Todo paseo contiene un camino

El hecho más útil sobre los paseos es que nunca hace falta repetir nada para llegar a algún sitio. Si hay un paseo de u a v, hay un camino de u a v, y el camino no es más largo que el paseo. La demostración es un atajo. Si el paseo visita dos veces algún vértice x, borra todo lo que hay entre las dos visitas: el paseo sigue yendo de u a v, y es más corto. Repite hasta que ningún vértice se repita. Lo que queda es un camino.

Este pequeño lema tiene grandes consecuencias:

• Conectividad. "Hay un paseo entre cada dos vértices" y "hay un camino entre cada dos vértices" significan lo mismo, así que un grafo puede llamarse conexo usando cualquiera de las dos palabras. La guía sobre componentes conexas se apoya en esto.
• Los recorridos más cortos son caminos. Un paseo más corto entre dos vértices nunca repite un vértice, ya que cortar la repetición lo haría más corto. Por eso la búsqueda en anchura y el algoritmo de Dijkstra pueden buscar entre paseos sin comprobar nunca si hay vértices repetidos, y aun así devuelven caminos. La guía sobre algoritmos de camino más corto trata ambos.
• Los pesos negativos lo rompen. Con pesos de arista negativos, cortar un lazo puede alargar un recorrido, porque el lazo podía tener un peso total negativo. Si se puede alcanzar un ciclo negativo, los paseos pueden hacerse tan baratos como quieras dando más vueltas a ese ciclo, y los paseos más cortos dejan de existir. Los caminos más cortos siguen existiendo, pero encontrar uno se vuelve NP-difícil en general, ya que también serviría para encontrar los caminos más largos de la sección 7. La guía sobre el algoritmo de Bellman-Ford muestra cómo detectar esos ciclos.

Los paseos cerrados requieren más cuidado. Un paseo cerrado no siempre contiene un ciclo: A, B, A es cerrado pero no contiene ninguno. Un paseo cerrado de longitud impar siempre contiene uno, y el ciclo que contiene también es impar. Divide el paseo cerrado por un vértice repetido en dos paseos cerrados más cortos. Sus longitudes suman la longitud impar original, así que uno de ellos es impar. Quédate con el impar y repite. El proceso se detiene en un paseo cerrado impar sin vértices repetidos y, como un grafo simple no tiene paseos cerrados de longitud 1, ese paseo es un ciclo de longitud al menos 3.

Este argumento es el paso clave del teorema de Kőnig: un grafo es bipartito exactamente cuando no tiene ningún ciclo de longitud impar. Un circuito se divide del mismo modo, en ciclos que no comparten ninguna arista. El programa de abajo realiza las tres operaciones: corta los lazos de un paseo, encuentra un ciclo impar dentro de un paseo cerrado impar y divide un circuito en ciclos.

def walk_to_path(walk):
    """Corta todos los lazos. El resultado es un camino con los mismos dos extremos."""
    path, where = [], {}
    for v in walk:
        if v in where:                       # de vuelta en v: descarta todo desde la última visita
            for u in path[where[v] + 1:]:
                del where[u]
            del path[where[v] + 1:]
        else:
            where[v] = len(path)
            path.append(v)
    return ''.join(path)

def split_closed_walk(walk):
    """Divide un paseo cerrado por su primer vértice repetido en dos paseos cerrados más cortos."""
    seen = {}
    for i, v in enumerate(walk[:-1]):
        if v in seen:
            j = seen[v]
            return walk[j:i + 1], walk[:j] + walk[i:]
        seen[v] = i
    return None                              # nada se repite: un ciclo, o un paso de ida y vuelta

def odd_cycle(walk):
    """Un paseo cerrado de longitud impar siempre contiene un ciclo de longitud impar."""
    while True:
        parts = split_closed_walk(walk)
        if parts is None:
            return walk
        walk = next(p for p in parts if (len(p) - 1) % 2 == 1)

def circuit_to_cycles(walk):
    """Divide un circuito en ciclos que no comparten ninguna arista."""
    parts = split_closed_walk(walk)
    if parts is None:
        return [walk]
    return circuit_to_cycles(parts[0]) + circuit_to_cycles(parts[1])

print(walk_to_path('ACBDCEF'))               # paseo de longitud 6
# ACEF
print(odd_cycle('ABCDCA'))                   # paseo cerrado de longitud 5, arista C-D usada dos veces
# ABCA
print(circuit_to_cycles('ABCDECA'))          # circuito de longitud 6 que pasa dos veces por C
# ['CDEC', 'ABCA']

El sendero A, C, B, D, C, E, F visita C dos veces, así que el lazo C, B, D, C desaparece y queda A, C, E, F. El paseo cerrado A, B, C, D, C, A se divide por C en C, D, C, de longitud 2, y A, B, C, A, de longitud 3, que es el ciclo impar. El circuito A, B, C, D, E, C, A se divide por C en los dos triángulos C, D, E, C y A, B, C, A.

La división del circuito es un caso particular de un teorema que Oswald Veblen publicó en 1912: las aristas de un grafo se pueden repartir en ciclos que no comparten ninguna arista si y solo si todo vértice tiene grado par. Un ciclo usa dos aristas en cada vértice por el que pasa, así que los grados deben ser pares; el recíproco se obtiene quitando repetidamente un ciclo, lo que mantiene pares todos los grados.

6. Contar paseos con potencias de matrices

Los paseos son difíciles de listar pero fáciles de contar. Escribe el grafo como su matriz de adyacencia A, con un 1 en la fila u, columna v cuando u y v son adyacentes y un 0 en caso contrario. La guía sobre la representación de grafos explica la matriz en sí. Entonces se cumple un hecho clásico: la entrada de la fila u, columna v de la potencia Ak es el número de paseos de longitud k de u a v.

El motivo es la regla para multiplicar matrices. Un paseo de longitud k de u a v es un paseo de longitud k - 1 de u a algún vértice w, seguido de un paso de w a v. Así que el número de esos paseos es la suma sobre todos los w de (paseos de longitud k - 1 de u a w) por A[w][v], que es exactamente la entrada de Ak-1 por A. La inducción sobre k hace el resto.

La franja muestra varias consecuencias a la vez:

• La diagonal de A2 es la lista de los grados. Un paseo cerrado de longitud 2 sale por una arista y vuelve, y hay uno por cada arista del vértice: 2, 3, 4, 4, 3, 2 de A a F.
• A2[A][D] = 2, por los paseos A, B, D y A, C, D.
• La primera potencia con una entrada no nula da la distancia. A1 y A2 valen 0 en la fila A, columna F, y en A3 vale 3. Así que la distancia de A a F es 3, y los tres paseos de esa longitud son los tres caminos más cortos A, B, D, F, A, C, D, F y A, C, E, F. Por la sección 5, los paseos más cortos siempre son caminos.
• Los triángulos salen de la diagonal de A3. Un paseo cerrado de longitud 3 en un grafo simple recorre un triángulo. Cada triángulo se cuenta una vez desde cada uno de sus 3 vértices en cada uno de los 2 sentidos, así que el número de triángulos es la suma de la diagonal dividida entre 6: aquí 24 / 6 = 4, los triángulos ABC, BCD, CDE y DEF.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def matmul(X, Y):
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*Y)] for row in X]

def walk_counts(adj, order, k):
    """La entrada [i][j] de la potencia k-ésima de la matriz de adyacencia cuenta los paseos de longitud k."""
    A = [[int(v in adj[u]) for v in order] for u in order]
    M = A
    for _ in range(k - 1):
        M = matmul(M, A)
    return M

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
order = 'ABCDEF'
for k in range(1, 7):
    M = walk_counts(strip, order, k)
    print(f'length {k}:  A to F {M[0][5]:3}   A back to A {M[0][0]:3}')
# length 1:  A to F   0   A back to A   0
# length 2:  A to F   0   A back to A   2
# length 3:  A to F   3   A back to A   2
# length 4:  A to F   6   A back to A  11
# length 5:  A to F  29   A back to A  24
# length 6:  A to F  78   A back to A  92
A3 = walk_counts(strip, order, 3)
print('triangles:', sum(A3[i][i] for i in range(len(order))) // 6)
# triangles: 4

El número de paseos de A a F crece deprisa con la longitud, de 3 a 78 en tres pasos, y aun así el cálculo sigue siendo barato. Cada multiplicación de dos matrices de n por n requiere unas n3 operaciones, y elevar al cuadrado repetidamente llega a Ak en unas log2 k multiplicaciones, así que incluso los paseos de longitud un millón se pueden contar exactamente con unas pocas docenas de productos de matrices. La suma de la diagonal de Ak es también la suma de las potencias k-ésimas de los valores propios de la matriz, y ahí es donde los paseos se encuentran con la teoría espectral de grafos: el mayor valor propio fija el ritmo de crecimiento del número de paseos largos.

7. Los paseos son fáciles, los caminos son difíciles

El truco de la matriz no tiene equivalente para los caminos. El número de caminos entre dos vértices es, en general, difícil de calcular: Leslie Valiant demostró en 1979 que contar los caminos entre dos vértices dados es #P-completo, el análogo de NP-completo para el conteo. No se conoce ningún método mucho mejor que probar los recorridos uno por uno, y no se espera que exista. El programa de abajo cuenta caminos exactamente con ese tipo de búsqueda, y cuenta senderos del mismo modo con aristas en lugar de vértices.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_paths(adj, s, t, seen=None):
    """Número de caminos de s a t: prueba cada vecino no visitado y después deshaz."""
    if s == t:
        return 1
    seen = seen or {s}
    total = 0
    for w in adj[s] - seen:
        seen.add(w)
        total += count_paths(adj, w, t, seen)
        seen.remove(w)
    return total

def count_trails(adj, s, t, used=None):
    """Número de senderos de s a t. Un sendero puede pasar por t y volver a él más tarde."""
    used = used or set()
    total = 1 if s == t else 0
    for w in adj[s]:
        e = frozenset((s, w))
        if e not in used:
            used.add(e)
            total += count_trails(adj, w, t, used)
            used.remove(e)
    return total

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
print(count_paths(strip, 'A', 'F'), count_trails(strip, 'A', 'F'))
# 13 23

def grid(n):
    """La cuadrícula de calles de n por n: vértices (fila, columna), aristas hacia la derecha y hacia abajo."""
    return graph([((r, c), (r, c + 1)) for r in range(n) for c in range(n - 1)] +
                 [((r, c), (r + 1, c)) for r in range(n - 1) for c in range(n)])

for n in range(2, 6):
    print(n, count_paths(grid(n), (0, 0), (n - 1, n - 1)))
# 2 2
# 3 12
# 4 184
# 5 8512

En la franja, la búsqueda confirma los recuentos de la sección 2: 13 caminos y 23 senderos de A a F. La cuadrícula muestra lo deprisa que se disparan los números. Entre esquinas opuestas de una cuadrícula de calles con 2, 3, 4 y 5 vértices por lado hay 2, 12, 184 y 8512 caminos, y una fila y una columna más dan 1.262.816. Los físicos y los químicos llaman a los caminos en una retícula caminos autoevitantes y los usan como modelos de cadenas de polímeros, una molécula que no puede atravesarse a sí misma.

La misma brecha separa las preguntas fáciles y las difíciles sobre recorridos individuales:

• Camino más corto: fácil. La búsqueda en anchura encuentra uno en tiempo lineal cuando las aristas no tienen pesos, y el algoritmo de Dijkstra cuando los pesos no son negativos, gracias al lema del atajo de la sección 5.
• Camino más largo: difícil. Decidir si un grafo tiene un camino de al menos una longitud dada es NP-completo. Un camino que pasa por los n vértices tiene longitud n - 1, así que la pregunta incluye como caso particular el problema del camino hamiltoniano. En la franja, el camino más largo de A a F tiene longitud 5 y pasa por los seis vértices; el zigzag A, B, C, D, E, F es uno de ellos.
• Paseo más largo: sin sentido. Los paseos pueden repetir aristas, así que cualquier grafo con una arista tiene paseos de todas las longitudes.

8. Senderos, circuitos y Euler

Los senderos pertenecen a Euler. Su solución de 1736 al problema de los puentes de Königsberg buscaba un paseo que cruzara cada puente exactamente una vez: un sendero por todas las aristas de un multigrafo. Un sendero así es un sendero euleriano, y uno cerrado es un circuito euleriano. La condición de Euler, demostrada por completo por Carl Hierholzer en un artículo publicado en 1873, trata de los grados. Un grafo conexo tiene un circuito euleriano exactamente cuando todos sus vértices tienen grado par, y un sendero euleriano no cerrado exactamente cuando hay exactamente dos vértices de grado impar, en cuyo caso el sendero debe empezar en uno de ellos y terminar en el otro.

En la franja, B y E tienen grado 3 y todos los demás vértices tienen grado par, así que un sendero euleriano va de B a E:

B, A, C, B, D, C, E, D, F, E        9 aristas, cada una usada una vez

Pasa por B, C, D y E dos veces cada uno, y por eso "camino euleriano" es, en sentido estricto, un nombre inapropiado. La guía sobre caminos y circuitos eulerianos trata en detalle el algoritmo de Hierholzer. Cuando un grafo tiene más de dos vértices impares, algunas aristas deben recorrerse dos veces, y encontrar el paseo cerrado más barato por todas las aristas es el problema del cartero chino.

El teorema de Veblen de la sección 5 es la otra cara de la misma moneda. Un circuito euleriano es un circuito por todas las aristas, y dividirlo por sus vértices repetidos reparte las aristas en ciclos que no comparten ninguna arista. Recíprocamente, un grafo conexo cuyas aristas se reparten en ciclos así tiene todos los grados pares, y los ciclos se pueden empalmar en los vértices compartidos para formar un único circuito euleriano.

9. Ciclos, cintura y circunferencia

La franja tiene exactamente 10 ciclos: los cuatro triángulos, tres ciclos de longitud 4, dos de longitud 5 y uno de longitud 6.

longitud 3:  ABC, BCD, CDE, DEF
longitud 4:  ABDC, BDEC, CDFE
longitud 5:  ABDEC, BDFEC
longitud 6:  ABDFEC

Dos números resumen los ciclos de un grafo. La cintura es la longitud de un ciclo más corto, aquí 3, y la circunferencia es la longitud de un ciclo más largo, aquí 6. Un ciclo que pasa por todos los vértices, como A, B, D, F, E, C, A, es un ciclo hamiltoniano, así que la franja es hamiltoniana. Un grafo sin ningún ciclo es un bosque, y uno conexo es un árbol, en el que hay exactamente un camino entre cada dos vértices; la guía sobre árboles desarrolla esa idea. La guía sobre ciclos en grafos explica cómo detectar un ciclo con búsqueda en profundidad y cuántos ciclos independientes tiene un grafo.

10. Paseos y caminos dirigidos

En un grafo dirigido cada paso debe seguir una flecha desde su cola hasta su cabeza. Con ese único cambio, las seis definiciones se trasladan tal cual: paseo dirigido, sendero dirigido, camino dirigido, paseo cerrado dirigido, circuito dirigido y ciclo dirigido. Algunas cosas se comportan de otra manera:

• Existen ciclos de longitud 2. Dos flechas u → v y v → u son aristas distintas, así que u, v, u es un ciclo dirigido incluso en un grafo sin aristas paralelas.
• La alcanzabilidad va en un solo sentido. Un camino dirigido de u a v no dice nada sobre un camino de vuelta. Los vértices que pueden alcanzarse mutuamente en ambos sentidos forman una componente fuertemente conexa, y la guía sobre componentes fuertemente conexas muestra cómo encontrarlas.
• Sin ciclos dirigidos existe un orden. Un grafo dirigido sin ciclos dirigidos, un DAG, siempre se puede listar de modo que cada flecha apunte hacia delante. Ese listado es una ordenación topológica, y en un DAG incluso el camino más largo se puede encontrar en tiempo lineal.
• Ignorar las flechas da un semipaseo o semicamino, que puede avanzar en contra de una flecha. Un grafo dirigido es débilmente conexo cuando sus vértices están unidos por semicaminos.

El truco de la matriz de la sección 6 funciona sin cambios para los grafos dirigidos: la entrada de la fila u, columna v de Ak cuenta los paseos dirigidos de longitud k de u a v.

11. Dónde se usa cada tipo de recorrido

Cada una de las seis palabras nombra el modelo adecuado para un tipo distinto de problema real:

• Los caminos son los recorridos para todo lo que no debe dar vueltas: indicaciones para conducir, paquetes a través de una red, una cadena de presentaciones entre dos personas. Todo problema de recorrido más corto es un problema de caminos, por el lema del atajo.
• Los senderos y los circuitos describen cómo cubrir cada calle, tubería o cable una vez: quitanieves, barredoras y rondas de reparto postal. Cuando hay que repetir algunas aristas, el problema se convierte en el problema del cartero chino de la sección 8.
• Los paseos aparecen siempre que el movimiento es aleatorio. Un paseo aleatorio se mueve a un vecino al azar en cada paso. George Pólya demostró en 1921 que un paseo aleatorio en la retícula de puntos enteros vuelve con certeza a su punto de partida en una o dos dimensiones, pero no en tres. El PageRank original de Google, descrito por Sergey Brin y Lawrence Page en 1998, ordena las páginas web según la frecuencia con que las visita un navegante aleatorio que sigue enlaces, y los métodos de incrustación de grafos como DeepWalk aprenden a partir de muchos paseos aleatorios cortos.
• Los ciclos suelen ser lo que hay que encontrar o prohibir: un interbloqueo es un ciclo de procesos en el que cada uno espera al siguiente, una importación circular o una fórmula de hoja de cálculo que se refiere a sí misma es un ciclo de dependencias, y la ley de tensiones de Kirchhoff dice que las tensiones a lo largo de cualquier ciclo de una red eléctrica suman cero.
• Los paseos cerrados cuentan estructura: la diagonal de A3 cuenta triángulos, algo que el análisis de redes sociales usa para medir con qué frecuencia los amigos de una persona se conocen entre sí.

12. Errores comunes

13. Glosario

15. 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. Presentado en 1736.
2. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6, 30 a 32.
3. Veblen, O. (1912). "An Application of Modular Equations in Analysis Situs." Annals of Mathematics, 2.ª serie, 14, 86 a 94.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77, 453 a 465.
5. Pólya, G. (1921). "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz." Mathematische Annalen 84, 149 a 160.
6. Berge, C. (1958). Théorie des graphes et ses applications. París: Dunod.
7. Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications 38. Providence, RI: American Mathematical Society.
8. Harary, F. (1969). Graph Theory. Reading, MA: Addison-Wesley.
9. Garey, M. R. y Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman.
10. Valiant, L. G. (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing 8(3), 410 a 421.
11. Biggs, N. (1993). Algebraic Graph Theory, 2.ª edición. Cambridge: Cambridge University Press.
12. 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.
13. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River, NJ: Prentice Hall.
14. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer.
15. Chartrand, G. y Zhang, P. (2012). A First Course in Graph Theory. Mineola, NY: Dover.
16. Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 7.ª edición. Nueva York: McGraw-Hill.
17. Perozzi, B., Al-Rfou, R. y Skiena, S. (2014). "DeepWalk: Online Learning of Social Representations." Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 701 a 710.
18. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.