Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 21/latex
\setcounter{section}{21}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Crystal Clear kdm user female.svg} }
\end{center}
\bildtext {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.} }
\bildlizenz { Crystal Clear kdm user female.svg } {} {Ftiercel} {Commons} {GNU-Lizenz für freie Dokumentatio} {}
\zwischenueberschrift{Vergleich von Paarungen}
Wir erinnern kurz an die symmetrische Differenz von Mengen, die beispielsweise schon in Aufgabe 5.15 auftrat.
Zu zwei
\definitionsverweis {Teilmengen}{}{}
\mavergleichskette
{\vergleichskette
{A,B
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man
\mavergleichskettedisp
{\vergleichskette
{ A \triangle B
}
{ =} { (A \setminus B) \cup (B \setminus A)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {symmetrische Differenz}{} von
\mathkor {} {A} {und} {B} {.}
Diese Konstruktion wird im Folgenden auf Paarungen angewendet.
\inputfaktbeweis
{Graph/Paarungen/Symmetrische Differenz/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph
}{}{}
und seien
\mathkor {} {P} {und} {Q} {}
\definitionsverweis {Paarungen}{}{}
in $G$. Es sei $H$ derjenige Graph auf $V$, dessen Kantenmenge die
\definitionsverweis {symmetrische Differenz}{}{}
von
\mathkor {} {P} {und} {Q} {}
ist.}
\faktfolgerung {Dann sind die
\definitionsverweis {Zusammenhangskomponenten}{}{}
von $H$ von einer der folgenden Gestalt.
\aufzaehlungdrei{Ein isolierter Punkt.
}{Ein
\definitionsverweis {linearer Graph}{}{,}
wobei die Kanten abwechselnd zu
\mathkor {} {P} {bzw. zu} {Q} {}
gehören.
}{Ein
\definitionsverweis {Rundgang}{}{}
mit gerader
\definitionsverweis {Länge}{}{,}
wobei die Kanten abwechselnd zu
\mathkor {} {P} {bzw. zu} {Q} {}
gehören.
}}
\faktzusatz {}
\faktzusatz {}
}
{
Ein jeder Knotenpunkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt höchstens an einer Kante aus
\mathl{P \setminus Q}{} an, da ja sonst
\mavergleichskette
{\vergleichskette
{ \{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
\mathl{(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.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Paarung}{}{.}
Man nennt einen
\definitionsverweis {Weg}{}{}
in $G$
\definitionswort {alternierend}{}
\zusatzklammer {bezüglich der gegebenen Paarung} {} {,}
wenn er abwechselnd Kanten aus $P$ und aus
\mathl{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 \stichwort {Satz von Berge} {.}
\inputfaktbeweis
{Ungerichteter Graph/Optimale Paarung/Alternierender Weg/Fakt}
{Satz}
{}
{
\faktsituation {Eine
\definitionsverweis {Paarung}{}{}
$P$ in einem
\definitionsverweis {Graphen}{}{}
$G$}
\faktfolgerung {ist genau dann
\definitionsverweis {optimal}{}{,}
wenn es keinen
\definitionsverweis {alternierenden Weg}{}{}
gibt, dessen Endpunkte verschieden und
\definitionsverweis {unabgedeckt}{}{}
sind.}
\faktzusatz {}
\faktzusatz {}
}
{
Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte
\mathkor {} {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
\mathdisp {\{ 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
\mathl{\{u_i,u_{i+1} \}}{} für $i$ gerade herausnehmen und die Kanten
\mathl{\{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
\mathl{\{ u_i, u_{i+1} \}}{} sein
\zusatzklammer {mit $i$ ungerade} {} {}
und die andere Kante gleich
\mathl{\{ u_i,x \}}{}
\zusatzklammer {oder gleich
\mathl{\{ 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
\mathl{\{ u_{i-1}, u_{i} \}}{}
\zusatzklammer {bzw. \mathlk{\{ u_{i+1}, u_{i+2} \}}{}} {} {}
der Paarungseigenschaft von $P$ widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich
\mathl{\{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
\zusatzklammer {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 \definitionsverweis {symmetrischen Differenz}{}{} von \mathkor {} {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 \definitionsverweis {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 \mathkor {} {P} {und} {Q} {} und wobei die Endkanten aus $Q \setminus P$ sind. Die Endpunkte sind dann insbesondere verschieden und nicht durch $P$ abgedeckt.
\zwischenueberschrift{Knotenüberdeckungen}
\inputbeispiel{}
{
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?
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Couverture_de_sommets.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Couverture_de_sommets.svg } {} {Fschwarzentruber} {Commons} {CC-by-sa 4.0} {}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Eine Teilmenge
\mavergleichskette
{\vergleichskette
{ W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {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
\mavergleichskettedisp
{\vergleichskette
{E
}
{ =} { \bigcup_{v \in W} E(v)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
In einem kantenleeren Graphen ist die leere Menge eine Knotenüberdeckung.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Eine
\definitionsverweis {Knotenüberdeckung}{}{}
\mavergleichskette
{\vergleichskette
{ W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
von $G$ heißt
\definitionswort {minimal}{,}
wenn
\mathl{W \setminus \{w\}}{} zu jedem
\mavergleichskette
{\vergleichskette
{w
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
keine Knotenüberdeckung ist.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Eine
\definitionsverweis {Knotenüberdeckung}{}{}
\mavergleichskette
{\vergleichskette
{ W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
von $G$ heißt
\definitionswort {optimal}{,}
wenn es keine Knotenüberdeckung von $G$ mit weniger als ${ \# \left( W \right) }$ Elementen gibt.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Die minimale Anzahl von Knoten in einer
\definitionsverweis {Knotenüberdeckung}{}{}
von $G$ heißt
\definitionswort {Knotenüberdeckungszahl}{}
von $G$.
}
\inputbeispiel{}
{
Es sei $G$ ein
\definitionsverweis {linearer Graph}{}{}
mit $n$ Knotenpunkten. Dann muss in einer
\definitionsverweis {Knotenüberdeckung}{}{}
zumindest jeder zweite Knoten
\zusatzklammer {in der natürlichen Reihenfolge auf einem linearen Graphen} {} {}
vorkommen.
\definitionsverweis {Minimale Knotenüberdeckungen}{}{}
sind beispielsweise durch die Knotenfolgen
\mathl{\{1,3,5, \ldots \}}{} und
\mathl{\{2,4 ,6 , \ldots \}}{} gegeben, wobei der letzte Knoten,
\mathkor {} {n-1} {oder} {n} {,}
davon abhängt, ob $n$ gerade oder ungerade ist. Bei $n$ gerade sind beide
\definitionsverweis {optimal}{}{,}
bei $n$ ungerade ist nur die zweite Knotenüberdeckung optimal. Die
\definitionsverweis {Knotenüberdeckungszahl}{}{}
beträgt in beiden Fällen
\mathl{\left \lfloor { \frac{ n }{ 2 } } \right \rfloor}{} Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise
\mathl{\{1,3,4,6,7, 9,10\}}{} bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{11
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputbeispiel{}
{
Bei einem \definitionsverweis {Sterngraphen}{}{} \zusatzklammer {sagen wir mit zumindest drei Knotenpunkten} {} {} ist die \definitionsverweis {Knotenüberdeckungszahl}{}{} gleich $1$, man kann ja das Zentrum als einelementige Knotenüberdeckungsmenge nehmen. Dies ist die einzige \definitionsverweis {optimale Knotenüberdeckung}{}{.} Die Menge aller \definitionsverweis {Blätter}{}{} ist eine \definitionsverweis {minimale Knotenüberdeckung}{}{,} aber keine optimale Knotenüberdeckung.
}
\zwischenueberschrift{Knotenüberdeckungszahl und Paarungszahl}
\inputfaktbeweis
{Graph/Paarungszahl/Knotenüberdeckungszahl/Vergleich/Fakt}
{Lemma}
{}
{
\faktsituation {In einem
\definitionsverweis {Graphen}{}{}}
\faktfolgerung {gelten zwischen der
\definitionsverweis {Knotenüberdeckungszahl}{}{}
$\kappa (G)$ und der
\definitionsverweis {Paarungszahl}{}{}
$\pi(G)$ die Abschätzungen
\mavergleichskettedisp
{\vergleichskette
{ \pi (G)
}
{ \leq} { \kappa (G)
}
{ \leq} { 2 \pi (G)
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
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.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Koenigs-theorem-graph.svg} }
\end{center}
\bildtext {Das Auswahlprinzip im Beweis des Satzes von König. Der einzige durch die Paarung
\zusatzklammer {blau} {} {}
unabgedeckte Punkt von $A$
\zusatzklammer {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
\zusatzklammer {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.} }
\bildlizenz { Koenigs-theorem-graph.svg } {} {David Eppstein} {Commons} {gemeinfrei} {}
Der folgende Satz heißt \stichwort {Satz von König} {.}
\inputfaktbeweis
{Bipartiter Graph/Paarungszahl/Knotenüberdeckungszahl/Fakt}
{Satz}
{}
{
\faktsituation {In einem
\definitionsverweis {bipartiten Graphen}{}{}}
\faktfolgerung {stimmt die
\definitionsverweis {Paarungszahl}{}{}
mit der
\definitionsverweis {Knotenüberdeckungszahl}{}{}
überein.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Abschätzung
\mavergleichskette
{\vergleichskette
{ \pi(G)
}
{ \leq }{ \kappa(G)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt nach
Lemma 21.11
in jedem Graphen. Es sei nun der Graph
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als bipartit mit einer Zerlegung
\mavergleichskette
{\vergleichskette
{}
{ A\uplus B }{}
{ }{}
{ }{}
{ }{}
}
{}{}{}
vorausgesetzt und sei $P$ eine
\definitionsverweis {optimale Paarung}{}{}
in $G$. Wir wählen aus jeder Kante
\mavergleichskette
{\vergleichskette
{e
}
{ = }{ \{ a,b \}
}
{ \in }{P
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{b
}
{ \in }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Endpunkt nach folgendem Prinzip aus: Wenn es einen in einem von der Paarung $P$
\definitionsverweis {unabgedeckten Punkt}{}{}
aus $A$ beginnenden
\definitionsverweis {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
\mathl{\{c,d\}}{} eine beliebige Kante von $G$. Wenn diese zu $P$ gehört, so sind wir fertig. Wir können also davon ausgehen, dass
\mathl{\{c,d\}}{} nicht zu $P$ gehört
\zusatzklammer {mit
\mavergleichskettek
{\vergleichskettek
{c
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskettek
{\vergleichskettek
{d
}
{ \in }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}
Da $P$ eine optimale Paarung ist, ist ein Endpunkt von
\mathl{\{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
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und eine Kante
\mavergleichskette
{\vergleichskette
{ \{a,d\}
}
{ \in }{ P
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da
\mathl{\{c,d\}}{} in dem nichtabgedeckten Punkt
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{A
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
startet, ist diese einzelne Kante ein alternierender Weg, der die geforderten Eigenschaften erfüllt, und daher wurde aus der Paarungskante
\mathl{\{a,d\}}{} der Punkt $d$ ausgewählt.
Zweiter Fall. Wenn $c$ von der Paarung abgedeckt ist, so gibt es ein
\mavergleichskette
{\vergleichskette
{b
}
{ \in }{B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart, dass
\mathl{\{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
\mathkor {} {\{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
\mavergleichskette
{\vergleichskette
{d
}
{ \in }{W
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}