Enthéorie des graphes, un graphe est ditbiparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans.
Un graphe biparti permet notamment de représenter unerelation binaire.
Il existe plusieurs façons de caractériser un graphe biparti.
Supposons qu'un graphe est décomposé en deux partitions et telles que toute arête relie un sommet de à un sommet de. Considérons un cycle quelconque. Ce cycle passe alternativement par les deux parties et avant de rejoindre le sommet de départ et a donc une longueur paire.
La réciproque est quelque peu plus dure à démontrer. Supposons que l'on ait un graphe qui ne comporte que des cycles de longueur paire. Pour simplifier, supposons également que estconnexe (si jamais il ne l'était pas, on pourrait raisonner individuellement sur chaque composante connexe).
Comme est connexe, il possède unarbre couvrant. Notons une racine de cet arbre. Créons deux ensembles de sommets et de la manière suivante :
Les ensembles de sommets et sont disjoints et contiennent tous les sommets de. Cela ne suffit cependant pas à montrer que est biparti : en effet, rien ne garantit a priori que l'on n'ait pas une arête « en trop » de qui relie deux sommets de, par exemple.
Considérons deux sommets et de dans une même partie ( ou) et reliés par une arête. Le chemin qui relie à dans est forcément de longueur paire, par construction de et de. Si l'on ajoute l'arête, on obtient un cycle de longueur impaire, ce qui est interdit par hypothèse.
Il n'est donc pas possible d'avoir de tels sommets et reliés en « court-circuit ». Toutes les arêtes du graphe relient des sommets de à des sommets de, ce qui achève de montrer que est biparti.
Les graphes suivants sont bipartis : legraphe vide, lesarbres, lescycles de longueurs paires, leshypercubes et lesgrilles.
De plus, on définit les graphes bipartis suivants :
