Graphe biparti
En théorie des graphes, un graphe est dit biparti 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 une relation binaire.
Caractérisation
modifierIl existe plusieurs façons de caractériser un graphe biparti.
- Par le nombre chromatique
- Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2.
- Par la longueur des cycles
- Un graphe est biparti si et seulement s'il ne contient pas de cycle impair[1].
- Si est une valeur propre de la matrice d'adjacence du graphe, alors en est aussi une, avec la même multiplicité que celle de .
- Par les polyèdres
- 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
modifierLes graphes suivants sont bipartis : le graphe vide, les arbres, les cycles de longueurs paires, les hypercubes et les grilles.
De plus, on définit les graphes bipartis suivants :
- 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.
- 110-graphe de Iofinova-Ivanov
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bipartite graph » (voir la liste des auteurs).
- (en) Armen S. Asratian, Tristan M. J. Denley et Roland Häggkvist, « Bipartite Graphs and their Applications », Cambridge Tracts in Mathematics, Cambridge University Press, vol. 131, (ISBN 9780521593458), Théorème 2.1.3, p. 8. Les auteurs attribuent cette caractérisation à Dénes Kőnig dans un article de 1916.
- (en) Norman Biggs, Algebraic Graph Theory, Cambridge University Press, , 2e éd., 205 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 53.
Voir aussi
modifierArticles connexes
modifier