Graphe bipartite
- Graphe bipartite
-
Graphe biparti
Exemple de graphe biparti quelconque
En théorie des graphes, un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles U et V telle que chaque arête ait une extrémité dans U et l'autre dans V. 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 il ne contient pas de cycle impair. La seconde est d'ordre polyédral : Un graphe est biparti si et seulement si son polytope des stables est décrit par les contraintes de clique de taille 2.
Un graphe biparti est dit biparti complet (ou encore est appelé une biclique) si chaque sommets de U est relié à chaque sommets de V.
Exemple de graphe biparti complet
Portail des mathématiques
Catégories : Famille de graphes | Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe bipartite de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe Petersen — Graphe de Petersen Graphe de Petersen Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier… … Wikipédia en Français
Graphe de Horton — Représentation du graphe de Horton. Nombre de sommets 96 Nombre d arêtes 144 Distribution des degrés 3 régulier Rayon 10 … Wikipédia en Français
Graphe de Barnette-Bosák-Lederberg — Représentation du graphe Barnette Bosák Lederberg Nombre de sommets 38 Nombre d arêtes 57 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe de Tutte — Représentation du graphe de Tutte Nombre de sommets 46 Nombre d arêtes 69 Distribution des degrés 3 régulier Rayon 5 … Wikipédia en Français
Graphe griffe — Représentation du graphe griffe. Nombre de sommets 4 Nombre d arêtes 3 Distribution des degrés 1 (3 sommets) 3 (1 sommet) Rayon … Wikipédia en Français
Graphe biparti complet — K3,2 Notation Km,n Nombre de sommets m + n … Wikipédia en Français
Bipartite — Graphe biparti Exemple de graphe biparti quelconque En théorie des graphes, un graphe est dit biparti s il existe une partition de son ensemble de sommets en deux sous ensembles U et V telle que chaque arête ait une extrémité dans U et l autre da … Wikipédia en Français
54-graphe de Ellingham-Horton — Représentation du 54 graphe de Ellingham Horton. Nombre de sommets 54 Nombre d arêtes 81 Distribution des degrés 3 régulier R … Wikipédia en Français
78-graphe de Ellingham-Horton — Représentation du 78 graphe de Ellingham Horton. Nombre de sommets 78 Nombre d arêtes 117 Distribution des degrés 3 régulier … Wikipédia en Français
92-graphe de Horton — Nombre de sommets 92 Nombre d arêtes 138 Distribution des degrés 3 régulier Rayon 11 Diamètre 12 Maille 6 Nombre chromatique 2 … Wikipédia en Français
