Les Graphes Cordaux expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Qu'est-ce qu'un Graphe Cordal ?

Un graphe cordal, aussi appelé graphe triangulé, est un graphe dans lequel tout cycle de quatre sommets ou plus possède une corde. Une corde est une arête qui relie deux sommets du cycle non voisins le long de celui-ci. Autrement dit, un graphe cordal ne contient aucun cycle induit de longueur quatre ou plus : tout long cycle est découpé en triangles par des arêtes plus courtes.

La définition paraît étroite, mais beaucoup de graphes que vous connaissez déjà sont cordaux : les arbres, les graphes complets et les graphes d'intervalles sont tous cordaux. La figure ci-dessous montre le plus petit cas intéressant, un cycle à quatre sommets, sous ses formes non cordale et cordale.

Cordes et Cycles Induits

Le mot qui fait tout le travail est induit. Un cycle est induit lorsque les seules arêtes entre ses sommets sont les arêtes du cycle elles-mêmes. Dès qu'une corde apparaît, le long cycle n'est plus induit : il a été triangulé.

Les deux définitions sont donc le même énoncé vu sous deux angles :

• Tout cycle de longueur ≥ 4 possède une corde, ou de façon équivalente
• Le graphe n'a aucun cycle induit de longueur ≥ 4 (pas de C₄, C₅ induit, et ainsi de suite).

Les triangles, étant des cycles de longueur 3, sont toujours autorisés et n'ont jamais besoin de corde. C'est pourquoi les graphes cordaux donnent l'impression d'être "faits de triangles".

Sommets Simpliciaux et Ordres d'Élimination

La vraie puissance des graphes cordaux vient d'un théorème structurel. D'abord, deux définitions.

• Un sommet est simplicial si ses voisins forment une clique, c'est-à-dire s'ils sont tous deux à deux adjacents.
• Un ordre d'élimination parfait (PEO) est un ordre v₁, v₂, …, vₙ des sommets tel que chaque vₚ est simplicial dans le graphe qui reste après avoir retiré v₁ jusqu'à vₚ₋₁.

Le théorème de Fulkerson-Gross relie le tout :

Un graphe est cordal si et seulement s'il possède un ordre d'élimination parfait. De plus, tout graphe cordal a au moins un sommet simplicial, si bien que vous pouvez toujours commencer par en détacher un.

C'est le moteur derrière tout algorithme efficace sur les graphes cordaux. Une fois que vous avez un PEO, vous pouvez traiter les sommets dans cet ordre et résoudre les problèmes de façon gloutonne, car à chaque étape les voisins restants du sommet forment une clique sans surprise.

Reconnaître un Graphe Cordal

Étant donné un graphe, comment savoir s'il est cordal ? On pourrait chasser les cycles induits, mais c'est lent. La voie élégante utilise la caractérisation par PEO et s'exécute en temps linéaire, O(V + E).

1. Exécutez un parcours en largeur lexicographique (Lex-BFS) ou une recherche de cardinalité maximale. Les deux produisent un ordre des sommets en visitant toujours ensuite le sommet ayant le plus de voisins déjà visités.
2. Inversez cet ordre. Si le graphe est cordal, l'inverse est garanti d'être un ordre d'élimination parfait.
3. Vérifiez que le candidat est bien un PEO. Si c'est le cas, le graphe est cordal ; si la vérification échoue, il ne l'est pas.

La recherche repose sur le parcours en largeur, adapté pour que les égalités soient départagées par des étiquettes lexicographiques. L'étape de vérification est la partie qui mérite d'être vue en code.

Vérifier un Ordre en Python

Voici la vérification centrale : étant donné un graphe sous forme d'ensemble d'adjacence et un ordre candidat, décidez s'il s'agit d'un ordre d'élimination parfait. Pour chaque sommet, tous ses voisins postérieurs doivent être adjacents au premier d'entre eux.

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

    for v in order:
        # Voisins de v qui viennent plus tard dans l'ordre.
        later = [u for u in graph[v] if pos[u] > pos[v]]
        if len(later) <= 1:
            continue

        # v est simplicial ici si et seulement si ces voisins postérieurs forment une clique.
        # Il suffit de vérifier qu'ils sont tous adjacents au premier, 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 et u suivent v mais ne sont pas adjacents

    return True

Si cela renvoie True pour l'ordre Lex-BFS inversé, le graphe est cordal. Ce même PEO est ensuite réutilisé pour résoudre les problèmes difficiles ci-dessous.

Pourquoi les Graphes Cordaux Comptent

Les graphes cordaux sont des graphes parfaits, une classe où le nombre chromatique est toujours égal à la taille de la plus grande clique. Cette structure ramène plusieurs problèmes réputés difficiles à des problèmes faciles. Étant donné un ordre d'élimination parfait, chacun d'eux s'exécute en temps linéaire.

Il y a un dernier joyau. Un graphe est cordal exactement lorsqu'il possède un arbre de cliques, une décomposition arborescente dont les sacs sont les cliques maximales. Cela relie les graphes cordaux à la largeur arborescente : la largeur arborescente d'un graphe est la plus petite taille maximale de clique possible, moins un, sur toutes ses complétions cordales. Pour situer cette classe dans le paysage plus large, voir les applications de la théorie des graphes et la feuille de route.

Applications Concrètes

• Solveurs de matrices creuses : l'élimination de Gauss remplit des zéros au fil de son exécution, et minimiser ce remplissage est exactement le problème d'ajouter des cordes pour rendre un graphe cordal, une complétion cordale.
• Compilateurs : l'allocation de registres sur le code moderne en forme SSA devient une coloration de graphe cordal, c'est pourquoi elle peut être résolue de façon optimale et rapide.
• Modèles probabilistes : l'algorithme de l'arbre de jonction pour les réseaux bayésiens triangule le graphe, c'est-à-dire le rend cordal, puis travaille sur son arbre de cliques.
• Bio-informatique et ordonnancement : les graphes d'intervalles, une sous-classe cordale, modélisent des intervalles qui se chevauchent, comme des segments de gènes ou des créneaux horaires.