Vérificateur de Graphe Cordal

Pseudocode

Tester la cordalité directement, en traquant un long cycle sans corde, coûte cher. La voie standard est indirecte: trouver un ordre d'élimination parfaite candidat, puis le vérifier.

// Etape 1: recherche de cardinalite maximale
poids[v] = 0 pour tout v; ordre = []
repeter V fois:
    choisir le v non numerote de plus grand poids
    ordre.prefixer(v)
    pour chaque voisin n de v non numerote: poids[n]++

// Etape 2: verifier que c est un ordre d elimination parfaite
pour chaque v dans ordre, a la position i:
    posterieurs = voisins de v apparaissant apres i
    si posterieurs est vide: continuer
    w = le sommet le plus precoce de posterieurs
    si un u de posterieurs n est pas adjacent a w:
        renvoyer NON cordal
renvoyer cordal

Un ordre d'élimination parfaite est un ordre dans lequel chaque sommet, pris avec ses voisins postérieurs, forme une clique. Un graphe est cordal exactement lorsqu'un tel ordre existe. La recherche de cardinalité maximale en produit toujours un si le graphe est cordal, l'étape de vérification est donc ce qui transforme un ordre heuristique en preuve, et c'est aussi elle qui détecte l'échec lorsqu'aucun tel ordre n'existe.

Exemple détaillé, étape par étape

Teste la cordalité d'un cycle de quatre sommets, puis ajoute une corde et teste à nouveau.

Graphe d'exemple: D'abord le cycle de 4 A-B, B-C, C-D, D-A. Ensuite le même graphe avec la corde A-C ajoutée.

1. Exécuter MCS sur le cycle de 4. La recherche de cardinalité maximale produit l'ordre D, C, B, A.
2. Vérifier D. D apparaît en premier. Ses voisins postérieurs dans l'ordre sont C et A. Le plus précoce d'entre eux est C, la vérification demande donc si A est adjacent à C. Dans le cycle de 4 pur, il ne l'est pas.
3. Rejeter. L'ordre n'est pas un ordre d'élimination parfaite, et puisque MCS en aurait trouvé un si le graphe avait été cordal, le cycle de 4 n'est pas cordal. C'est exact: A-B-C-D-A est un cycle de longueur 4 sans aucune corde.
4. Ajouter la corde A-C et retester. MCS redonne D, C, B, A. En vérifiant D, ses voisins postérieurs sont C et A, et A est désormais adjacent à C, la vérification passe donc. En vérifiant C, ses voisins postérieurs sont B et A, et le test n'exige que l'adjacence des autres au plus précoce, à savoir B; comme A-B est une arête, cela passe également. Chaque sommet restant a au plus un voisin postérieur et passe trivialement.

Le cycle de 4 pur n'est pas cordal; l'ajout de la seule corde A-C le rend cordal. C'est la définition rendue concrète: un graphe est cordal lorsque tout cycle de quatre sommets ou plus possède une arête reliant deux sommets non consécutifs de ce cycle. Le cycle de 4 est le plus petit contre-exemple possible, ce qui en fait le cas de test standard.

Complexité et son origine

Temps: O(V + E) · Espace: O(V + E)

La recherche de cardinalité maximale s'exécute en O(V + E) lorsqu'on la met en œuvre avec des seaux de sommets par poids, de sorte que sélectionner le maximum et incrémenter les voisins soient tous deux en temps amorti constant. La passe de vérification examine chaque sommet une fois et chacun de ses voisins postérieurs une fois, ce qui totalise O(V + E) à condition que les requêtes d'adjacence soient en temps constant via un ensemble de hachage. Le test complet est donc linéaire, ce qui constitue un résultat réellement surprenant: l'approche naïve consistant à énumérer les cycles et à vérifier la présence d'une corde dans chacun est exponentielle, et même une méthode plus fine fondée sur les cycles serait bien pire. Le BFS lexicographique est une alternative à MCS avec la même borne.

Quand utiliser Vérification de Chordalité, et quand l'éviter

La cordalité sert généralement de porte d'entrée: dès qu'un graphe est reconnu cordal, plusieurs problèmes NP-difficiles y deviennent linéaires.

Pièges fréquents

• Sauter l étape de vérification. MCS produit un ordre pour n'importe quel graphe, cordal ou non. Seule la passe de vérification distingue les deux cas. Prendre la sortie de MCS pour une preuve de cordalité revient à accepter tous les graphes.
• Mal lire la définition comme tout cycle a une corde. La condition ne s'applique qu'aux cycles de longueur 4 ou plus. Les triangles n'ont aucune paire de sommets non consécutifs et la satisfont donc trivialement. Tout graphe composé uniquement de triangles est cordal.
• Vérifier toutes les paires de voisins postérieurs. La vérification n'a besoin de comparer chaque voisin postérieur qu'au plus précoce d'entre eux, pas à tous les autres. Vérifier toutes les paires est correct mais transforme un algorithme linéaire en algorithme quadratique.
• Supposer que cordal signifie dense ou arborescent. Les arbres sont cordaux parce qu'ils n'ont aucun cycle, et les graphes complets sont cordaux parce que toute corde possible y figure déjà. La cordalité n'est pas une mesure de densité et la traverse de part en part.
• Oublier de tester chaque composante connexe. Un graphe n'est cordal que si toutes ses composantes le sont. MCS couvre naturellement les composantes lorsqu'il parcourt tous les sommets, mais une implémentation par composante doit itérer sur toutes.

Questions fréquentes

Qu'est-ce qu'un graphe cordal?

Un graphe cordal est un graphe dans lequel tout cycle de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non consécutifs de ce cycle. De façon équivalente, il n'a aucun cycle induit plus long qu'un triangle. Les arbres, les graphes complets et les graphes d'intervalles sont tous cordaux; le cycle de 4 pur est le plus petit graphe qui ne l'est pas.

Comment vérifie-t-on si un graphe est cordal?

Lance une recherche de cardinalité maximale pour produire un ordre d'élimination parfaite candidat, puis vérifie-le: pour chaque sommet, ses voisins apparaissant plus tard dans l'ordre doivent tous être adjacents au plus précoce d'entre eux. Si la vérification passe, le graphe est cordal; si elle échoue, aucun ordre d'élimination parfaite n'existe et il ne l'est pas. Le test complet est en O(V + E).

Qu'est-ce qu'un ordre d'élimination parfaite?

Un ordre des sommets dans lequel chaque sommet, pris avec ses voisins qui apparaissent après lui, forme une clique. Un graphe possède un tel ordre exactement lorsqu'il est cordal, ce qui explique qu'en trouver et en vérifier un constitue le test standard de cordalité.

Pourquoi les graphes cordaux comptent-ils?

Parce que plusieurs problèmes NP-difficiles en général y deviennent linéaires. Clique maximum, coloration de graphes, ensemble indépendant maximum et couverture minimale par cliques sont tous résolubles en O(V + E) sur un graphe cordal grâce à l'ordre d'élimination. Les graphes cordaux sont en outre exactement ceux qui admettent une décomposition arborescente en cliques, fondement des algorithmes fondés sur la largeur arborescente.

Tous les arbres sont-ils cordaux?

Oui, trivialement. La cordalité ne contraint que les cycles de longueur 4 ou plus, et un arbre n'a aucun cycle, la condition est donc satisfaite à vide. À l'autre extrême, les graphes complets sont cordaux eux aussi, puisque toute corde possible y est déjà présente.