Direkt zum Inhalt

Lexikon der Mathematik: bipartiter Graph

paarer Graph, ein Graph G, der eine Zerlegung der Eckenmenge E(G) in zwei paarweise disjunkte Teilmengen X und Y besitzt (d. h. XY = E(G) und XY = ∅), so daß jede Kante von G mit genau einer Ecke aus X und einer Ecke aus Y inzidiert. Man nennt X, Y Partitionsmengen oder kurz eine Partition bzw. Bipartition von G.

Ist zusätzlich jede Ecke aus X mit jeder Ecke aus Y durch eine Kante verbunden, so spricht man von einem vollständigen bipartiten Graphen, in Zeichen \({k}_{m,n}\), falls \(|X|=n\) und \(|Y|=m\) gilt.

Färbt man in einem bipartiten Graphen G mit der Bipartition X, Y die Eckenmenge X mit einer Farbe und die Eckenmenge Y mit einer weiteren Farbe, so erhält man eine Eckenfärbung von G mit zwei Farben.

Der wichtigste Charakterisierungssatz für bipartite Graphen wurde 1916 von König entdeckt und lautet wie folgt:

Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.

Nach diesem Satz sind z. B. Bäume (Baum) und Wälder (Wald) bipartite Graphen, denn sie besitzen überhaupt keine Kreise.

Da ein Kreis ungerader Länge keine 2-Eckenfärbung hat, ergibt sich aus dem Satz von König, daß ein Graph genau dann bipartit ist, wenn er zweifärbbar ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos