Définition - Que signifie le graphe bipartite?
Un graphe biparti est un graphe dans lequel un ensemble de sommets de graphe peut être divisé en deux jeux indépendants, et aucun deux sommets de graphe dans le même jeu ne sont adjacents. En d'autres termes, les graphiques bipartis peuvent être considérés comme égaux à deux graphiques colorables. Les graphes bipartites sont principalement utilisés dans la modélisation des relations, en particulier entre deux classes d'objets distinctes.
Un graphe bipartite est également appelé bigraphe.
Definir Tech explique Bipartite Graph
Un graphe biparti a deux ensembles de sommets, par exemple A et B, avec la possibilité que lorsqu'une arête est dessinée, la connexion puisse se connecter entre n'importe quel sommet de A à n'importe quel sommet de B. Si le graphe n'en contient aucun cycle impair (le nombre de sommets dans le graphe est impair), alors son spectre est symétrique. Le nombre chromatique, qui est le nombre minimum de couleurs requis pour colorer les sommets sans sommets adjacents partageant les mêmes couleurs, doit être inférieur ou égal à deux dans le cas d'un graphe biparti. Tous les types de graphes acycliques (graphes qui n'ont pas de cycles de graphes) sont des exemples de graphes bipartis. Un graphe cyclique est considéré biparti si tous les cycles impliqués sont de même longueur. Selon le théorème de coloration des lignes de Koning, tous les graphes bipartis sont des graphes de classe 1.
Les graphes bipartites sont largement utilisés dans la théorie du codage moderne en plus d'être utilisés dans la modélisation des relations.