Graphe biparti

Exemple de graphe biparti quelconque

En théorie des graphes, un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles $U$ et $V$ telle que chaque arête ait une extrémité dans $U$ et l'autre dans $V$. En d'autres termes, les graphes bipartis sont précisément ceux dont le nombre chromatique est inférieur ou égal à 2.

Un graphe biparti permet notamment de représenter une relation binaire.

Il existe deux autres définitions équivalentes d'un graphe biparti. La première est purement graphique : Un graphe est biparti si et seulement s'il ne contient pas de cycle impair. La seconde est d'ordre polyédral : Un graphe est biparti si et seulement si son polytope des stables est décrit par les contraintes de clique de taille 2.

Un graphe biparti est dit biparti complet (ou encore est appelé une biclique) si chaque sommet de $U$ est relié à chaque sommet de $V$.

Exemple de graphe biparti complet