Los Grafos Cordales Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

¿Qué Es un Grafo Cordal?

Un grafo cordal, también llamado grafo triangulado, es un grafo en el que todo ciclo de cuatro o más vértices tiene una cuerda. Una cuerda es una arista que une dos vértices del ciclo que no están contiguos a lo largo de él. Dicho de otro modo, un grafo cordal no contiene ningún ciclo inducido de longitud cuatro o más: todo ciclo largo queda partido en triángulos por aristas más cortas.

La definición suena estrecha, pero muchos grafos que ya conoces son cordales: los árboles, los grafos completos y los grafos de intervalos son todos cordales. La figura de abajo muestra el caso interesante más pequeño, un ciclo de cuatro vértices, en sus formas no cordal y cordal.

Cuerdas y Ciclos Inducidos

La palabra que hace el trabajo pesado es inducido. Un ciclo es inducido cuando las únicas aristas entre sus vértices son las propias aristas del ciclo. En cuanto aparece una cuerda, el ciclo largo deja de ser inducido: ha sido triangulado.

Así que las dos definiciones son la misma afirmación vista desde dos ángulos:

• Todo ciclo de longitud ≥ 4 tiene una cuerda, o de forma equivalente
• El grafo no tiene ningún ciclo inducido de longitud ≥ 4 (ningún C₄, C₅ inducido, etc.).

Los triángulos, al ser ciclos de longitud 3, siempre están permitidos y nunca necesitan cuerda. Por eso los grafos cordales dan la sensación de estar "hechos de triángulos".

Vértices Simpliciales y Órdenes de Eliminación

El verdadero poder de los grafos cordales viene de un teorema estructural. Primero, dos definiciones.

• Un vértice es simplicial si sus vecinos forman un clique, es decir, son todos adyacentes entre sí.
• Un orden de eliminación perfecto (PEO) es un orden v₁, v₂, …, vₙ de los vértices tal que cada vₚ es simplicial en el grafo que queda tras eliminar v₁ hasta vₚ₋₁.

El teorema de Fulkerson-Gross lo une todo:

Un grafo es cordal si y solo si tiene un orden de eliminación perfecto. Además, todo grafo cordal tiene al menos un vértice simplicial, así que siempre puedes empezar quitando uno.

Este es el motor detrás de todo algoritmo eficiente en grafos cordales. Una vez que tienes un PEO, puedes procesar los vértices en ese orden y resolver problemas de forma voraz, porque en cada paso los vecinos restantes del vértice forman un clique sin sorpresas.

Reconocer un Grafo Cordal

Dado un grafo, ¿cómo saber si es cordal? Podrías buscar ciclos inducidos, pero eso es lento. La ruta elegante usa la caracterización por PEO y se ejecuta en tiempo lineal, O(V + E).

1. Ejecuta una búsqueda en anchura lexicográfica (Lex-BFS) o una búsqueda de cardinalidad máxima. Ambas producen un orden de vértices visitando siempre a continuación el vértice con más vecinos ya visitados.
2. Invierte ese orden. Si el grafo es cordal, se garantiza que el inverso es un orden de eliminación perfecto.
3. Verifica que el candidato realmente es un PEO. Si lo es, el grafo es cordal; si la comprobación falla, no lo es.

La búsqueda se apoya en la búsqueda en anchura, adaptada para que los empates se rompan con etiquetas lexicográficas. El paso de verificación es la parte que vale la pena ver en código.

Verificar un Orden en Python

Aquí está la comprobación central: dado un grafo como conjunto de adyacencia y un orden candidato, decide si es un orden de eliminación perfecto. Para cada vértice, todos sus vecinos posteriores deben ser adyacentes al primero de ellos.

def is_perfect_elimination_order(graph, order):
    pos = {v: i for i, v in enumerate(order)}

    for v in order:
        # Vecinos de v que vienen después en el orden.
        later = [u for u in graph[v] if pos[u] > pos[v]]
        if len(later) <= 1:
            continue

        # v es simplicial aquí si y solo si esos vecinos posteriores forman un clique.
        # Basta comprobar que todos son adyacentes al primero, w.
        w = min(later, key=lambda u: pos[u])
        for u in later:
            if u != w and u not in graph[w]:
                return False   # w y u van tras v pero no son adyacentes

    return True

Si esto devuelve True para el orden Lex-BFS invertido, el grafo es cordal. Ese mismo PEO se reutiliza luego para resolver los problemas difíciles de abajo.

Por Qué Importan los Grafos Cordales

Los grafos cordales son grafos perfectos, una clase donde el número cromático siempre es igual al tamaño del clique más grande. Esa estructura reduce varios problemas famosamente difíciles a problemas fáciles. Dado un orden de eliminación perfecto, cada uno de estos se ejecuta en tiempo lineal.

Hay una joya más. Un grafo es cordal exactamente cuando tiene un árbol de cliques, una descomposición en árbol cuyas bolsas son los cliques maximales. Eso conecta los grafos cordales con el ancho de árbol: el ancho de árbol de un grafo es el menor tamaño máximo de clique posible, menos uno, sobre todas sus completaciones cordales. Para ver dónde encaja esta clase en el panorama más amplio, consulta las aplicaciones de la teoría de grafos y la hoja de ruta.

Aplicaciones en el Mundo Real

• Solucionadores de matrices dispersas: la eliminación gaussiana rellena ceros al ejecutarse, y minimizar ese relleno es exactamente el problema de añadir cuerdas para volver cordal un grafo, una completación cordal.
• Compiladores: la asignación de registros en código moderno en forma SSA se convierte en coloreado de grafos cordales, por lo que puede resolverse de forma óptima y rápida.
• Modelos probabilísticos: el algoritmo del árbol de unión para redes bayesianas triangula el grafo, es decir, lo hace cordal, y luego trabaja sobre su árbol de cliques.
• Bioinformática y planificación: los grafos de intervalos, una subclase cordal, modelan intervalos que se solapan, como segmentos de genes o franjas horarias.