Bipartit
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:

  • bipartit — BIPARTÍT, Ă, bipartiţi, te, adj. Care este constituit din două părţi. ♢ convenţie (sau înţelegere etc.) bipartită = convenţie (sau înţelegere etc.) între două state, două partide etc. – Din fr. biparti, lat. bipartitus. Trimis de paula,… …   Dicționar Român

  • bipartit — bi|par|tit Mot Agut Adjectiu variable …   Diccionari Català-Català

  • bipartít — adj. m., pl. bipartíţi; f. sg. bipartítã, pl. bipartíte …   Romanian orthography

  • bipartit — bi|parti̱t, in fachspr. Fügungen: bi|parti̱tus, ...ti̱ta, ...ti̱tum [zu lat. bipartire, bipartitum = in zwei Teile teilen]: zweigeteilt, zweiteilig (Biol. u. Anat.); z. B. ↑Uterus bipartitus …   Das Wörterbuch medizinischer Fachausdrücke

  • Bipartit (Graphentheorie) — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Bipartite Graphen — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Bipartiter Graph — K3,3: vollständig bipartiter Graph mit 3 Knoten pro Teilmenge Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen.… …   Deutsch Wikipedia

  • Bipartition — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Paarer Graph — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Chordal bipartiter Graph — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses… …   Deutsch Wikipedia

Share the article and excerpts

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