Bipartiter Graph

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

1 Definition

1.1 Formal

2 Folgerungen

3 Eigenschaften

4 Siehe auch

Definition

K _{3 3}: bipartiter Graph mit
3 Knoten pro Teilmenge

Ein Graph heißt in der Graphentheorie bipartit (auch paar ) falls sich seine Knoten in zwei disjunkte Teilmengen aufteilen lassen ( Bipartition ) so dass es zwischen den Knoten einer Teilmenge keine Kanten gibt.

Formal

Ein Graph <math>K_{m n}:=G(E K)</math> heißt bipartit falls <math>E=A+B</math> aus zwei disjunkten Teilmengen A und B besteht mit <math>|A|=m \ |B|=n</math> und alle Kanten <math>ab \in K</math> mit <math>a A \ b \in B</math> gilt.

Ein Graph <math>K_{m n}</math> heißt vollständig bipartit falls <math>|E|=m+n \ |K|=m \cdot n</math> <math>E := \{ab\ |\ \forall\ a \in b \in B\}</math> d.h. alle Kanten zwischen A und B sind vorhanden.

Folgerungen

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

Für bipartite Graphen lassen sich viele Grapheigenschaften effektiv berechnen die für allgemeine Graphen effizient bzw. nicht in polynomieller Zeit bestimmt können.

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

Eigenschaften

Die Paarungszahl entspricht der Knotenüberdeckungszahl .
Mit dem Algorithmus von Hopcroft und lässt sich in O(√nm) eine größte Paarung und darüber auch die Stabilitätszahl bestimmen.
Der chromatische Index entspricht seinem Maximalgrad . Eine gültige Kantenfärbung lässt sich in bestimmen.
Ein regulärer bipartiter Graph besitzt ein perfektes Matching .

Siehe auch

k-partiter Graph Typen von Graphen in der Graphentheorie

Bücher zum Thema Bipartiter Graph

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Bipartiter_Graph.html">Bipartiter Graph </a>