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.

Ein einfacher Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit oder 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, sodass jeder Knoten aus A mit jedem Knoten aus B verbunden ist. Einen solchen Graphen bezeichnet man auch als Km,n, wobei m und n die Anzahl der Knoten von A und 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

Verallgemeinerung

Ein k-partiter Graph ist ein Graph, dessen Knotenmenge in k Partitionen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten einer Partition gibt.

Weblinks

 Commons: Bipartiter Graph – Sammlung von Bildern, Videos und Audiodateien

Wikimedia Foundation.

Synonyme:

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

  • bipartiter Graph — Umschlüsselung; Mapping; Entsprechung …   Universal-Lexikon

  • 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

  • Vollständig bipartiter Graph — Als vollständig bipartiten Graphen bezeichnet man in der Graphentheorie einen bipartiten Graphen, der eine Partition seiner Knotenmenge in zwei disjunkte Teilmengen besitzt, so dass jeder Knoten der einen Teilmenge mit jedem Knoten der anderen… …   Deutsch Wikipedia

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

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • K-regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Kubischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Metrischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schleifenfreier Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

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