graphe biparti

Imaginez quatre points nommés A, B, 1 et 2. Placez A et B dans un camp, 1 et 2 dans l’autre, puis tracez seulement des traits qui passent d’un camp à l’autre. Le réseau obtenu est un graphe biparti. Deux points d’un même camp ne sont jamais reliés directement. Une autre façon de le voir consiste à colorier chaque camp d’une couleur différente : chaque trait possède alors une extrémité de chaque couleur.

Un graphe non orienté est biparti lorsque son ensemble de sommets se partage en deux sous-ensembles disjoints, notés U et V, tels que chaque arête relie un sommet de U à un sommet de V. Aucun sommet n’appartient aux deux parties, et deux sommets situés dans une même partie ne sont jamais adjacents. Avec E pour l’ensemble des arêtes, cette structure s’écrit :

Le symbole V(G) désigne ici tous les sommets du graphe G. La partition en deux parties équivaut à une coloration utilisant au plus deux couleurs, avec des couleurs différentes aux extrémités de chaque arête. Elle existe exactement lorsque le graphe ne contient aucun cycle de longueur impaire. Le théorème de König (1916), dû au mathématicien hongrois Dénes König, fournit cette caractérisation structurelle. Le graphe peut être non connexe : chaque composante doit alors respecter le même critère.

La structure repose sur quatre éléments. Les sommets sont les objets reliés. Les deux parties U et V répartissent tous ces sommets sans chevauchement. Les arêtes sont des paires qui doivent toujours avoir une extrémité dans U et l’autre dans V. Enfin, une 2-coloration peut servir de témoin : une couleur marque U et l’autre marque V.

La partition contraint donc les arêtes, tandis que les arêtes permettent de tester une partition proposée. La couleur ou la position dessinée d’un sommet ne définit pas à elle seule le graphe : seul compte le fait que les adjacences traversent la séparation. Ces données suffisent à reconstruire le graphe et à contrôler s’il est biparti.

Considérons les sommets A, B, 1 et 2. Les quatre arêtes sont A–1, A–2, B–1 et B–2. La partition proposée est U = {A, B} et V = {1, 2}. La figure rend cette séparation et ces quatre arêtes directement vérifiables.

1. On vérifie que U et V n’ont aucun sommet commun et réunissent bien les quatre sommets.
2. On examine A–1 : son extrémité A appartient à U et son extrémité 1 appartient à V.
3. Le même contrôle réussit pour A–2, B–1 et B–2.
4. On attribue une couleur à A et B, puis une seconde couleur à 1 et 2. Chaque arête relie alors deux couleurs différentes.

Le graphe est donc biparti. Pour refaire le contrôle autrement, on suit le cycle A–1–B–2–A : il possède quatre arêtes, donc une longueur paire. Il n’existe ici aucun cycle impair.

Pour tester un graphe, choisissez la couleur d’un sommet, puis imposez l’autre couleur à tous ses voisins. Continuez de proche en proche dans chaque composante. Si un sommet doit recevoir les deux couleurs, la tentative révèle un cycle impair et le graphe n’est pas biparti.

Pour modéliser des relations entre deux catégories, placez une catégorie dans U et l’autre dans V. Une arête représente alors seulement une relation entre catégories. Si des relations internes à une catégorie sont indispensables, ce modèle biparti ne convient plus sans modifier ce que représentent les sommets.

Pour relire un dessin, ignorez d’abord sa disposition visuelle. Cherchez une partition ou une 2-coloration valide : deux sommets dessinés côte à côte peuvent appartenir à des parties différentes, et des sommets éloignés peuvent appartenir à la même partie.

Graphe biparti et graphe biparti complet. Dans un graphe biparti, les arêtes présentes traversent toutes la partition. Dans un graphe biparti complet, chaque sommet de U est relié à chaque sommet de V. L’exemple A, B, 1, 2 est complet ; retirer l’arête A–1 le laisse biparti, mais il n’est plus complet.

Graphe biparti et graphe complet. Un graphe complet relie toute paire de sommets distincts. Dès qu’il possède trois sommets, ceux-ci forment un cycle de longueur 3, impair : il n’est donc pas biparti. Le graphe complet à deux sommets reste, lui, biparti.

Un dessin en deux colonnes ne suffit pas. Si une arête relie deux sommets rangés dans la même colonne, la séparation montrée n’est pas une bipartition. Il faut chercher une autre répartition ou effectuer une 2-coloration.

Un cycle impair bloque toute tentative. Sur un triangle, l’alternance de deux couleurs ramène à la première couleur après trois arêtes et crée un conflit. Un cycle pair, comme le cycle de longueur 4 de l’exemple, ne constitue pas un obstacle.

La connexité n’est pas requise. Un graphe formé de plusieurs composantes peut être biparti. Il faut recommencer la coloration dans chaque composante isolée ; une seule composante contenant un cycle impair suffit à faire échouer le graphe entier.

Les sommets isolés ne posent aucun problème. Sans arête incidente, un tel sommet peut être placé dans l’une ou l’autre partie. La bipartition n’est donc pas nécessairement unique, même lorsque le graphe est biparti.

Coloration d'un graphe — Pour approfondir le rôle des couleurs dans la séparation de sommets adjacents.

Graphe complet — Pour comparer la bipartition avec une structure où toutes les paires de sommets sont reliées.