§6: Bipartite Graphen

Chr.Nelius: Graphentheorie (WS 2015/16)
16
§6 : Bipartite Graphen
Häufig tritt die folgende Situation auf:
Die Eckenmenge E eines Graphen läßt sich in zwei disjunkte nichtleere Teilmengen U und V zerlegen,
so dass es Kanten nur zwischen einer Ecke aus U und einer Ecke aus V gibt, nicht aber zwischen
zwei Ecken aus U bzw. aus V . Man spricht dann von einem bipartiten Graphen.
U
V
(6.1) DEF: a) Ein Graph G = (E, K) heißt bipartit , wenn es zwei Teilmengen U und V
von E gibt mit folgenden Eigenschaften:
1)
U 6= ∅ , V 6= ∅
2)
E =U ∪V , U ∩V =∅
3)
jede Kante aus K hat eine Begrenzungsecke in U und eine Begrenzungsecke in V .
Das Paar (U, V ) heißt eine Bipartition von G .
b) Ein schlichter bipartiter Graph G mit der Bipartition (U, V ) heißt ein vollständig bipartiter
Graph , wenn jede Ecke aus U adjazent zu jeder Ecke aus V ist.
c) Ein vollständig bipartiter Graph G mit der Bipartition (U, V ) , für die |U | = m und |V | =
n gilt, wird mit Km,n bezeichnet.
(6.2) BEISPIELE: a) Der vollständig bipartite Graph K1,6 (Man nennt den Graphen K1,n
einen Stern–Graphen) :
Chr. Nelius: Graphentheorie (WS 2015/16)
17
b) Der vollständig bipartite Graph K2,3 :
c) Der vollständig bipartite Graph K3,3 :
d) Der Null–Graph Nn ist für n ≥ 2 bipartit.
(6.3) BEM: a) Ein bipartiter Graph hat mindestens zwei Ecken.
b) In einem bipartiten Graphen mit der Partition (U, V ) gibt es keine Kanten zwischen Ecken aus
U und auch keine Kanten zwischen Ecken aus V .
c) Ein bipartiter Graph hat keine Schlingen, kann aber parallele Kanten haben.
d) Der vollständig bipartite Graph Km,n hat genau m + n Ecken und m · n Kanten.
Wie lässt sich praktisch eine Bipartition eines Graphen bestimmen?
(6.4) SATZ: Sei G ein Graph mit mindestens 2 Ecken. Dann sind folgende Aussagen äquivalent:
a) G ist bipartit
b) G besitzt keine Schlingen, und die Ecken von G können so mit genau zwei Farben gefärbt werden,
dass je zwei adjazente Ecken unterschiedliche Farben haben.
(6.5) SATZ: Für einen Graphen G mit mindestens zwei Ecken sind folgende Aussagen äquivalent:
a) G ist bipartit
b) G enthält keine Schlingen, und jede Zusammenhangskomponente mit mindestens zwei Ecken ist
bipartit.
Chr. Nelius: Graphentheorie (WS 2015/16)
18
Wir untersuchen jetzt Kreise in bipartiten Graphen.
(6.6) SATZ: G = (E, K) sei ein bipartiter Graph mit der Bipartition (U, V ) . Dann gilt:
a) Jeder Kantenzug zwischen zwei Ecken aus U (bzw. zwischen zwei Ecken aus V ) hat eine gerade
Länge.
b) Jeder Kantenzug zwischen einer Ecke aus U und einer Ecke aus V hat eine ungerade Länge.
c) In einem bipartiten Graphen gibt es keine ungeraden Kreise.
Nach (6.6c) gibt es in einem bipartiten Graphen keine ungeraden Kreise. Wir wollen uns überlegen,
dass auch die Umkehrung gilt.
(6.7) SATZ: Für einen Graphen G mit mindestens zwei Ecken sind folgende Aussagen äquivalent:
a) G enthält keine ungeraden Kreise
b) G besitzt keine Schlingen, und zwischen je zwei verschiedenen Ecken von G kann es entweder
nur Wege gerader Länge oder nur Wege ungerader Länge geben.
(6.8) SATZ: (König, 1936)
Ein Graph mit mindestens zwei Ecken ist genau dann bipartit, wenn er keine ungeraden Kreise
enthält.
(6.9) FOLGERUNG: Jeder Baum–Graph mit mindestens zwei Ecken ist bipartit.

Download Report