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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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 nennt man

die symmetrische Differenz von und .

Diese Konstruktion wird im Folgenden auf Paarungen angewendet.



Lemma  

Es sei ein Graph und seien und Paarungen in . Es sei derjenige Graph auf , dessen Kantenmenge die symmetrische Differenz von und ist.

Dann sind die Zusammenhangskomponenten von von einer der folgenden Gestalt.

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

Beweis  

Ein jeder Knotenpunkt liegt höchstens an einer Kante aus an, da ja sonst wäre, was der Paarungseigenschaft widerspricht. Gleiches gilt für . Da die Kanten in durch gegeben sind, besitzt jeder Knotenpunkt in höchstens zwei anliegende Kanten, wobei bei zwei Kanten die eine aus und die andere aus sein muss. Deshalb verbleiben die angegebenen Möglichkeiten.



Definition  

Es sei ein Graph und eine Paarung. Man nennt einen Weg in alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus und aus 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 in einem Graphen

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 und 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

der alternierende Weg. Dabei gehören die beiden Endkanten nicht zu , da die beiden Endpunkte nicht durch abgedeckt sind. Die Länge des Weges, also , ist ungerade. Wir modifizieren nun die Paarung, indem wir die Kanten für gerade herausnehmen und die Kanten für ungerade hinzunehmen. Dabei wird die Gesamtzahl der Kanten um 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 sein (mit ungerade) und die andere Kante gleich (oder gleich ) Wenn diese zweite Kante nicht zum alternierenden Weg gehört, so gehört sie zu und würde zusammen mit (bzw. ) der Paarungseigenschaft von widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich mit ungerade, und dann würden die an dem Durchschnittspunkt anliegenden Kanten aus der Paarungseigenschaft von widersprechen (bei den Endkanten muss man etwas anders argumentieren).

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




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?


Couverture de sommets.svg

Definition  

Es sei ein Graph. Eine Teilmenge heißt Knotenüberdeckung von , wenn jede Kante mindestens einen Knoten aus trifft.

Es muss also jede Kante aus durch die Knoten aus 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 anliegenden Kanten mit bezeichnet, so lautet die Bedingung, dass eine Knotenüberdeckung ist, einfach

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


Definition  

Es sei ein Graph. Eine Knotenüberdeckung von heißt minimal, wenn zu jedem keine Knotenüberdeckung ist.


Definition  

Es sei ein Graph. Eine Knotenüberdeckung von heißt optimal, wenn es keine Knotenüberdeckung von mit weniger als Elementen gibt.


Definition  

Es sei ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von heißt Knotenüberdeckungszahl von .


Beispiel  

Es sei ein linearer Graph mit 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 und gegeben, wobei der letzte Knoten, oder , davon abhängt, ob gerade oder ungerade ist. Bei gerade sind beide optimal, bei ungerade ist nur die zweite Knotenüberdeckung optimal. Die Knotenüberdeckungszahl beträgt in beiden Fällen Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise bei .



Beispiel  

Bei einem Sterngraphen (sagen wir mit zumindest drei Knotenpunkten) ist die Knotenüberdeckungszahl gleich , 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 und der Paarungszahl die Abschätzungen

Beweis  

Wenn eine Paarung mit 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.


Das Auswahlprinzip im Beweis des Satzes von König. Der einzige durch die Paarung (blau) unabgedeckte Punkt von (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 gilt nach Lemma 21.11 in jedem Graphen. Sei nun der Graph als bipartit mit einer Zerlegung vorausgesetzt und sei eine optimale Paarung in . Wir wählen aus jeder Kante mit , einen Endpunkt nach folgendem Prinzip aus: Wenn es einen in einem von der Paarung unabgedeckten Punkt aus beginnenden alternierenden Weg in gibt, der in endet, so wählen wir , andernfalls . Nennen wir die Menge der so ausgewählten Knotenpunkte . Es ist zu zeigen, dass diese Auswahl eine Knotenüberdeckung ist. Sei dazu eine beliebige Kante von . Wenn diese zu gehört, so sind wir fertig. Wir können also davon ausgehen, dass nicht zu gehört (mit , ). Da eine optimale Paarung ist, ist ein Endpunkt von mit einem Endpunkt einer Kante aus identisch. Entsprechend betrachten wir zwei Fälle.

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

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



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)