Comprendre les bipartitions dans la théorie des graphes

Dans la théorie des graphes, une bipartition d'un graphe est une division de son ensemble de sommets en deux ensembles disjoints (appelés ensembles de partites) de telle sorte que toutes les arêtes connectent les sommets de différents ensembles de partites. En d'autres termes, il n'y a pas d'arêtes entre les sommets d'un même ensemble de parties.

Par exemple, considérons un graphe avec 4 sommets {a,b,c,d} et nous divisons l'ensemble de sommets en deux parties : {a,b} et {CD}. Le graphe est biparti car toutes les arêtes relient les sommets de différentes parties.

La bipartition peut être utilisée pour réduire la complexité des algorithmes pour les problèmes de graphe tels que le parcours de graphe, la recherche du chemin le plus court et la correspondance de graphe.