Vérificateur de Graphe Biparti

Pseudocode

Un graphe est biparti exactement lorsqu'il peut être colorié avec deux couleurs. Le test est donc un parcours qui colorie chaque sommet à l'opposé de son parent et guette une collision.

estBiparti(graphe):
    couleur = {} pour tous les sommets

    pour chaque sommet s sans couleur:   // chaque composante
        couleur[s] = 0
        file = [s]
        tant que la file est non vide:
            u = file.retirer()
            pour chaque voisin v de u:
                si v n a pas de couleur:
                    couleur[v] = 1 - couleur[u]
                    file.ajouter(v)
                sinon si couleur[v] == couleur[u]:
                    renvoyer faux    // cycle impair

    renvoyer vrai

La collision n'est pas un signal d'échec arbitraire, c'est une preuve. Si deux sommets adjacents reçoivent la même couleur, les chemins de l'arbre depuis chacun d'eux jusqu'à leur ancêtre commun, plus l'arête qui les relie, forment un cycle de longueur impaire. Les graphes bipartis sont exactement les graphes sans cycle impair, si bien que l'arête en conflit constitue un certificat que tu peux renvoyer à l'appelant.

Exemple détaillé, étape par étape

Colorie un cycle de quatre sommets avec deux couleurs, puis ajoute une corde et observe le même parcours le rejeter.

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

1. Colorier le cycle de 4 depuis A. A reçoit la couleur 0. Ses voisins B et D reçoivent la couleur 1. Depuis B, le voisin C n'a pas de couleur et reçoit 0. Depuis D, le voisin C est déjà colorié en 0 tandis que D vaut 1, ce qui est une différence valide, aucun conflit n'apparaît donc.
2. Résultat pour le cycle de 4. Les couleurs sont A 0, B 1, C 0, D 1. Le graphe est biparti, avec les parties {A, C} et {B, D}. Chaque arête relie les deux parties et aucune ne reste à l'intérieur de l'une d'elles.
3. Ajouter la corde A-C. A et C portent tous deux la couleur 0, la corde relie donc désormais deux sommets d'une même partie. Relance le parcours depuis A: A reçoit 0, et ses voisins B, D ainsi que C reçoivent tous 1.
4. Le conflit apparaît. En traitant B, dont la couleur est 1, son voisin C porte lui aussi la couleur 1. C'est une arête interne à une partie, l'algorithme renvoie donc faux sur l'arête B-C.
5. Pourquoi la corde casse tout. La corde crée le triangle A-B-C, un cycle de longueur 3. Les cycles impairs ne peuvent pas être coloriés avec deux couleurs: parcourir un cycle impair en alternant les couleurs te ramène au départ en exigeant l'opposé de celle qui s'y trouve déjà.

Le cycle de 4 est biparti avec les parties {A, C} et {B, D}; l'ajout de la corde A-C le rend non biparti, détecté sur l'arête B-C. Note la règle générale ainsi illustrée: tout cycle pair est biparti et tout cycle impair ne l'est pas, la seule longueur du cycle tranche donc. Note aussi que le conflit a été signalé sur l'arête B-C et non sur la corde elle-même, ce qui est normal, car l'algorithme signale l'endroit où la contradiction apparaît en premier, pas celui que tu tiendrais pour responsable.

Complexité et son origine

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

Il s'agit d'un unique BFS ou DFS avec une comparaison par arête, le coût est donc exactement celui d'un parcours. Chaque sommet est colorié une fois et chaque arête inspectée une fois depuis chaque extrémité. L'espace tient à une couleur par sommet plus la file ou la pile de récursion, les deux en O(V). La boucle sur tous les sommets n'ajoute rien asymptotiquement et c'est elle qui fait fonctionner les graphes non connexes. Il n'existe pas d'approche plus rapide, car décider la bipartition impose de regarder chaque arête: une seule arête non examinée pourrait être celle qui crée un cycle impair.

Quand utiliser Vérification Bipartite, et quand l'éviter

La bipartition est le plus souvent une condition préalable et non un but. Ce que tu fais ensuite dépend de la raison pour laquelle tu as posé la question.

Pièges fréquents

• Ne parcourir qu à partir d un seul sommet. Un graphe non connexe n'est biparti que si chaque composante l'est. Partir d'une unique source teste une composante et laisse passer en silence un graphe contenant un cycle impair ailleurs. Parcours tous les sommets et lance un nouveau parcours depuis chacun de ceux sans couleur.
• Traiter l absence de couleur comme une couleur. Utiliser 0 à la fois pour non visité et pour la partie zéro fait échouer le test de conflit. Emploie une sentinelle distincte, comme -1 ou l'absence dans une table, afin que pas encore de couleur et couleur 0 restent distinguables.
• Oublier que les boucles sont fatales. Une boucle sur soi-même est un cycle impair de longueur 1 et rend immédiatement un graphe non biparti. Un parcours qui saute le parent peut la manquer entièrement, vérifie donc explicitement les boucles.
• Croire que le cas intéressant est l acyclique. Tout arbre et toute forêt est trivialement biparti, puisqu'il n'y a aucun cycle. Le test ne prend son sens qu'une fois des cycles présents, si bien que des succès triviaux sur des entrées en forme d'arbre ne prouvent pas grand-chose.
• L appliquer à des graphes orientés sans symétriser. La bipartition est une propriété non orientée. Sur un graphe orienté, tu dois décider si une arête à sens unique compte comme adjacence et traiter les arêtes symétriquement, sans quoi la réponse n'est pas bien définie.

Questions fréquentes

Qu'est-ce qu'un graphe biparti?

Un graphe biparti est un graphe dont les sommets peuvent être répartis en deux ensembles de sorte que chaque arête relie un sommet de l'un à un sommet de l'autre, sans aucune arête à l'intérieur de l'un des deux. De façon équivalente, c'est un graphe coloriable correctement avec deux couleurs, et de façon encore équivalente, un graphe ne contenant aucun cycle de longueur impaire.

Comment vérifier si un graphe est biparti?

Lance un BFS ou un DFS en coloriant chaque sommet nouvellement atteint à l'opposé de celui d'où tu viens. Si tu trouves une arête dont les deux extrémités partagent déjà une couleur, le graphe n'est pas biparti. Recommence depuis chaque sommet sans couleur afin de couvrir toutes les composantes. Le test complet est en O(V + E).

Pourquoi les cycles impairs sont-ils le facteur décisif?

Parce que les couleurs doivent alterner le long de tout chemin. Parcourir un cycle de longueur paire te ramène au départ avec la couleur initiale, ce qui est cohérent. Parcourir un cycle impair te ramène en exigeant la couleur opposée à celle déjà attribuée, ce qui est contradictoire. Un graphe est donc biparti exactement lorsqu'il n'a aucun cycle impair.

Quelle est la complexité temporelle de la vérification de bipartition?

O(V + E) en temps et O(V) en espace. C'est un unique parcours avec une comparaison de couleur par arête. C'est optimal, car toute arête non examinée pourrait être celle qui crée un cycle impair, il faut donc toutes les regarder.

À quoi servent les graphes bipartis?

À modéliser toute relation à deux côtés: candidats et postes, étudiants et cours, acheteurs et vendeurs, documents et termes. Une fois qu'un graphe est connu comme biparti, le couplage maximal devient efficacement calculable par Hopcroft-Karp, ce qui sous-tend les problèmes d'affectation, l'ordonnancement et les systèmes de recommandation.