Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 21/kontrolle
- Vergleich von Paarungen
Wir erinnern kurz an die symmetrische Differenz von Mengen, die beispielsweise schon in Aufgabe 5.15 auftrat.
Diese Konstruktion wird im Folgenden auf Paarungen angewendet.
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.
- Ein isolierter Punkt.
- Ein linearer Graph, wobei die Kanten abwechselnd zu bzw. zu gehören.
- Ein Rundgang mit gerader Länge, wobei die Kanten abwechselnd zu bzw. zu gehören.
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.
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.
ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.
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
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?
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.
Es sei ein Graph. Eine Knotenüberdeckung von heißt minimal, wenn zu jedem keine Knotenüberdeckung ist.
Es sei ein Graph. Eine Knotenüberdeckung von heißt optimal, wenn es keine Knotenüberdeckung von mit weniger als Elementen gibt.
Es sei ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von heißt Knotenüberdeckungszahl von .
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 .
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
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.
Der folgende Satz heißt Satz von König.
In einem bipartiten Graphen
stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.
Die Abschätzung gilt nach Lemma 21.11 in jedem Graphen. Es 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. Es 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 .
