Biparti
- Biparti
-
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 Biparti de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
biparti — biparti, ie [ biparti ] ou bipartite [ bipartit ] adj. • 1361, 1768; bas lat. bipartitus, p. p. de bipartire, de bi (bis) et partire « partager » ♦ Qui est divisé en deux parties. « ces portillons bipartis, dont le haut ne se ferme que le soir »… … Encyclopédie Universelle
biparti — biparti, ie (bi par ti, tie) adj. Terme d histoire naturelle. Divisé en deux. Feuille bipartie, feuille divisée de manière que la scissure excède manifestement le milieu de la longueur. ÉTYMOLOGIE Bi pour bis, et partitus, partagé (voy.… … Dictionnaire de la Langue Française d'Émile Littré
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
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 … Wikipédia en Français
Graphe biparti complet — K3,2 Notation Km,n Nombre de sommets m + n … Wikipédia en Français
bipartite — biparti, ie [ biparti ] ou bipartite [ bipartit ] adj. • 1361, 1768; bas lat. bipartitus, p. p. de bipartire, de bi (bis) et partire « partager » ♦ Qui est divisé en deux parties. « ces portillons bipartis, dont le haut ne se ferme que le soir »… … Encyclopédie Universelle
bipartie — ● biparti, bipartie ou bipartite adjectif (de parti, participe passé de l ancien français partir, partager) Composé ou issu de deux éléments, de deux groupes : Comité biparti. Se dit d un organe partagé en deux sur plus de la moitié de sa… … Encyclopédie Universelle
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
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 da … Wikipédia en Français
Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
