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

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

Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte${\displaystyle {}u}$ und ${\displaystyle {}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

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

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

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

Wenn eine Paarung mit ${\displaystyle {}\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.

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

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

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