Graphe biparti
Un article de Wikipédia, l'encyclopédie libre.
En théorie des graphes, un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles 
et 
telle que chaque arête ait une extrémité dans et l'autre dans . 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édrique : un graphe est biparti si et seulement si son polytope des stables est décrit par les contraintes de clique de taille 2.
Graphes bipartis particuliers [modifier]
- Un graphe biparti est dit biparti complet (ou encore est appelé une biclique) si chaque sommet de
est relié à chaque sommet de 
. - Un graphe biparti est dit birégulier si tous les sommets de ont le même degré, et si tous les sommets de ont le même degré.
- Les graphes bipartis de Kneser sont une famille de graphes bipartis permettant de décrire des relations d'inclusion entre ensembles.
