Bipartition
bipartiter Graph

allgemeiner:

Beispiele:

K3,3: vollständig bipartiter Graph mit 3 Knoten pro Teilmenge

Ein einfacher Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt in der Graphentheorie bipartit (auch paar), falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen. Das heißt für eine Kante \{v,w\} \in E gilt entweder v \in A und w \in B oder aber w \in A und v \in B. Die Menge {A, B} bezeichnet man dann als Bipartition des Graphen G. Vereinfacht dargestellt, ist ein bipartiter Graph ein Graph, in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.

Der Graph G heißt vollständig bipartit, falls eine Bipartition {A,B} existiert, für die für jedes Paar (a,b) mit a \in A und b \in B die Kante {a,b} zu E gehört (d.h. jeder Knoten aus A ist mit jedem Knoten aus B verbunden, wie in der Graphik rechts zu sehen). Einen solchen Graphen bezeichnet man auch als Km,n, wobei m und n die Anzahl der Knoten von A bzw. B sind.

Inhaltsverzeichnis

Folgerungen

Die Teilmengen A und B sind also schon nach Definition stabile Mengen und die Bipartition impliziert eine mögliche 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit.

Für bipartite Graphen lassen sich viele Grapheneigenschaften mit weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.

Mit einem einfachen Algorithmus, der auf Tiefensuche basiert, lässt sich in linearer Zeit bestimmen, ob ein Graph bipartit ist, und eine gültige Partition bzw. 2-Färbung ermitteln.

Eigenschaften

Anwendung

Petri-Netz

Siehe auch

k-partiter Graph

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • bipartition — [ bipartisjɔ̃ ] n. f. • 1751; lat. bipartitio ♦ Didact. Division en deux parties. Bipartition cellulaire. ● bipartition nom féminin Partage d une cellule vivante en deux cellules filles identiques entre elles. bipartition n. m. Division en deux… …   Encyclopédie Universelle

  • Bipartition — Bi par*ti tion, n. The act of dividing into two parts, or of making two correspondent parts, or the state of being so divided. [1913 Webster] …   The Collaborative International Dictionary of English

  • bipartition — index dichotomy Burton s Legal Thesaurus. William C. Burton. 2006 …   Law dictionary

  • bipartition — dvidalis dalijimasis statusas T sritis fizika atitikmenys: angl. binary fission; bipartition vok. binäre Spaltung, f rus. деление на две части, n pranc. bipartition, f; fission binaire, f …   Fizikos terminų žodynas

  • bipartition — noun see bipartite …   New Collegiate Dictionary

  • Bipartition — Scissiparité La reproduction par scissiparité est un mode de multiplication asexué qui se réalise simplement par division de l organisme. Divers organismes sont scissipares, tels : les bactéries (par exemple, les Rickettsia) Entamoeba… …   Wikipédia en Français

  • bipartition — See bipartitely. * * * …   Universalium

  • bipartition — noun Something that is bipartite …   Wiktionary

  • bipartition — (bi par ti sion) s. f. Terme didactique. Division en deux parties. ÉTYMOLOGIE    Biparti …   Dictionnaire de la Langue Française d'Émile Littré

  • Bipartition — Halvering …   Danske encyklopædi

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”