Graph Labs

Referencia de los algoritmos

Pseudocódigo, invariantes y errores comunes de cada método del estudio, con la misma notación usada en clase. Es exactamente esta formulación la que la simulación ejecuta paso a paso.

Búsqueda en grafos

Búsqueda en profundidad

Elige siempre el vértice marcado alcanzado más recientemente y registra un tiempo de descubrimiento TD y un tiempo de finalización TF.

O(n + m)

Idea central

Búsqueda genérica en la que, entre todos los vértices marcados e incidentes a alguna arista aún no explorada, se elige siempre el alcanzado más recientemente. Cada vértice recibe un tiempo de descubrimiento TD[v] y un tiempo de finalización TF[v], marcados por un contador global t.

Invariante

Los intervalos de vida I(v) = [TD[v], TF[v]] están anidados o son disjuntos; nunca se superponen parcialmente. El vértice w es descendiente de v si y solo si I(w) está contenido en I(v).

Requisitos del grafo

Acepta aristas dirigidas y no dirigidasGrafo no dirigido: aristas de árbol y de retrocesoGrafo dirigido: árbol, retroceso, avance y cruce

Errores comunes

  • En un grafo no dirigido solo existen aristas de árbol y de retroceso; las de avance y de cruce solo aparecen en grafos dirigidos.
  • Olvidar la condición w ≠ padre[v]: la arista usada para llegar a v no es una arista de retroceso.
  • Toda arista de retroceso revela un ciclo en el grafo original. En un grafo dirigido, es la única evidencia necesaria.
Inicialización / Llamada inicial
  t ← 0
  para todo vértice v ∈ V(G) hacer
    TD[v] ← 0; TF[v] ← 0; padre[v] ← nulo
  mientras exista algún vértice v tal que TD[v] = 0 hacer
    Ejecutar Búsqueda_Profundidad(v)   // v es la raíz de la búsqueda
 
Búsqueda_Profundidad(v)               // grafo no dirigido
  t ← t + 1; TD[v] ← t
  para todo vértice w ∈ Γ(v) hacer
    si TD[w] = 0 entonces           // arista de árbol
      padre[w] ← v; Ejecutar Búsqueda_Profundidad(w)
    si no, si TF[w] = 0 y w ≠ padre[v] entonces
      Visitar arista de retroceso {v, w}
  t ← t + 1; TF[v] ← t
 
Búsqueda_Profundidad(v)               // grafo dirigido
  para todo vértice w ∈ Γ⁺(v) hacer
    si TD[w] = 0 entonces  arista de árbol (v, w); padre[w] ← v; ...
    si no, si TF[w] = 0 entonces       arista de retroceso (v, w)
    si no, si TD[v] < TD[w] entonces   arista de avance (v, w)
    si no                              arista de cruce (v, w)

Búsqueda en grafos

Búsqueda en anchura

Elige siempre el vértice marcado alcanzado hace más tiempo, usando una cola, y asigna a cada vértice su nivel.

O(n + m)

Idea central

Búsqueda genérica en la que, entre todos los vértices marcados e incidentes a alguna arista aún no explorada, se elige siempre el alcanzado hace más tiempo, criterio que se implementa con una cola. Cada vértice recibe un índice L[v] (orden de descubrimiento) y un nivel[v] (distancia a la raíz en número de aristas).

Invariante

nivel[w] = nivel[padre[w]] + 1 para todo w ≠ raíz. Así, en el momento en que w se marca, nivel[w] ya es la distancia (número de aristas) entre la raíz de la búsqueda y w.

Requisitos del grafo

Acepta aristas dirigidas y no dirigidasIgnora los pesos de las aristasClasifica las aristas en padre, tío, hermano y primo

Errores comunes

  • Marcar el vértice (asignar L[w]) solo cuando sale de la cola, y no cuando entra: el mismo vértice terminaría encolado varias veces.
  • Olvidar la condición L[w] > L[v] al clasificar aristas de hermano y de primo: garantiza que cada arista se explore una sola vez.
  • En un grafo ponderado, la búsqueda en anchura solo devuelve un camino de peso mínimo si todos los pesos son iguales; minimiza el número de aristas, no el peso.
Inicialización / Llamada inicial
  t ← 0; Cola ← ∅
  para todo vértice v ∈ V(G) hacer
    L[v] ← 0; nivel[v] ← 0; padre[v] ← nulo
  mientras exista algún vértice v tal que L[v] = 0 hacer
    t ← t + 1; L[v] ← t          // v es la raíz de la búsqueda
    Cola.Insertar(v)
    Ejecutar Búsqueda_Anchura()
 
Búsqueda_Anchura()
  mientras not Cola.Vacía() hacer
    v ← Cola.Quitar()
    para todo vértice w ∈ Γ(v) hacer
      si L[w] = 0 entonces       // arista de árbol (o padre)
        padre[w] ← v; nivel[w] ← nivel[v] + 1
        t ← t + 1; L[w] ← t; Cola.Insertar(w)
      si no, si nivel[w] = nivel[v] + 1 entonces
        Visitar arista de tío {v, w}
      si no, si nivel[w] = nivel[v] y padre[v] = padre[w] y L[w] > L[v] entonces
        Visitar arista de hermano {v, w}
      si no, si nivel[w] = nivel[v] y padre[v] ≠ padre[w] y L[w] > L[v] entonces
        Visitar arista de primo {v, w}

Conectividad

Algoritmo de Kosaraju

Encuentra las componentes fuertemente conexas con dos búsquedas en profundidad: una en G y otra en el grafo inverso Gᴿ.

O(n + m)

Idea central

Una primera búsqueda en profundidad en G registra los tiempos de finalización TF. La segunda búsqueda, hecha en el grafo inverso Gᴿ y tomando los vértices en orden decreciente de TF, produce un bosque en el que cada árbol es exactamente una componente fuertemente conexa.

Invariante

El orden decreciente de tiempo de finalización garantiza que la búsqueda en Gᴿ iniciada en un vértice nunca escapa de la componente fuertemente conexa a la que pertenece.

Requisitos del grafo

Requiere un grafo dirigidoIgnora los pesos de las aristas

Errores comunes

  • Olvidar construir el grafo inverso Gᴿ antes de la segunda búsqueda.
  • Recorrer la segunda búsqueda en orden creciente de TF en lugar de decreciente.
  • Confundir los tres niveles de conectividad de un grafo dirigido conexo: débilmente conexo (el grafo subyacente es conexo), unilateralmente conexo (para todo par, uno alcanza al otro) y fuertemente conexo (todos mutuamente alcanzables).
Algoritmo de Kosaraju
  1. Hacer una búsqueda en profundidad en G
       // guardar el tiempo de finalización TF de cada vértice
  2. Construir el grafo inverso (o traspuesto) Gᴿ
       // si (v, w) ∈ E(G) entonces (w, v) ∈ E(Gᴿ)
  3. Hacer una búsqueda en profundidad en Gᴿ tomando los
     vértices en orden decreciente de TF
 
  Cada árbol del bosque de profundidad obtenido en el paso 3
  corresponde a una componente fuertemente conexa de G.

Grafos eulerianos

Algoritmo de Fleury

Construye un camino euleriano recorriendo el grafo y evitando cruzar un puente mientras haya otra arista disponible.

O(m² )

Idea central

Un grafo conexo es euleriano si y solo si todos sus vértices tienen grado par (teorema de Euler), y semieuleriano si existen exactamente dos vértices de grado impar. El algoritmo recorre el grafo eliminando las aristas recorridas y evita cruzar un puente mientras haya otra opción.

Invariante

El camino construido nunca repite aristas y, al evitar puentes, mantiene conexas las aristas restantes de G', lo que garantiza que el recorrido solo termine cuando todas hayan sido recorridas.

Requisitos del grafo

Requiere un grafo no dirigido y conexoComo máximo 2 vértices de grado imparIgnora los pesos de las aristas

Errores comunes

  • Cruzar un puente mientras existe otra arista disponible: las aristas del otro lado quedan inalcanzables y el camino termina antes de tiempo.
  • Empezar por un vértice de grado par en un grafo semieuleriano: el camino debe partir de uno de los dos vértices de grado impar.
  • Confundirlo con un grafo hamiltoniano: un camino euleriano pasa una vez por cada arista; uno hamiltoniano, una vez por cada vértice.
Algoritmo de Fleury
  1. si V(G) tiene 3 o más vértices de grado impar entonces PARAR
  2. Sea G' = (V', E') tal que V' ← V(G) y E' ← E(G)
  3. Seleccionar un vértice inicial v ∈ V'
       (elegir un v de grado impar, si lo hay)
  4. mientras E' ≠ ∅ hacer
     a. si d(v) > 1 entonces
          Seleccionar una arista {v, w} que no sea puente en G'
        si no
          Seleccionar la única arista {v, w} disponible en G'
     c. v ← w;   E' ← E' − {v, w}
 
  // Caminar de v a w y eliminar la arista recorrida

Árbol de expansión mínima

Algoritmo de Prim

Incluye vértices uno a uno: en cada paso añade la arista de menor peso entre V(T) y los vértices aún no seleccionados.

O(m log n)

Idea central

Construye el árbol de expansión mínima (AEM) de forma voraz, incluyendo los vértices uno a uno. Partiendo de una raíz r, en cada paso añade la arista de menor peso con un extremo en V(T) (ya seleccionados) y el otro fuera de V(T).

Invariante

En cada iteración, T = (V(T), E(T)) es un árbol y está contenido en algún árbol de expansión mínima de G.

Requisitos del grafo

Requiere un grafo no dirigidoRequiere un grafo ponderado con peso w(e) > 0Solo existe árbol de expansión si el grafo es conexo

Errores comunes

  • Comparar el peso de la arista con la distancia acumulada desde la raíz en lugar del peso de la propia arista, lo que convertiría a Prim en Dijkstra.
  • Aplicar Prim a un grafo dirigido: el problema correcto pasa a ser el de la arborescencia de peso mínimo.
  • Un grafo no conexo no tiene árbol de expansión: un grafo G tiene árbol de expansión si y solo si G es conexo.
Algoritmo de Prim
  1. Elegir un vértice cualquiera r ∈ V(G)   // raíz
  2. V(T) ← { r }        // conj. de vértices seleccionados
  3. E(T) ← ∅            // conj. de aristas del AEM
  4. mientras V(T) ≠ V(G) hacer
     a. Encontrar la arista {v, w} de menor peso tal que
        v ∈ V(T) y w ∉ V(T)
     b. Añadir w a V(T)
     c. Añadir {v, w} a E(T)
 
  Peso total: C(T) = Σ  w  , para e ∈ E(T)
                         e

Árbol de expansión mínima

Algoritmo de Kruskal

Incluye aristas, no vértices: ordena las aristas por peso no decreciente y acepta cada una que no forme ciclo con las ya incluidas en E(T).

O(m log m)

Idea central

Construye el AEM incluyendo aristas, y no vértices como en Prim. Ordena las aristas en orden no decreciente de peso y acepta, en cada iteración, la arista de menor peso que no forme ciclo con las ya incluidas en E(T).

Invariante

En cada iteración, T = (V(T), E(T)) es un bosque de expansión contenido en algún árbol de expansión mínima de G.

Requisitos del grafo

Requiere un grafo no dirigidoRequiere un grafo ponderado con peso w(e) > 0En un grafo no conexo produce un bosque de expansión mínima

Errores comunes

  • Suponer que bastan n − 1 iteraciones: se necesitan al menos n − 1, pero pueden ser más, ya que las aristas que forman ciclo deben descartarse.
  • Aceptar una arista cuyos extremos ya están unidos por aristas de E(T): cerraría un ciclo.
  • En un grafo no conexo el resultado es un bosque de expansión mínima, no un árbol de expansión.
Algoritmo de Kruskal
  1. Ordenar las aristas en orden no decreciente de peso:
     e₁, e₂, e₃, . . .
  2. V(T) ← V(G)      // todos los vértices entran en el AEM
  3. E(T) ← { e₁ }
  4. j ← 2            // arista a analizar
  5. mientras | E(T) | < | V(T) | − 1 hacer
     a. si la arista e  no forma ciclo con las aristas de E(T)
                      j
        entonces Añadir e  a E(T)
                         j
     b. j ← j + 1

Caminos mínimos

Algoritmo de Dijkstra

"Cierra" un vértice por iteración, siempre el de menor dist, y relaja las aristas tensas que salen de él.

O(n²)

Idea central

Resuelve el problema del camino mínimo desde una única raíz s. Se basa en el principio de relajación y "cierra" un vértice por iteración: elige el vértice aún no cerrado con el menor valor de dist y relaja las aristas tensas que salen de él.

Invariante

Para todo v ∈ S, dist[v] ya es el peso del camino mínimo desde la raíz hasta v. Al final, dist[ ] guarda los pesos de los caminos mínimos; los caminos en sí se recuperan con la lista de predecesores pred[ ].

Requisitos del grafo

Acepta aristas dirigidas y no dirigidasRequiere pesos no negativosSe basa en el principio de relajación

Errores comunes

  • Aplicar el algoritmo a un grafo con una arista de peso negativo: falla. Reponderar sumando una constante a todas las aristas también puede fallar.
  • Reabrir un vértice que ya pertenece a S: una vez cerrado, su dist ya no cambia.
  • Creer que dist[ ] devuelve los caminos: sin pred[ ] solo se obtienen los pesos.
Operación de relajación
  si dist[v] + d    < dist[w] entonces   // ¿la arista (v, w) está tensa?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Algoritmo de Dijkstra
  1. para todo vértice v ∈ V(G) hacer
       dist[v] ← ∞; pred[v] ← nulo
  2. dist[s] ← 0        // s es la raíz de la búsqueda
  3. S ← ∅              // conjunto de vértices cerrados
  4. mientras S ≠ V(G) hacer
     a. Elegir el vértice v ∉ S de menor dist[v]
     b. S ← S ∪ { v }                  // "cerrar" el vértice v
     c. para todo vértice w ∈ Γ⁺(v) hacer
          si dist[w] > dist[v] + d    entonces   // ¿arista tensa?
                                  vw
            dist[w] ← dist[v] + d
                                 vw
            pred[w] ← v

Caminos mínimos

Algoritmo de Bellman-Ford

Programación dinámica: examina todas las aristas en cada iteración, relajando las que estén tensas, durante |V(G)| − 1 iteraciones.

O(n · m)

Idea central

Calcula caminos mínimos mediante programación dinámica. En lugar de "cerrar" un vértice por iteración, como Dijkstra, examina todas las aristas en cada iteración. Como cualquier camino en un grafo con n vértices tiene como máximo n − 1 aristas, bastan n − 1 iteraciones.

Invariante

Tras la i-ésima iteración, dist[w] es como máximo el peso del camino más corto de s a w que usa hasta i aristas.

Requisitos del grafo

Admite aristas de peso negativoNo admite ciclos de peso negativoDetecta un ciclo de peso negativo alcanzable desde el origen

Errores comunes

  • Si en alguna iteración ninguna arista está tensa, el algoritmo puede terminar: las iteraciones siguientes no traerían actualizaciones.
  • Si hay un ciclo de peso negativo entre s y t, no existe camino mínimo entre ellos; sin ese ciclo, el camino mínimo es simple (no repite vértices).
  • Una arista no dirigida con peso negativo ya es, por sí sola, un ciclo de peso negativo.
Operación de relajación
  si dist[v] + d    < dist[w] entonces   // ¿la arista (v, w) está tensa?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Algoritmo de Bellman-Ford
  1. para todo vértice v ∈ V(G) hacer
       dist[v] ← ∞; pred[v] ← nulo
  2. dist[s] ← 0
  3. para i = 1, . . ., | V(G) | − 1 hacer
       para cada (v, w) ∈ E(G) hacer
         si dist[w] > dist[v] + d    entonces   // ¿arista tensa?
                                 vw
           dist[w] ← dist[v] + d
                                vw
           pred[w] ← v
 
  Si aún hay alguna arista tensa tras la última iteración,
  entonces el grafo tiene un ciclo de peso negativo.

Caminos mínimos

Algoritmo de Floyd-Warshall

Caminos mínimos entre todos los pares mediante programación dinámica: la ronda k habilita el vértice k como intermedio.

O(n³)

Idea central

Programación dinámica sobre el conjunto de vértices intermedios permitidos. Con los vértices numerados de 1 a n, distᵏ[i, j] es la distancia entre i y j usando como intermedios solo los vértices de { 1, 2, . . ., k }.

Invariante

Al final de la ronda k, dist[i, j] es el peso del camino más corto de i a j que usa solo { 1, . . ., k } como vértices intermedios; pred[i, j] guarda el penúltimo vértice de ese camino.

Requisitos del grafo

Admite aristas de peso negativoNo admite ciclos de peso negativoCalcula todos los pares de vértices de una sola vez

Errores comunes

  • Cambiar el orden de los bucles: k debe ser el bucle más externo.
  • Actualizar el predecesor con pred[i, k] en lugar de pred[k, j]: pred[i, j] es el penúltimo vértice del camino de i a j.
  • Una entrada negativa en la diagonal, es decir, dist[i, i] < 0, indica un ciclo de peso negativo.
Relajación de la longitud de los caminos
  distᵏ[i, j] = min( distᵏ⁻¹[i, j],
                     distᵏ⁻¹[i, k] + distᵏ⁻¹[k, j] )
  con dist⁰[i, j] = d   si (i, j) ∈ E(G); ∞ en otro caso;
                     ij
  y dist⁰[i, i] = 0
 
Algoritmo de Floyd-Warshall
  1. para i = 1, . . ., n hacer
       para j = 1, . . ., n | j ≠ i hacer
         dist[i, j] ← ∞; pred[i, j] ← nulo
       dist[i, i] ← 0;   pred[i, i] ← i
  2. para toda arista (i, j) ∈ E(G) hacer
       dist[i, j] ← d  ;  pred[i, j] ← i
                     ij
  3. para k = 1, . . ., n hacer   // cada posible intermedio
       para i = 1, . . ., n hacer
         para j = 1, . . ., n hacer
           si dist[i, j] > dist[i, k] + dist[k, j] entonces
             dist[i, j] ← dist[i, k] + dist[k, j]
             pred[i, j] ← pred[k, j]

Flujo máximo

Método de Ford-Fulkerson

Mientras exista algún camino aumentante en G'(f), envía por él el cuello de botella δ y actualiza la red residual.

O(m · f) con capacidades enteras

Idea central

Mientras exista un camino aumentante de la fuente s al sumidero t en la red residual G′(f), se envía por él lo máximo posible, el cuello de botella δ, y se actualiza la red residual. Las aristas inversas permiten deshacer envíos anteriores.

Invariante

El flujo f respeta siempre la restricción de capacidad, 0 ≤ f(e) ≤ u(e), y la conservación del flujo en todo nodo interno. Por el teorema de flujo máximo y corte mínimo, al final el valor del flujo es igual a la capacidad del corte s-t mínimo.

Requisitos del grafo

Requiere una red de flujo: grafo dirigido con capacidad u(e) > 0Requiere una fuente s y un sumidero tEl camino aumentante se elige de forma arbitraria

Errores comunes

  • Olvidar crear la arista inversa en la red residual, lo que impide deshacer envíos hechos en iteraciones anteriores.
  • Elegir caminos aumentantes arbitrarios: con capacidades irracionales el método puede no terminar. Elegir siempre el camino aumentante con menos aristas (búsqueda en anchura) es el algoritmo de Edmonds-Karp.
  • Suponer que el corte mínimo es cualquier corte: en la solución óptima, S es el conjunto de vértices alcanzables desde la fuente s en la red residual final.
Red residual G′(f): V(G′) = V(G) y, para e = (v, w) ∈ E:
  si f(e) < u(e): arista directa (v, w) con u (e) = u(e) − f(e)
                                             r
  si f(e) > 0:    arista inversa (w, v) con capacidad f(e)
 
Método de Ford-Fulkerson
  1. para toda arista e ∈ E(G) hacer  f(e) ← 0
  2. Construir la red residual G′(f)
  3. mientras exista un camino aumentante P en G′(f) hacer
     a. δ ← min { u (e) | e ∈ P }        // "cuello de botella" de P
                   r
     b. para cada arista (v, w) ∈ P hacer
        i.  si (v, w) es una arista directa entonces
              f(v, w) ← f(v, w) + δ      // aumentar el flujo
        ii. si no
              f(w, v) ← f(w, v) − δ      // reducir el flujo
     c. Actualizar la red residual G′(f)

Flujo máximo

Algoritmo de Edmonds-Karp

Implementación eficiente de Ford-Fulkerson: en cada iteración elige el camino aumentante más corto, obtenido mediante una búsqueda en anchura.

O(n · m² )

Idea central

Implementación eficiente del método de Ford-Fulkerson: en cada iteración selecciona el camino aumentante más corto de la red residual, es decir, el que usa el menor número de aristas. Ese camino se encuentra con una búsqueda en anchura.

Invariante

La longitud del camino aumentante elegido nunca disminuye de una iteración a la siguiente. Hay como máximo O(n·m) caminos aumentantes y cada uno se encuentra en O(m), de ahí O(n·m²).

Requisitos del grafo

Requiere una red de flujo: grafo dirigido con capacidad u(e) > 0Requiere una fuente s y un sumidero tElige siempre el camino aumentante con menos aristas

Errores comunes

  • Usar búsqueda en profundidad: se vuelve al método genérico de Ford-Fulkerson, que es solo pseudopolinomial, O(m·f), con f igual al valor del flujo máximo.
  • En la red con dos aristas de capacidad 100 unidas por una de capacidad 1, la elección arbitraria puede requerir 200 iteraciones; la elección del camino más corto requiere 2.
  • Olvidar que el algoritmo fue publicado de forma independiente por Dinitz (1970) y por Edmonds y Karp (1972).
Algoritmo de Edmonds-Karp
  1. para toda arista e ∈ E(G) hacer  f(e) ← 0
  2. Construir la red residual G′(f)
  3. mientras exista algún camino aumentante P en G′(f) hacer
     a. Sea P el camino aumentante en G′(f) con menor número
        de aristas   // obtenido por búsqueda en anchura
     b. δ ← min { u (e) | e ∈ P }
                   r
     c. para cada arista (v, w) ∈ P hacer
        i.  si (v, w) es una arista directa entonces
              f(v, w) ← f(v, w) + δ
        ii. si no
              f(w, v) ← f(w, v) − δ
     d. Actualizar la red residual G′(f)

Flujo máximo

Algoritmo de Dinic

En cada iteración construye la red de niveles GL a partir de G′(f) y determina en ella un flujo bloqueante.

O(n² · m)

Idea central

En lugar de aumentar un camino cada vez, construye la red de niveles GL a partir de G′(f) y determina en ella un flujo bloqueante completo. Como el número de niveles crece al menos en una unidad en cada iteración, hay como máximo n − 1 flujos bloqueantes.

Invariante

dist(t) crece estrictamente entre iteraciones, así que hay como máximo n − 1 flujos bloqueantes. Cada flujo bloqueante se obtiene en O(n·m), de ahí O(n²·m).

Requisitos del grafo

Requiere una red de flujo: grafo dirigido con capacidad u(e) > 0Requiere una fuente s y un sumidero tComo máximo n − 1 flujos bloqueantes

Errores comunes

  • Buscar caminos fuera de GL: solo valen las aristas (v, w) con dist(w) = dist(v) + 1.
  • Reconstruir la red de niveles tras cada camino en lugar de tras cada flujo bloqueante: lo que caracteriza una iteración es el flujo bloqueante completo.
  • Detenerse cuando un camino se satura: el flujo bloqueante solo termina cuando ya no existe ningún camino de s a t en GL.
Red de niveles GL: V(GL) = V(G′) y, para (v, w) ∈ E(G′):
  (v, w) ∈ E(GL) con capacidad u (e) si dist(w) = dist(v) + 1,
                                r
  donde dist(v) es la menor distancia geodésica de s a v
 
Flujo bloqueante fb: flujo en GL tal que, conservando solo las
  aristas con capacidad mayor que fb, ya no exista ningún
  camino aumentante en GL
 
Algoritmo de Dinic
  1. para toda arista e ∈ E(G) hacer  f(e) ← 0
  2. Construir la red residual G′(f)
  3. Construir la red de niveles GL a partir de G′(f)
  4. mientras dist(t) < ∞ hacer
     a. Determinar un flujo bloqueante fb en GL
     b. Actualizar el flujo f usando fb
     c. Actualizar la red residual G′(f)
     d. Construir la red de niveles GL a partir de G′(f)

Ordenación topológica

Algoritmo de Kahn

En cada paso toma un vértice con grado de entrada cero, lo añade al final del resultado y reduce el grado de entrada de sus sucesores.

O(n + m)

Idea central

En cada paso determina un vértice sin aristas de entrada, es decir, con d⁻(v) = 0, y lo inserta al final del resultado. En lugar de eliminar las aristas, mantiene y actualiza un mapa M con el grado de entrada de cada vértice.

Invariante

Un vértice solo entra en la cola cuando todos sus predecesores ya están en Orden_Top, así que ord(v) < ord(w) para toda arista (v, w) ∈ E(G).

Requisitos del grafo

Requiere un grafo dirigidoSolo existe un orden topológico en un grafo acíclicoDetecta la existencia de un ciclo

Errores comunes

  • Aplicarlo a un grafo no dirigido o con ciclos: no se puede establecer una relación de precedencia y el orden topológico no existe.
  • Interpretar la cola vacía con vértices pendientes como un error: es exactamente así como el algoritmo detecta la existencia de un ciclo.
  • Suponer que el orden es único: un grafo acíclico dirigido puede tener varios órdenes topológicos válidos.
Algoritmo de Kahn
  1. para todo vértice v hacer M[v] ← d⁻(v)
  2. Cola ← ∅; Orden_Top ← ∅
  3. para todo vértice v tal que d⁻(v) = 0 hacer
       Cola.Insertar(v)
  4. mientras not Cola.Vacía() hacer
     a. v ← Cola.Quitar()
     b. Orden_Top.InsertarAlFinal(v)
     c. para todo vértice w ∈ Γ⁺(v) hacer
        i.  M[w] ← M[w] − 1
        ii. si M[w] = 0 entonces Cola.Insertar(w)
  5. Si se procesaron todos los vértices, ÉXITO;
     en otro caso, existe un CICLO

Ordenación topológica

Ordenación topológica por búsqueda en profundidad

Descrito por Tarjan en 1976: inserta cada vértice al principio del resultado solo después de visitar todos los que dependen de él.

O(n + m)

Idea central

Alternativa basada en la búsqueda en profundidad, descrita por Tarjan en 1976. Cada vértice se inserta en el resultado solo después de todos los que dependen de él, y la inserción se hace al principio de la lista, de ahí el orden inverso.

Invariante

Cuando v recibe la marca permanente, todos los vértices alcanzables desde v ya están en Orden_Top. Como v se inserta al principio, los precede a todos en el orden.

Requisitos del grafo

Requiere un grafo dirigidoSolo existe un orden topológico en un grafo acíclicoVolver a encontrar una marca temporal revela un ciclo

Errores comunes

  • Insertar al final en lugar de al principio: el orden sale invertido. El orden correcto es el inverso del orden de inserción, equivalente al orden decreciente de tiempo de finalización.
  • No distinguir la marca temporal de la permanente: solo volver a encontrar una marca temporal revela un ciclo; la permanente indica un vértice ya resuelto.
  • Confundirlo con el bosque de profundidad común: aquí lo que importa es el orden de finalización, no el árbol.
Método por búsqueda en profundidad
  1. para todo vértice v hacer Marca[v] ← 0
  2. Orden_Top ← ∅
  3. mientras exista algún vértice v tal que Marca[v] = 0
     hacer Visita(v)
 
Visita(v)
  1. si Marca[v] ≠ 2 entonces   // si v no es permanente
     a. si Marca[v] = 1 entonces CICLO   // marca temporal
     b. Marca[v] ← 1                     // marca temporal
     c. para todo vértice w ∈ Γ⁺(v) hacer Visita(w)
     d. Marca[v] ← 2                     // marca permanente
     e. Orden_Top.InsertarAlPrincipio(v)

Emparejamiento

Algoritmo de Edmonds

Busca caminos M-aumentantes entre vértices expuestos, contrayendo las flores (blossoms) que aparecen, hasta que no quede ninguno.

O(n² · m)

Idea central

Por el teorema de Berge, M tiene cardinalidad máxima si y solo si no existe ningún camino M-aumentante. El algoritmo busca esos caminos en un bosque M-alternante; cuando una arista une dos vértices a distancia par del mismo árbol, aparece un ciclo impar, la flor (blossom), que se contrae en un pseudovértice.

Invariante

M ⊕ EP es siempre un emparejamiento con una arista más que M. Por el teorema de Edmonds, M es máximo en G si y solo si M/B es máximo en G/B, lo que justifica la contracción de las flores.

Requisitos del grafo

Requiere un grafo no dirigidoIgnora los pesos de las aristasTrata grafos generales, no solo bipartitos

Errores comunes

  • Usar solo búsqueda en anchura o en profundidad en un grafo general: sin tratar las flores, caminos M-aumentantes existentes dejan de encontrarse.
  • Ignorar la arista {v, w} cuando dist(w, F.raíz[w]) es impar: no genera un camino aumentante.
  • Confundir emparejamiento maximal con máximo: maximal solo significa que no admite añadir más aristas; máximo es el de mayor cardinalidad. Y un emparejamiento máximo no implica un emparejamiento perfecto.
Emparejamiento_Máximo(G)
  1. M ← ∅
  2. P ← Buscar_Camino_Aumentante(G, M)
  3. mientras (P ≠ ∅) hacer
     a. M ← M ⊕ EP
     b. P ← Buscar_Camino_Aumentante(G, M)
 
Buscar_Camino_Aumentante(G, M)
  1. F ← Inicializar_Bosque_Alternante(G, M)
  2. para todo vértice sin marcar v ∈ F tal que
     dist(v, F.raíz[v]) sea par hacer
     a. mientras ∃ arista e = {v, w} sin marcar hacer
        i.   si w ∉ F entonces Añadir_al_Bosque(M, F, v, w)
        ii.  si no, si dist(w, F.raíz[w]) es par entonces
               devolver Obtener_Nuevo_Camino(G, M, F, v, w)
        iii. Marcar la arista e
     b. Marcar el vértice v
  3. devolver ∅
 
Obtener_Nuevo_Camino(G, M, F, v, w)
  1. si F.raíz[v] ≠ F.raíz[w] entonces
       P ← ObtenerCamino(F, F.raíz[v], v)
            + ObtenerCamino(F, w, F.raíz[w])
  2. si no                          // flor (blossom)
     a. B ← ObtenerCamino(F, v, w) + v
     b. G′ ← Contraer_Flor_Grafo(G, B, z)
     c. M′ ← Contraer_Flor_Emparejamiento(M, B, z)
     d. P ← Buscar_Camino_Aumentante(G′, M′)
     e. si z ∈ P entonces P ← Expandir_Flor(P, G, B, z)
  3. devolver P

Coloración

Coloración voraz

Recorre los vértices en cualquier orden y asigna a cada uno el color de menor índice que no use ninguno de sus vecinos.

O(n + m)

Idea central

No existe un método eficiente para obtener la coloración mínima de un grafo, pero sí se puede obtener rápidamente una coloración aproximada: se recorren los vértices en cualquier orden y se asigna a cada uno el color de menor índice que no usen sus vecinos.

Invariante

En cada paso la coloración parcial es válida: color(v) ≠ color(w) para todo par de vértices adyacentes ya coloreados. Como un vértice tiene como máximo Δ(G) vecinos, el método nunca usa más de Δ(G) + 1 colores.

Requisitos del grafo

Requiere un grafo no dirigidoColoración aproximada, no necesariamente mínimaEl resultado depende del orden de los vértices

Errores comunes

  • Tomar el número de colores obtenido como el número cromático: el resultado depende del orden de los vértices y en general χ(G) es menor.
  • Olvidar las cotas conocidas: ω(G) ≤ χ(G) ≤ Δ(G) + 1 y, por el teorema de Brooks, χ(G) ≤ Δ(G) si G es simple, no completo y no es un ciclo impar.
  • Aplicarlo a un grafo dirigido: la coloración de vértices está definida para grafos no dirigidos.
Método voraz
  1. Considerar los vértices del grafo en cualquier orden
     v₁, v₂, . . ., vₙ
  2. Identificar los colores con índices, añadiendo más
     colores cuando sea necesario
  3. Colorear v₁ con el primer color
  4. En cada iteración, asignar al vértice actual el color
     de menor índice que no use ninguno de sus vecinos

Coloración

Algoritmo de Welsh-Powell

Ordena los vértices por grado no creciente y colorea con un mismo color todos los que no estén conectados a un vértice ya coloreado con él.

O(n² )

Idea central

Refinamiento del método voraz: los vértices se ordenan por grado no creciente y cada color se reparte en una pasada completa por la lista, coloreando todos los vértices que no estén conectados a uno ya coloreado con ese color.

Invariante

Cada color forma un conjunto independiente: ningún par de vértices con el mismo color es adyacente. El método termina porque cada pasada colorea al menos un vértice.

Requisitos del grafo

Requiere un grafo no dirigidoColoración aproximada, no necesariamente mínimaSuele usar menos colores que el método voraz

Errores comunes

  • Tomar el resultado como óptimo: existe un contraejemplo en el que Welsh-Powell usa 3 colores en un grafo bipartito, para el cual χ(G) = 2.
  • Abandonar el orden por grado al empezar un nuevo color: la lista ordenada se recorre desde el principio en cada pasada.
  • Colorear un vértice adyacente a otro ya coloreado con el color de la pasada actual: la comprobación se hace contra los vértices ya coloreados con ese color.
Algoritmo de Welsh-Powell
  1. Ordenar los vértices por grado no creciente
     v₁, v₂, . . ., vₙ
  2. Identificar los colores con índices, añadiendo más
     colores cuando sea necesario
  3. Colorear v₁ con el primer color
  4. Recorrer la lista de vértices coloreando todos los
     vértices no conectados a un vértice ya coloreado,
     usando siempre el mismo color
  5. Repetir el paso 4 para todos los vértices sin colorear
     usando un nuevo color, respetando siempre el orden de
     grado no creciente, hasta que todos estén coloreados