Bipartite
- 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 Bipartite de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Bipartite — means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:* 2 (number)In mathematics: * Bipartite graph * Bipartite Cubic, a type of Cubic function * Bipartite matching, a type of… … Wikipedia
Bipartite — Bip ar*tite, a. [L. bipartitus, p. p. of bipartire; bis twice + partire. See {Partite}.] 1. Being in two parts; having two correspondent parts, as a legal contract or writing, one for each party; shared by two; as, a bipartite treaty. [1913… … The Collaborative International Dictionary of English
bipartite — bipartite, bipartisan Affecting two parties (‘bipartite agreement’) or divided into two parts. The term is mostly employed in reference to formal economic and political negotiations and arrangements. For example, a number of social scientists… … Dictionary of sociology
bipartite — [bī pär′tīt΄] adj. [L bipartitus, pp. of bipartire < bi , BI 1 + partire, to PART2] 1. having two parts 2. having two corresponding parts, one each for the two parties to a contract 3. with two involved [a bipartite alliance] … English World dictionary
bipartite — I adjective apart, being in two corresponding parts, bicameral, bifurcated, bifurcous, bisected, detached, dichotomous, disconnected, disengaged, disjoined, disjointed, disjunct, disunited, divaricate, divided, furcate, furcular, halved, in two,… … Law dictionary
bipartite — (adj.) 1570s, from L. bipartitus divided, pp. of bipartire to divide into two parts, from bi (see BI (Cf. bi )) + partiri (see PART (Cf. part) (v.)) … Etymology dictionary
bipartite — ► ADJECTIVE 1) involving two separate parties. 2) technical consisting of two parts … English terms dictionary
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
bipartite — adjective Etymology: Latin bipartitus, past participle of bipartire to divide in two, from bi + partire to divide, from part , pars part Date: 1574 1. a. being in two parts b. having a correspondent part for each of two parties < a bipartite… … New Collegiate Dictionary
bipartite — bipartitely, adv. bipartition /buy pahr tish euhn/, n. /buy pahr tuyt/, adj. 1. divided into or consisting of two parts. 2. Law. being in two corresponding parts: a bipartite contract. 3. shared by two; joint: a bipartite pact; bipartite rule. 4 … Universalium
bipartite — bi|par|tite [baıˈpa:taıt US ˈpa:r ] adj [Date: 1500 1600; : Latin; Origin: bipartitus, from bi + partitus divided ] formal involving two different parts or groups ▪ a bipartite treaty ▪ bipartite DNA structures … Dictionary of contemporary English
