Ungerichteter Graph/Bipartit/Einführung/Textabschnitt

Die Zerlegung

Ein Sterngraph ist ein vollständiger bipartiter Graph der Form ${}K_{1,s}$.

Definition

Ein Graph ${}G=(V,E)$ heißt bipartit, wenn es eine disjunkte Zerlegung

${}V=A\uplus B\,$

derart gibt, dass es nur Kanten zwischen ${}A$ und ${}B$ gibt.

${}V=A\uplus B\,$

nennt man dann auch eine bipartite Unterteilung. Bei einem bipartiten Graphen gibt es im Allgemeinen mehrere Möglichkeiten für eine solche Zerlegung, man denke etwa an eine disjunkte Vereinigung von einzelnen Kanten. Wenn aber der Graph zusammenhängend ist, so ist die bipartite Unterteilung eindeutig bestimmt, siehe Aufgabe.

Beispiel

Bei einem Fußballspiel möchte man wissen, wer gegen wen im Verlauf des Spieles einen Zweikampf geführt hat, und dies durch einen Graphen darstellen. Da man innerhalb seiner Mannschaft keinen Zweikampf führt, ergibt sich ein bipartiter Graph, es ergeben sich nur Kanten zwischen den Spielern der einen und der anderen Mannschaft.

Beispiel

In einer heteronormativen Welt besteht die erwachsene Menschheit aus Männern und Frauen und nur diese haben miteinander Sex. Deshalb ergibt die Frage, wer mit wem schon einmal Sex hatte, einen bipartiten Graphen.

Beispiel

In Vorbereitung auf einen Schulaustausch zwischen einer Klasse in Osnabrück und einer Klasse in Málaga werden Brieffreundschaften geschnürt, wobei man mehrere Brieffreunde haben kann, aber nur mit Leuten aus der anderen Stadt. Mit den beiden Klassen ${}A$ und ${}B$ ergibt sich ein bipartiter Graph auf ${}V=A\uplus B$, bei dem eine Person aus ${}A$ mit einer Person aus ${}B$ verbunden wird, wenn eine Brieffreundschaft zwischen ihnen besteht.

Beispiel

Es seien ${}A$ und ${}B$ disjunkte Mengen und sei ${}R$ eine Relation zwischen ${}A$ und ${}B$. Dann erhält man auf

${}V:=A\uplus B\,$

einen bipartiten Graphen, indem man ${}\{a,b\}$ als Kante erklärt, falls ${}(a,b)\in R$ gilt. Dadurch entsteht auf ${}V$ eine symmetrische Relation allein dadurch, dass ${}A$ und ${}B$ feste Rollen in der Relation ${}R$ haben. Dies muss man sich klar machen, um vor Missverständnissen geschützt zu sein. Wenn beispielsweise ${}A$ eine Menge von Männern und ${}B$ eine Menge von Frauen ist und ${}(a,b)\in R$ bedeutet, dass ${}a$ Person ${}b$ nett findet, so bedeutet die Kante ${}\{a,b\}$ genau dies, dass ${}a$ die Person ${}b$ nett findet, nicht, dass sie sich gegenseitig nett finden. Dies gilt auch, wenn man die Kante als ${}\{b,a\}$ schreibt.

Beispiel

Der Würfelgraph aus Beispiel ist bipartit, eine Einteilung erhält man, indem man ${}A$ als die Menge der ${}d$-Tupel ${}(\pm ,\ldots ,\pm )$ mit einer geraden Anzahl an ${}+$ und ${}B$ als die Menge der ${}d$-Tupel mit einer ungeraden Anzahl an ${}+$ ansetzt.

Definition

Der vollständige bipartite Graph ${}K_{m,n}$ ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer ${}m$-elementigen Menge ${}A$ und einer ${}n$-elementigen Menge ${}B$ besteht und dessen Kantenmenge durch

${}E={\left\{\{a,b\}\mid a\in A,\,b\in B\right\}}\,$

gegeben ist.

Satz

Ein Graph

ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.

Beweis

Es sei ${}V=A\uplus B$ eine bipartite Zerlegung eines bipartiten Graphen. In jedem Weg in einem bipartiten Graphen gehören die Knoten abwechselnd zu ${}A$ oder zu ${}B$. Die Existenz eines Kreises mit ungerader Anzahl führt daher direkt zu einem Widerspruch.

Es sei nun umgekehrt die Kreisbedingung erfüllt. Wir können annehmen, dass ${}G$ zusammenhängend ist. Es sei ${}v\in V$ ein fixierter Punkt. Wir definieren

${}A={\left\{x\in V\mid {\text{ es gibt einen geradzahligen Weg von }}v{\text{ nach }}x\right\}}\,$

und

${}B={\left\{x\in V\mid {\text{ es gibt einen ungeradzahligen Weg von }}v{\text{ nach }}x\right\}}\,.$

Wegen der Zusammenhangseigenschaft ist

${}V=A\cup B\,.$

Nehmen wir an, dass ${}A$ und ${}B$ nicht disjunkt sind, sagen wir ${}y\in A\cap B$. Es gibt dann Wege

${}v=v_{0}\sim v_{1}\sim \ldots \sim v_{r}=y\,$

und

${}v=v_{0}\sim u_{1}\sim \ldots \sim u_{s}=y\,$

mit ${}r$ gerade und ${}s$ ungerade. Indem man die beiden Wege zusammensetzt, erhält man einen Zyklus mit ungerade vielen Knoten. Wenn es in ihm Wiederholungen gibt, so kann man daraus zwei kleinere Zyklen herausarbeiten, von denen einer ebenfalls eine ungerade Anzahl besitzt. Somit erhält man auch einen ungeraden Kreis im Widerspruch zur Voraussetzung. Die beiden Mengen sind also disjunkt. Wenn es eine Kante innerhalb von ${}A$ geben würde, so würden die daran beteiligten Punkte sofort auch zu ${}B$ gehören im Widerspruch zur gezeigten Disjunktheit.

$\Box$

Insbesondere ist jeder Baum und jeder Wald bipartit.