Table des matières:
Définition - Que signifie le graphique bipartite?
Un graphe bipartite est un graphe dans lequel un ensemble de sommets de graphe peut être divisé en deux ensembles indépendants, et aucun sommet de graphe dans le même ensemble n'est adjacent. En d'autres termes, les graphiques bipartites 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 entières distinctes.
Un graphique bipartite est également appelé bigraphe.
Techopedia explique le graphique bipartite
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 doit pouvoir se connecter entre n'importe quel sommet en A à n'importe quel sommet en B. Si le graphe ne contient aucun cycle impair (le nombre de sommets dans le graphique est impair), puis son spectre est symétrique. Le nombre chromatique, qui est le nombre minimum de couleurs nécessaires pour colorer les sommets sans aucun sommet adjacent partageant les mêmes couleurs, doit être inférieur ou égal à deux dans le cas d'un graphe bipartite. Tous les types de graphes acycliques (graphes qui n'ont pas de cycles de graphes) sont des exemples de graphes bipartites. Un graphique cyclique est considéré comme bipartite 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.
