Verificador de Grafo Cordal

Pseudocódigo

Probar la cordalidad directamente, buscando un ciclo largo sin cuerdas, es caro. La vía estándar es indirecta: hallar un candidato a orden de eliminación perfecta y después verificarlo.

// Paso 1: búsqueda de cardinalidad máxima
peso[v] = 0 para todo v; orden = []
repetir V veces:
    elegir el v sin numerar de mayor peso
    orden.anteponer(v)
    para cada vecino n de v sin numerar: peso[n]++

// Paso 2: verificar que es un orden de eliminación perfecta
para cada v en orden, en la posición i:
    posteriores = vecinos de v que aparecen tras i
    si posteriores está vacío: continuar
    w = el vértice más temprano de posteriores
    si algún u de posteriores no es adyacente a w:
        devolver NO cordal
devolver cordal

Un orden de eliminación perfecta es aquel en el que cada vértice, junto con sus vecinos posteriores, forma un clique. Un grafo es cordal exactamente cuando existe tal orden. La búsqueda de cardinalidad máxima siempre produce uno si el grafo es cordal, así que el paso de verificación es lo que convierte un orden heurístico en una demostración, y es también lo que detecta el fallo cuando ese orden no existe.

Ejemplo resuelto, paso a paso

Prueba la cordalidad de un ciclo de cuatro vértices, después añade una cuerda y vuelve a probar.

Grafo de ejemplo: Primero el ciclo de 4 A-B, B-C, C-D, D-A. Después el mismo grafo con la cuerda A-C añadida.

1. Ejecutar MCS sobre el ciclo de 4. La búsqueda de cardinalidad máxima produce la ordenación D, C, B, A.
2. Verificar D. D aparece el primero. Sus vecinos posteriores en la ordenación son C y A. El más temprano de ellos es C, así que la comprobación pregunta si A es adyacente a C. En el ciclo de 4 puro no lo es.
3. Rechazar. La ordenación no es un orden de eliminación perfecta, y dado que MCS habría encontrado uno si el grafo fuese cordal, el ciclo de 4 no es cordal. Es correcto: A-B-C-D-A es un ciclo de longitud 4 sin ninguna cuerda.
4. Añadir la cuerda A-C y volver a probar. MCS vuelve a dar D, C, B, A. Verificando D, sus vecinos posteriores son C y A, y ahora A sí es adyacente a C, así que la comprobación pasa. Verificando C, sus vecinos posteriores son B y A, y la prueba solo exige que los demás sean adyacentes al más temprano, que es B; como A-B es una arista, también pasa. Cada vértice restante tiene a lo sumo un vecino posterior y pasa trivialmente.

El ciclo de 4 puro no es cordal; añadir la única cuerda A-C lo vuelve cordal. Esto es la definición hecha concreta: un grafo es cordal cuando todo ciclo de cuatro o más vértices tiene una arista que une dos vértices no consecutivos de ese ciclo. El ciclo de 4 es el contraejemplo más pequeño posible, y por eso es el caso de prueba estándar.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V + E)

La búsqueda de cardinalidad máxima corre en O(V + E) cuando se implementa con cubetas de vértices por peso, de modo que seleccionar el máximo e incrementar los vecinos sean ambos de coste amortizado constante. La pasada de verificación examina cada vértice una vez y cada uno de sus vecinos posteriores una vez, lo que totaliza O(V + E) siempre que las consultas de adyacencia sean de tiempo constante mediante un conjunto hash. Así que toda la prueba es lineal, lo cual es un resultado genuinamente sorprendente: el enfoque ingenuo de enumerar ciclos y comprobar si cada uno tiene cuerda es exponencial, e incluso un método basado en ciclos más astuto sería mucho peor. La BFS lexicográfica es una alternativa a MCS con la misma cota.

Cuándo usar Prueba de Cordalidad y cuándo no

La cordalidad suele ser una puerta de entrada: una vez que se sabe que un grafo es cordal, varios problemas NP-difíciles pasan a ser lineales sobre él.

Errores frecuentes

• Saltarse el paso de verificación. MCS produce una ordenación para cualquier grafo, sea cordal o no. Solo la pasada de verificación distingue ambos casos. Tratar la salida de MCS como demostración de cordalidad acepta todos los grafos.
• Leer mal la definición como que todo ciclo tiene cuerda. La condición se aplica solo a ciclos de longitud 4 o más. Los triángulos no tienen pares de vértices no consecutivos y por tanto la satisfacen trivialmente. Todo grafo formado solo por triángulos es cordal.
• Comprobar todos los pares de vecinos posteriores. La verificación solo necesita comparar cada vecino posterior con el más temprano de ellos, no con todos los demás. Comprobar todos los pares es correcto pero convierte un algoritmo lineal en uno cuadrático.
• Suponer que cordal implica denso o con forma de árbol. Los árboles son cordales porque no tienen ciclos en absoluto, y los grafos completos son cordales porque toda cuerda posible ya está presente. La cordalidad no es una medida de densidad y la atraviesa por completo.
• Olvidar probar cada componente conexa. Un grafo es cordal solo si lo son todas sus componentes. MCS abarca las componentes de forma natural cuando se implementa sobre todos los vértices, pero una implementación por componentes debe iterar sobre todas ellas.

Preguntas frecuentes

¿Qué es un grafo cordal?

Un grafo cordal es aquel en el que todo ciclo de cuatro o más vértices tiene una cuerda, es decir una arista que une dos vértices no consecutivos de ese ciclo. Equivalentemente, no tiene ningún ciclo inducido más largo que un triángulo. Los árboles, los grafos completos y los grafos de intervalos son todos cordales; el ciclo de 4 puro es el grafo más pequeño que no lo es.

¿Cómo se comprueba si un grafo es cordal?

Ejecuta una búsqueda de cardinalidad máxima para producir un candidato a orden de eliminación perfecta y después verifícalo: para cada vértice, sus vecinos que aparecen más tarde en la ordenación deben ser todos adyacentes al más temprano de ellos. Si la verificación pasa el grafo es cordal; si falla, no existe ningún orden de eliminación perfecta y el grafo no lo es. Toda la prueba es O(V + E).

¿Qué es un orden de eliminación perfecta?

Una ordenación de los vértices en la que cada vértice, tomado junto con sus vecinos que aparecen después, forma un clique. Un grafo tiene tal ordenación exactamente cuando es cordal, y por eso hallar y verificar una es la prueba estándar de cordalidad.

¿Por qué importan los grafos cordales?

Porque varios problemas NP-difíciles en general pasan a ser lineales sobre ellos. Clique máximo, coloración de grafos, conjunto independiente máximo y cobertura mínima por cliques son todos resolubles en O(V + E) sobre un grafo cordal usando el orden de eliminación. Los grafos cordales son además exactamente los que admiten una descomposición en árbol de cliques, base de los algoritmos guiados por ancho de árbol.

¿Son cordales todos los árboles?

Sí, trivialmente. La cordalidad solo restringe ciclos de longitud 4 o más, y un árbol no tiene ciclos en absoluto, así que la condición se satisface de forma vacía. En el otro extremo, los grafos completos también son cordales, ya que toda cuerda posible está presente.