Grafos y expresiones regulares

Avanzado · Actualizado el 16 de agosto de 2026

Este apéndice recoge las definiciones y resultados sobre grafos que los capítulos «4», «7» y «14» usan: caminos, ciclos, componentes fuertemente conexas, bosques y árboles, dominadores, y el orden inverso de postorden, que es el que hace rápidos los algoritmos de lista de trabajo. Cierra con las expresiones regulares de caminos, base de los métodos de eliminación.

C.1 Grafos, caminos y ciclos

Un grafo dirigido (digraph) G = (N, A) consta de un conjunto finito N de nodos y un conjunto A ⊆ N × N de aristas. Una arista (n₁, n₂) tiene origen n₁ y destino n₂, y se dice que va de n₁ a n₂; si n₁ = n₂ es un bucle propio (self-loop). Cuando no hay bucles propios se habla simplemente de grafo.

Un camino dirigido, o camino a secas, del nodo n₀ al nodo n_m es una secuencia de aristas (n₀,n₁), (n₁,n₂), …, (n_m-1, n_m) en la que el destino de cada arista es el origen de la siguiente. Su origen es n₀, su destino n_m, y su longitud es m ≥ 0. El camino es trivial si m = 0, y vacío si la secuencia de aristas es vacía. La concatenación de dos caminos con destino y origen coincidentes es un camino. Diremos que n' es alcanzable desde n si existe un camino, posiblemente trivial, de n a n'.

Se escribe el camino por la secuencia de nodos visitados,

p = [n₀, n₁, n₂, …, n_m]

y se define el conjunto de caminos de n a n':

paths_A(n, n') = \{ [n₀,…,n_m] : m ≥ 0 ∧ n₀ = n ∧ n_m = n' ∧ ∀i < m . (nᵢ, n_i+1) ∈ A \}

Un ciclo es un camino no trivial de un nodo a sí mismo; el caso m = 1 es el bucle propio. Los ciclos de n a n son

cycles(n) = \{ [n₀,…,n_m] : m ≥ 1 ∧ n₀ = n ∧ n_m = n \}

y se observa que cycles(n) = { p ∈ paths_A(n,n) : p ≠ [n] }. Un ciclo [n₀,…,n_m] es de entrada múltiple (multiple entry) si contiene dos nodos distintos n₁ y n₂ a los que se puede llegar desde fuera del ciclo. Ésa es exactamente la caracterización de la irreducibilidad del capítulo «4».

Un grafo sin ciclos es acíclico; un grafo dirigido acíclico es un DAG. Una ordenación topológica de un grafo dirigido es un orden total sobre sus nodos tal que si (n, n') ∈ A entonces n va estrictamente antes que n'. Un grafo dirigido admite ordenación topológica si y sólo si es acíclico.

C.2 Componentes fuertemente conexas

Dos nodos n y n' son fuertemente conexos si hay un camino, posiblemente trivial, de n a n' y otro de n' a n. Definiendo

SC = \{ (n, n') : n\ y\ n'\ son\ fuertemente\ conexos \}

se obtiene una relación binaria sobre N.

Formalización

SC es una relación de equivalencia y el grafo reducido es un DAG

Hecho. SC es una relación de equivalencia.

Demostración. La reflexividad se sigue de que hay un camino trivial de cualquier nodo a sí mismo; la simetría, de la propia definición; y la transitividad, de que si p₁₂ es un camino de n₁ a n₂ y p₂₃ uno de n₂ a n₃, su concatenación p₁₂p₂₃ es un camino de n₁ a n₃. ∎

Las clases de equivalencia de SC son las componentes fuertemente conexas (strong components) del grafo. Un grafo es fuertemente conexo si consta exactamente de una componente.

Las conexiones entre componentes se representan mediante el grafo reducido: cada componente es un nodo, y hay una arista de una a otra si en el grafo original hay una arista de algún nodo de la primera a algún nodo de la segunda.

Lema. Para todo grafo G, el grafo reducido es un DAG.

Demostración. Por reducción al absurdo, supóngase que el grafo reducido contiene un ciclo SC₁, …, SCₙ con SCₘ = SC₁. Como ya se ha observado, el grafo reducido no contiene bucles propios, luego el ciclo contiene dos componentes distintas SCᵢ y SCⱼ con i < j. Como hay arista de SC_k a SC_k+1 para todo k, hay en el grafo original un camino de algún nodo de SCᵢ a algún nodo de SCⱼ, y por ser el ciclo cerrado, también uno de vuelta. Componiéndolos con los caminos internos a cada componente se concluye que cualquier nodo de SCᵢ y cualquiera de SCⱼ son fuertemente conexos, es decir, SCᵢ = SCⱼ, contra la hipótesis. ∎

En el CFG de un programa escrito en un lenguaje estructurado, el cuerpo de un bucle constituye una componente fuertemente conexa, y esto vale tanto para el grafo de flujo hacia adelante como para el invertido. Es la base del algoritmo de iteración por componentes fuertemente conexas mencionado en el capítulo «7»: se resuelve componente a componente, en orden topológico del grafo reducido, y dentro de cada una se itera hasta punto fijo.

C.3 Asideros, bosques y árboles

Un asidero (handle) de un grafo G = (N, A) es un conjunto H ⊆ N tal que todo nodo de N es alcanzable desde algún nodo de H. Una raíz es un r ∈ N tal que {r} es asidero. Todo grafo tiene al menos un asidero, a saber H = N; un asidero es minimal si ningún subconjunto propio suyo lo es. Los asideros minimales siempre existen, pero no tienen por qué ser únicos, y sólo si el grafo tiene raíz un asidero minimal es un conjunto unitario.

Dado un asidero H, el conjunto de caminos de H a un nodo n es

path^H_*(n) = ⋃ \{ paths_A(h, n) : h ∈ H \}

y cuando H está claro por el contexto se escribe path_*(n).

Grados. El grado de entrada (in-degree) de un nodo n es el cardinal de {n' : (n', n) ∈ A}; el grado de salida, el de {n' : (n, n') ∈ A}. En el vocabulario del capítulo «4», un nodo de confluencia es uno de grado de entrada mayor que 1, y uno de bifurcación tiene grado de salida mayor que 1.

Bosques y árboles. Un bosque (forest) es un grafo dirigido acíclico en el que todos los nodos tienen grado de entrada a lo sumo 1. El conjunto de nodos de grado de entrada 0 constituye un asidero minimal. Si (n, n') ∈ A se dice que n es el padre de n' y n' un hijo de n; ancestro y descendiente son las clausuras reflexiva y transitiva de padre e hijo. Un árbol (tree) es un bosque con raíz.

Un bosque de recubrimiento (spanning forest) de un grafo es un bosque con los mismos nodos y un subconjunto de las aristas.

Dominadores. Dado un grafo G = (N, A) con asidero H, un nodo n' domina a n si todo camino, posiblemente trivial, de H a n contiene a n'.

Formalización

Los dominadores como mayor solución

El conjunto de dominadores se especifica como la mayor solución de la ecuación

Dom(n) = {n}                                        si n en H
       = {n} union (interseccion de Dom(n')
                    para todo (n', n) en A)          en otro caso

Nótese que se busca la mayor solución y no la menor. La razón es la del capítulo «6»: es un análisis must, la operación de combinación es la intersección, y en la orientación por ⊆ la solución más precisa es la mayor. En la orientación del capítulo «5», con ⊑ = ⊇, vuelve a ser la menor.

n' domina propiamente a n si n' ∈ Dom(n) \ {n}, y domina directamente —es el dominador inmediato— si es el más «cercano»: n' ∈ Dom(n)\{n} y para todo n'' ∈ Dom(n)\{n} se tiene n'' ∈ Dom(n').

Como consecuencia de la definición de camino, el único dominador de un elemento de un asidero minimal es él mismo.

C.4 Orden inverso de postorden

Ésta es la sección con más consecuencias prácticas del apéndice.

El algoritmo de bosque de recubrimiento en profundidad (depth-first spanning forest, DFSF) construye no deterministamente un bosque de recubrimiento y, en paralelo, genera una numeración de los nodos:

ENTRADA:  un grafo dirigido (N, A) con k nodos y asidero H
SALIDA:   (1) un DFSF  T = (N, A_T)
          (2) una numeracion rPostorder de los nodos que indica el orden
              inverso en el que fueron visitados por ultima vez

METODO:
    i := k
    marcar todos los nodos de N como no visitados
    A_T := vacio
    while queden nodos no visitados en H do
        elegir h en H no visitado
        DFS(h)

procedure DFS(n):
    marcar n como visitado
    while exista (n, n') en A con n' no visitado do
        anadir (n, n') a A_T
        DFS(n')
    rPostorder[n] := i
    i := i - 1

La numeración se llama orden inverso de postorden (reverse postorder, rPO) y se representa como un array indexado por los nodos. Si el DFSF es un árbol se llama árbol de recubrimiento en profundidad (DFST); nótese que el algoritmo no especifica qué nodo no visitado se elige en cada paso, así que el bosque no es único.

Clasificación de las aristas. Dado un bosque de recubrimiento, las aristas del grafo original se clasifican en cuatro clases:

aristas de árbol (tree edges): las presentes en el bosque de recubrimiento;
aristas hacia adelante (forward edges): las que no son de árbol y van de un nodo a un descendiente propio suyo en el árbol;
aristas de retroceso (back edges): las que van de un descendiente a un ancestro, incluidos los bucles propios;
aristas cruzadas (cross edges): las que van entre nodos no relacionados por ancestro/descendiente.

Formalización

La propiedad que hace útil el orden inverso de postorden

El algoritmo anterior garantiza que las aristas cruzadas van siempre de nodos visitados más tarde a nodos visitados antes, es decir, de números rPostorder menores a mayores.

Combinando esto con la clasificación anterior se obtiene el resultado operativo: recorriendo los nodos en orden creciente de rPostorder, todo nodo se visita después que sus predecesores, salvo por las aristas de retroceso. Ésa es exactamente la propiedad que se necesita para que la iteración de un análisis hacia adelante converja rápido: la información fluye en el mismo sentido en que se recorre, y sólo hay que dar vueltas adicionales por los bucles.

De ahí el resultado del capítulo «7»: para un CFG reducible y un problema de vector de bits hacia adelante, el algoritmo round-robin en orden inverso de postorden converge en d + 2 pasadas, con d la conectividad de bucle del grafo. Y de ahí también la regla práctica de que un análisis hacia atrás debe recorrerse en orden de postorden del grafo invertido.

Obsérvese que las aristas de retroceso identificadas por el DFSF no coinciden necesariamente con las aristas de retroceso definidas por dominancia en el capítulo «4»: las primeras dependen del bosque elegido, las segundas no. En grafos reducibles ambas nociones coinciden, y esa coincidencia es una caracterización más de la reducibilidad.

C.5 Expresiones regulares de caminos

La última pieza. El conjunto de caminos de un nodo a otro en un grafo finito es en general infinito —hay ciclos— pero es siempre un lenguaje regular sobre el alfabeto de las aristas. Por tanto puede describirse mediante una expresión regular de caminos (path expression), construida con concatenación, unión y clausura de Kleene.

Eso abre una vía alternativa para resolver problemas de flujo de datos, los llamados métodos de eliminación (elimination methods), por oposición a los métodos iterativos del capítulo «7»:

calcular una expresión regular que describa el conjunto de caminos desde la entrada hasta cada nodo;
interpretar esa expresión en el dominio abstracto, sustituyendo la concatenación por composición de funciones de transferencia, la unión por ⊔ y la clausura de Kleene por el cierre de la función de transferencia, f* = ⊔ₙ fⁿ.

El resultado es la solución MOP del capítulo «7», calculada sin iterar. Su interés práctico es doble: es más eficiente en grafos con estructura regular, y es la técnica natural cuando el mismo grafo se analiza muchas veces con dominios distintos, porque la expresión de caminos se calcula una sola vez.

Su limitación es que requiere poder calcular el cierre f* en el dominio abstracto, cosa que no siempre es posible ni barata; en los marcos de vector de bits es trivial, en los dominios numéricos no.

Las expresiones regulares de caminos aparecen también en el capítulo «16», en el cálculo de las puertas de la forma GSA: la puerta de una función γ es precisamente la expresión de caminos de la arista de entrada correspondiente.

En ingeniería inversa

Lo que hay que llevarse de este apéndice

Tres cosas, todas con efecto directo sobre el rendimiento de una herramienta de análisis de binarios:

Ordene por orden inverso de postorden. Es la optimización más barata y de mayor efecto en cualquier análisis hacia adelante. Una implementación que procese los bloques por dirección creciente en lugar de por rPO paga un factor que puede ser de un orden de magnitud en funciones con bucles anidados.

Trate las componentes fuertemente conexas por separado. Resolver el grafo reducido en orden topológico y hacer punto fijo sólo dentro de cada componente evita revisitar todo el CFG cada vez que un bucle interno cambia.

Y recuerde que el bosque en profundidad no es único. Las aristas clasificadas como «de retroceso» por un DFS dependen del orden en que se eligieron los sucesores; sólo la definición por dominancia del capítulo «4» es independiente del recorrido. En un grafo irreducible las dos nociones divergen, y una herramienta que las confunda identificará bucles distintos en ejecuciones distintas —un síntoma desconcertante y sorprendentemente frecuente—.

C.6 Notas

El capítulo «4» cubre este mismo material desde el punto de vista del análisis de binarios y añade la frontera de dominancia; los algoritmos eficientes de cálculo de dominadores se citan allí.

La «sección C.5 · Expresiones regulares de caminos» sintetiza la literatura sobre métodos de eliminación, cuya referencia canónica es Tarjan (1981).