Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 21

Dies ist nochmal Dr. Ines Eisenbeis. Ihre zweite These lautet: Es kommt nicht auf die Hunderasse, sondern stets auf den individuellen Hund an, ob er für den Einsatz als Vorlesungshund geeignet ist.

Vergleich von Paarungen

Wir erinnern kurz an die symmetrische Differenz von Mengen, die beispielsweise schon in Aufgabe 5.15 auftrat.

Zu zwei Teilmengen ${}A,B\subseteq M$ nennt man

${}A\triangle B=(A\setminus B)\cup (B\setminus A)\,$

die symmetrische Differenz von ${}A$ und ${}B$.

Diese Konstruktion wird im Folgenden auf Paarungen angewendet.

Lemma

Es sei ${}G=(V,E)$ ein Graph und seien ${}P$ und ${}Q$ Paarungen in ${}G$. Es sei ${}H$ derjenige Graph auf ${}V$, dessen Kantenmenge die symmetrische Differenz von ${}P$ und ${}Q$ ist.

Dann sind die Zusammenhangskomponenten von ${}H$ von einer der folgenden Gestalt.

1. Ein isolierter Punkt.
2. Ein linearer Graph, wobei die Kanten abwechselnd zu ${}P$ bzw. zu ${}Q$ gehören.
3. Ein Rundgang mit gerader Länge, wobei die Kanten abwechselnd zu ${}P$ bzw. zu ${}Q$ gehören.

Beweis

Ein jeder Knotenpunkt ${}v\in V$ liegt höchstens an einer Kante aus ${}P\setminus Q$ an, da ja sonst ${}\{v,u\},\{v,w\}\in P$ wäre, was der Paarungseigenschaft widerspricht. Gleiches gilt für ${}Q\setminus P$. Da die Kanten in ${}H$ durch ${}(P\setminus Q)\cup (Q\setminus P)$ gegeben sind, besitzt jeder Knotenpunkt in ${}H$ höchstens zwei anliegende Kanten, wobei bei zwei Kanten die eine aus ${}P$ und die andere aus ${}Q$ sein muss. Deshalb verbleiben die angegebenen Möglichkeiten.

$\Box$

Definition

Es sei ${}G=(V,E)$ ein Graph und ${}P\subseteq E$ eine Paarung. Man nennt einen Weg in ${}G$ alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus ${}P$ und aus ${}E\setminus P$ besitzt.

Häufig werden alternierende Wege in Zusammenhang mit zusätzlichen Eigenschaften verwendet, wie beispielsweise, dass sie mit einer Nichtpaarungskante oder in einem nicht abgedeckten Punkt beginnen oder enden. Solche Bedingungen werden wir aber stets explizit machen. Der folgende Satz heißt Satz von Berge.

Satz

Eine Paarung ${}P$ in einem Graphen ${}G$

ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

Beweis

Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte ${}u$ und ${}v$ verbindet, die beide nicht durch die Paarung abgedeckt sind. Wir müssen zeigen, dass man eine Paarung konstruieren kann, die mehr Kanten als die gegebene Paarung besitzt. Es sei

$\{u,u_{2}\},\{u_{2},u_{3}\},\ldots ,\{u_{n-1},v\}$

der alternierende Weg. Dabei gehören die beiden Endkanten nicht zu ${}P$, da die beiden Endpunkte nicht durch ${}P$ abgedeckt sind. Die Länge des Weges, also ${}n-1$, ist ungerade. Wir modifizieren nun die Paarung, indem wir die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ gerade herausnehmen und die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ ungerade hinzunehmen. Dabei wird die Gesamtzahl der Kanten um ${}1$ erhöht. Ferner handelt es sich nach wie vor um eine Paarung. Würde es nämlich in der neuen Paarung einen Knotenpunkt geben, der mit zwei Kanten inzident ist, so würde eine Kante davon gleich ${}\{u_{i},u_{i+1}\}$ sein (mit ${}i$ ungerade) und die andere Kante gleich ${}\{u_{i},x\}$ (oder gleich ${}\{u_{i+1},x\}$) Wenn diese zweite Kante nicht zum alternierenden Weg gehört, so gehört sie zu ${}P$ und würde zusammen mit ${}\{u_{i-1},u_{i}\}$ (bzw. $\{u_{i+1},u_{i+2}\}$) der Paarungseigenschaft von ${}P$ widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich ${}\{u_{j},u_{j+1}\}$ mit ${}j$ ungerade, und dann würden die an dem Durchschnittspunkt anliegenden Kanten aus ${}P$ der Paarungseigenschaft von ${}P$ widersprechen (bei den Endkanten muss man etwas anders argumentieren).

Nehmen wir nun an, dass ${}P$ nicht optimal ist. Es sei ${}Q$ eine optimale Paarung, die ja dann nach Definition mehr Kanten als ${}P$ besitzt. Es ist zu zeigen, dass es einen alternierenden Weg für ${}P$ gibt, dessen Endpunkte von ${}P$ nicht abgedeckt sind. Wir betrachten den Graphen ${}H$ auf ${}V$ mit der symmetrischen Differenz von ${}P$ und ${}Q$ als Kantenmenge. Da ${}Q$ mehr Kanten als ${}P$ besitzt, gibt es in ${}H$ mehr Kanten aus ${}Q\setminus P$ als aus ${}P\setminus Q$. Dies muss dann auch für eine Zusammenhangskomponente von ${}H$ gelten, und deren Möglichkeiten sind in Lemma 21.1 aufgelistet. Daher muss eine Komponente ein linearer Graph sein, mit Kanten abwechselnd aus ${}P$ und ${}Q$ und wobei die Endkanten aus ${}Q\setminus P$ sind. Die Endpunkte sind dann insbesondere verschieden und nicht durch ${}P$ abgedeckt.

$\Box$

Knotenüberdeckungen

Beispiel

In einem Landkreis sind Städte durch Straßen verbunden. Da es im Winter häufig schneit, sollen in gewissen Städten Räumdienste eingerichtet werden. Da man die Straßen schnell räumen möchte, sollen die Räumdienste nur für direkt an die Stadt anliegende Straßen zuständig sein. Man möchte dabei sicherstellen, dass jede Straße durch mindestens einen Räumdienst abgedeckt wird. Gleichzeitig möchte man möglichst wenige Räumdienste aufbauen. In welchen Städten sollen Räumdienste eingerichtet werden?

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Teilmenge ${}W\subseteq V$ heißt Knotenüberdeckung von ${}G$, wenn jede Kante mindestens einen Knoten aus ${}W$ trifft.

Es muss also jede Kante aus ${}G$ durch die Knoten aus ${}W$ abgedeckt sein. Es geht also um die Überdeckung von Kanten durch Knoten. Ein einzelner Knoten deckt genau die an ihm anliegenden Kanten ab. Wenn man die an einen Knoten ${}v$ anliegenden Kanten mit ${}E(v)$ bezeichnet, so lautet die Bedingung, dass ${}W$ eine Knotenüberdeckung ist, einfach

${}E=\bigcup _{v\in W}E(v)\,.$

In einem kantenleeren Graphen ist die leere Menge eine Knotenüberdeckung.

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt minimal, wenn ${}W\setminus \{w\}$ zu jedem ${}w\in W$ keine Knotenüberdeckung ist.

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt optimal, wenn es keine Knotenüberdeckung von ${}G$ mit weniger als ${}{\#\left(W\right)}$ Elementen gibt.

Definition

Es sei ${}G=(V,E)$ ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von ${}G$ heißt Knotenüberdeckungszahl von ${}G$.

Beispiel

Es sei ${}G$ ein linearer Graph mit ${}n$ Knotenpunkten. Dann muss in einer Knotenüberdeckung zumindest jeder zweite Knoten (in der natürlichen Reihenfolge auf einem linearen Graphen) vorkommen. Minimale Knotenüberdeckungen sind beispielsweise durch die Knotenfolgen ${}\{1,3,5,\ldots \}$ und ${}\{2,4,6,\ldots \}$ gegeben, wobei der letzte Knoten, ${}n-1$ oder ${}n$, davon abhängt, ob ${}n$ gerade oder ungerade ist. Bei ${}n$ gerade sind beide optimal, bei ${}n$ ungerade ist nur die zweite Knotenüberdeckung optimal. Die Knotenüberdeckungszahl beträgt in beiden Fällen ${}\left\lfloor {\frac {n}{2}}\right\rfloor$ Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise ${}\{1,3,4,6,7,9,10\}$ bei ${}n=11$.

Beispiel

Bei einem Sterngraphen (sagen wir mit zumindest drei Knotenpunkten) ist die Knotenüberdeckungszahl gleich ${}1$, man kann ja das Zentrum als einelementige Knotenüberdeckungsmenge nehmen. Dies ist die einzige optimale Knotenüberdeckung. Die Menge aller Blätter ist eine minimale Knotenüberdeckung, aber keine optimale Knotenüberdeckung.

Knotenüberdeckungszahl und Paarungszahl

Lemma

In einem Graphen

gelten zwischen der Knotenüberdeckungszahl ${}\kappa (G)$ und der Paarungszahl ${}\pi (G)$ die Abschätzungen

${}\pi (G)\leq \kappa (G)\leq 2\pi (G)\,.$

Beweis

Wenn eine Paarung mit ${}\pi (G)$ Kanten vorliegt, so sind diese disjunkt und eine Knotenüberdeckung muss jede der beteiligten Kanten treffen. Andererseits bilden die Endpunkte einer maximalen Paarung eine Knotenüberdeckung, da sie jede Kante treffen, denn andernfalls könnte man zu einer größeren Paarung gelangen.

$\Box$

Das Auswahlprinzip im Beweis des Satzes von König. Der einzige durch die Paarung (blau) unabgedeckte Punkt von ${}A$ (obere Reihe) ist der Punkt rechts oben. Er ist mit dem zweiten Punkt von rechts unten durch eine Kante, die nicht zur Paarung gehört, verbunden. Damit gehört schon mal aufgrund dieses einkantigen alternierenden Weges dieser Punkt zur Knotenüberdeckung und wird rot markiert. Diesen alternierenden Weg kann man fortsetzen, indem man längs der Paarungskante nach oben und dann wieder längs einer (der beiden) Nichtpaarungskanten nach unten wandert. Dies ergibt die beiden anderen unten rot markierten Punkte. Eine weitere alternierende Fortsetzung ergibt keine neuen Verbindungen. Aus den verbleibenden Paarungskanten sind die oberen Punkte rot zu markieren.

Der folgende Satz heißt Satz von König.

Satz

In einem bipartiten Graphen

stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.

Beweis

Die Abschätzung ${}\pi (G)\leq \kappa (G)$ gilt nach Lemma 21.11 in jedem Graphen. Es sei nun der Graph ${}G=(V,E)$ als bipartit mit einer Zerlegung ${}A\uplus B$ vorausgesetzt und sei ${}P$ eine optimale Paarung in ${}G$. Wir wählen aus jeder Kante ${}e=\{a,b\}\in P$ mit ${}a\in A$, ${}b\in B$ einen Endpunkt nach folgendem Prinzip aus: Wenn es einen in einem von der Paarung ${}P$ unabgedeckten Punkt aus ${}A$ beginnenden alternierenden Weg in ${}G$ gibt, der in ${}b$ endet, so wählen wir ${}b$, andernfalls ${}a$. Nennen wir die Menge der so ausgewählten Knotenpunkte ${}W$. Es ist zu zeigen, dass diese Auswahl ${}W$ eine Knotenüberdeckung ist. Es sei dazu ${}\{c,d\}$ eine beliebige Kante von ${}G$. Wenn diese zu ${}P$ gehört, so sind wir fertig. Wir können also davon ausgehen, dass ${}\{c,d\}$ nicht zu ${}P$ gehört (mit ${}c\in A$, ${}d\in B$). Da ${}P$ eine optimale Paarung ist, ist ein Endpunkt von ${}\{c,d\}$ mit einem Endpunkt einer Kante aus ${}P$ identisch. Entsprechend betrachten wir zwei Fälle.

Erster Fall. Wenn ${}c$ von der Paarung nicht abgedeckt ist, so ist ${}d$ von der Paarung abgedeckt und es gibt ein ${}a\in A$ und eine Kante ${}\{a,d\}\in P$. Da ${}\{c,d\}$ in dem nichtabgedeckten Punkt ${}c\in A$ startet, ist diese einzelne Kante ein alternierender Weg, der die geforderten Eigenschaften erfüllt, und daher wurde aus der Paarungskante ${}\{a,d\}$ der Punkt ${}d$ ausgewählt.

Zweiter Fall. Wenn ${}c$ von der Paarung abgedeckt ist, so gibt es ein ${}b\in B$ derart, dass ${}\{c,b\}$ eine Kante von ${}P$ ist. Wenn aus dieser Kante ${}c$ ausgewählt wird, sind wir fertig. Wenn aber ${}b$ ausgewählt wird, so bedeutet dies, dass es einen in einem unabgedeckten Punkt von ${}A$ beginnenden alternierenden Weg gibt, der in ${}b$ endet. Dieser Weg wird durch die beiden Kanten ${}\{c,b\}$ und ${}\{c,d\}$ alternierend mit Endpunkt ${}d$ fortgesetzt. Da eine optimale Paarung vorliegt, folgt nach Satz 21.3, dass ${}d$ durch die Paarung abgedeckt ist. Somit ist ${}d\in W$.

$\Box$

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)