Bipartiter Graph

K_3,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.

Definitionen

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 $v \in B$ und $w \in A$. 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 $K_{m,n}$, wobei $m$ und $n$ jeweils die Anzahl der Knoten von $A$ und $B$ sind. Ein vollständig bipartiter Graph, bei dem $m=1$ oder $n=1$ ist, heißt Sterngraph.

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

• Die Paarungszahl entspricht der Knotenüberdeckungszahl.
• Mit dem Algorithmus von Hopcroft und Karp lässt sich in $O(m\sqrt{n})$ eine größte Paarung finden und darüber auch die Stabilitätszahl bestimmen.
• Der chromatische Index entspricht seinem Maximalgrad. Eine gültige Kantenfärbung lässt sich in $O(n \cdot m)$ bestimmen.
• Ein regulärer bipartiter Graph besitzt ein perfektes Matching.
• Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.

Anwendung

• Petri-Netz

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