date-created: 2024-06-17 10:24:09 date-modified: 2024-06-24 11:15:30

Graphen - Matching

anchored to 115.00_graphentheorie_anchor

Wir möchten einen weiteren, wichtigen Themenabschnitt für Graphentheorie betrachten und definieren bzw. diverse Erkenntnisse dafür evaluieren und festlegen.

Mit Matching beschreiben wir konzeptuell das Aufteilen eines Graphen in verschiedene Kanten, wobei sich die Knoten, die mit den Knoten verbunden werden, nicht mit anderen, ausgesuchten Kanten überschneiden. Ferner wollen wir also eine gewisse “Coverage” des Graphen durch wenige Kanten abdecken bzw. definieren.

Definition | Matching (Paarung)

[!Definition] Matching

Wir wollen zuvor den simplen Begriff des matchings beschreiben und definieren:

Was wird bei einem Graphen G unter Matching verstanden? #card

Sei $M \subset E$ eine Menge von Kanten des Graphen $G = (V, E)$ . Wenn in dieser Submenge je zwei Kanten keine gleichen Endpunkte haben, sprechen wir bei $M$ von einem Matching (Paarung)

Konzeptuell wollen wir also mit einer kleinen Menge von Kanten alle Knoten des Graphen “erreichen / abdecken” (Wir sehen später auch, dass es gleich dem Vertex-Cover ist!)

Wir wollen jetzt noch weitere Erweiterungen / Zusatzdefinitionen zu dieser Struktur definieren:

Nicht erweiterbar | maximal

[!Definition] nicht erweiterbare Matchings | maximal

Wann sprechen wir bei einem Matching von einem nicht erweiterbaren Matching? #card

Falls für jede Kante $e \in / M$ gilt, dass $M \cup {e}$ keine Paarung mehr ist also sie sich etwa in einem Knoten treffen dann nennen wir $M$ nicht erweiterbar bzw maximal.

Größtmögliche Paarung

[!Req] größtmögliche Paarung

Wann sprechen wir von einer größtmöglichen Paarung über einen Graphen G? #card

Falls für alle Paarungen $M^{'}$ in G gilt, dass $∣ M^{'} ∣\leq∣ M ∣$ (Also diese Paarung ist garantiert größer, als alle anderen, die man bilden kann) Dann nennen wir $M$ ferner die größtmögliche Paarung –> also das Maximum

Perfect matching

[!Idea] perfect matching

wann beschreiben wir einen Graphen und dessen matching $M$ perfekt? #card

Falls jeder Knoten in $G$ durch $M$ gepaart ist (wir also jeden Knoten abdecken können), dann ist $M$ eine perfekte Paarung.

Naives Finden von Matching

Wir wollen ferner einen einfachen Algorithmus beschreiben, welcher uns hilft, ein großes Matching zu finden. –> Dabei werden wir aber nicht garantiert das Optimum bzw das größte Matching finden.

[!Feedback] Greedy-Algorithmus

wie läuft der greedy-algorithmus zum bestimmen eines Matchings für einen Graphen G ab? Ist M am Ende erweiterbar? #card
\begin{algorithm} 

\begin{algorithmic} 
\Procedure{Greedy}{G}
\State $M = \emptyset$
\State $S = \{   \}$
  \For{$(u,v) \in E$}
  	\If{$u \notin S \land v\notin S$}
  	\State \Comment{We know that both nodes were not added yet}
  	\State $M = M + (u,v)$ 
  	\State $S = S \cup \{  u,v \}$ 
  	\EndIf
  \EndFor
\state $return~M$
\EndProcedure
\end{algorithmic}
\end{algorithm}
Wir werden ferner herausfinden, dass $M$ noch erweiterbar sein kann, wir also nicht die optimalste Struktur finden werden / können.

Folgerung der Lösung

Wir werden in folgender Abgabe herausfinden und beweisen, dass für diesen Greedy-Algorithmus gilt, $∣ M ∣\geq 0.5 \cdot ∣ M^{*} ∣$ , wobei hier $M^{*}$ das größtmögliche Matching beschreibt!

115.86_uebung06

Alternierende Erweiterbare Pfade

Ferner möchten wir noch bestimmte Matchings betrachten, welch in ihrer Struktur teils “Oszillieren”, also abwechselnd auftreten. Ferner möchten wir dann bei Beobachtung dieser über die Erweiterbarkeit der Inhalte urteilen.

[!Intuition]

Betrachten wir folgendes nicht erweiterbares Matching:

Betrachten wir die mittleren vier Knoten mit der diagonalen, ausgewählten Kante, dann können wir hier ferner einen Pfad aufspannen, wo dann entlang des Pfades abwechselnd Kanten innerhalb und außerhalb des Matching sind:

Mit dieser Betrachtung können wir dann alternierende pfade beschreiben / definieren:

[!Definition] alternierende Pfade

Wann sprechen wir bei einem Pfade $P = (v_{1}, v_{2}, v_{3}, \dots)$ von einem alternierenden Pfad? #card

Wir beschreiben einen solchen Pfad als alternierend, wenn folglich entlang des Pfades abwechselnd gematchte und ungematchte Kanten auftreten.

Erweiterbare Pfade

[!Definition]

Wann nennen wir einen Pfad $P = v_{1}, v_{2}, v_{3}, \dots$ erweiterbar? #card

Wir nennen einen Pfad erweiterbar, wenn es sich um einen alternierenden Pfad handelt, welcher mit ungematchten Kanten startet und endet!

Warum? Weil man dann einfach die ungematchten Kanten als gematchte labled und ferner die gematchten Kanten aus $M$ herausnimmt –> also tauscht

Dadurch hat man die Eigenschaften von Matching weiter erhalten, und ein anderes Matching erhalten.

Wir wissen ferner, dass dieser neue Pfad, dann eine Kante mehr besitzt: Da: (mit $M Δ P$ meinen wir die symmetrische Differenz, also die disjunkten Kanten von M und P werden jeweils beibehalten, alles andere wird gelöscht) $M^{'} = M Δ P = (M \cup P) ∖ (M \cap P)$

Satz (38) | Satz von Berge

eine relativ wichtige Aussage im Themenbereich des Matchings!

[!Satz]

Matching $M$ ist möglich $⟺$

Was lässt sich hieraus folgern? #card

Wenn also das $M$ das größtmögliche Matching ist, dann ist das äquivalent dazu, $⟺$ dass es keinen erweiternden Pfad bezüglich $M$ gibt. (man ihn also nicht doch erweitern kann)

[!Beweis]

Unter Anwendung von Kontraposition können wir folglich beide Seiten der Aussage beweisen:

$⟹$

Wir wollen das durch eine Kontraposition beweisen:

Angenommen es gibt einen erweiternden Pfad $P$

Dann folgt ein neues Matching $M^{'} = M Δ P$ ist ei Matching mit $∣ M^{'} ∣ > ∣ M ∣$ , was dann aber heißt, dass $M$ nicht größtmöglich war. Somit resultieren wir mit einem Widerspruch.

$⟸$

Wir nehmen mit Kontraposition an, dass $M$ nicht größtmöglich ist. Das heïßt $\exists M^{'}$ mit $∣ M^{'} ∣> ∣ M ∣$ (also $M^{'}$ ist das größtmögliche Matching, was wir noch nicht gefunden haben!)

-> Wir bilden jetzt die symmetrische Differenz der beiden Graphen: $H = G [M Δ M^{'}]$

(Wir löschen alle Kanten, die in keinem Matching genutzt werden und auch die, die von beiden Matching genommen werden –> also wir behalten nur die disjunkt genutzten Kanten der beiden Matchings)

(betrachten also die Kanten, die in beiden Matchings auftreten, sich aber nicht überschneiden)

Es folgt:

Jeder Knoten in $H$ hat $de g () = 1 \lor 2$

Jede Komponente in $H$ ist dann entweder ein gerade Zykel oder Pfad ( Der Zykel folgt, weil wir oben wissen, dass jeder $d e g () = 1 \lor 2$ hat und somit garantiert ein Zykel auftritt. Ferner müssen die Matchings immer in gleiche Knoten übergehen; Pfade folgen mit dem gleichen Argument, aber wenn sie etwa nicht geschlossen sind)

Betrachten wir etwa folgendes Beispiel

Es folgt hierbei, dass jeder Knoten in $H$ Grad 1 oder Grad 2 hat! (Das kommt, weil jeder Knoten mindestens in einem der matchings auftreten muss, wenn es jetzt $> 2$ ) sind, dann haben wir kein Matching mehr!

Da $H$ dann mehr Kanten aus $M^{'}$ , als aus $M$ besitzt - weil er ja größer ist und somit anteilig mehr abdecken muss! - existiert dann ein Pfad $P^{'}$ mit einer Start- und Endkante aus $M^{'}$ !

Ferner gilt für diesen Pfad $P^{'}$ , dass er ein erweitender Pfad für $M$ ist!

Das wichtigste aus diesem beweis:

wir nutzen, dass Matching nicht größtmöglich ist ( also es muss ein größtmögliches existieren)

Aus der symmetrischen Differenz folgern wir, dass es entsprechend ungerade Zykel oder Pfade gibt

Wie findet man ein größtmögliches Matching

Aus dem Satz von Berge wissen wir, dass wir ein vorhandenes Matching Schritt für Schritt nach und nach aufbauen können, also wenn wir von einem kleinen Matching anfangen, können wir uns dann nach und nach ein besseres Matching zusammenbauen und so ein optimales finden - was besser als der Bruteforce sein wird / muss.

[!Definition] Algorithmus unter Anwendung Satz von Berge

Was ist die High-Level Idee des Algorithmus? #card
\begin{algorithm} 

\begin{algorithmic} 
\Procedure{FindeMitBerge}{G}
\State $M = \emptyset$
\While{$\exists \text{ aufgmentierender Pfad } P  \in M$}
\State $M = M \Delta P$

\EndWhile \EndProcedure

\end{algorithmic}

\end{algorithm}

Wir müssen diesen Ansatz in zwei Fälle unterscheiden:

$G = (V, E)$ ist bipartite

Falls $G$ bipartite ist, können wir das Matching durch ein Flussnetzwerk aufbauen und erörtern. link für weitere Infos

Idee

Man hat hierbei zwei weitere Punkte - Start und Senke - und baut quasi einen gerichteten Pfad vom Quell-Ursprung zur Ziel-senke über den Graphen

Dieser Algorithmus wird mit Ford-Fulkerson beschrieben:

Wenn man dann zwischen zwei Knoten (aus jeweils einer Partition) entsprechend Pfade finden möchte, dann kann man einen Pfad zwischen diesen beiden Punkte setzen –> dadurch finden wir augmentierende Pfade im bipartiten Graph.

Genereller Fall $G = (V, E)$

Im Generellen Fall - also, wenn er nicht zwingend bipartite ist - müssen wir einen passenden Pfad finden, der durch den Graphen traversiert–> dabei darf man aber nicht in ungerade Zykel fallen, was schwer zu entscheiden ist (also solche, die einfach nicht die optimale Lösung sind, was man visuell vielleicht erkennt, aber nicht ohne Vorbetrachtung)

Abhilfe schafft hierbei etwa, Blossom Shrink, was eine Idee ist, bei welcher man bestimmte Kanten kontrahiert, dann einen Pfad baut und anschließend “wieder entfaltet” –> dadurch lässt sich entspechen ein Pfad konstruieren. (Ist aber out-of-scope für diese Vorlesung)

Weitere Betrachtung der Themen findet man etwa in

Methodik der Algorithmen für Flussnetzwerke

Algorithmen und Komplexität für Blossom Shrinking

Additional Information

Matching, bzw das Maximieren davon in generellen Graphen ist “aufwendiger”, als bei bipartiten, weswegen wir es nicht genau betrachten. Dennoch ist es eine Möglichkeit und man kann es umsetzen, nur halt komplexer!

[!Tip] Es gibt aber mittlerweile einen Algorithmus, der die Laufzeit für beide Fälle auf $O (∣ V ∣ \cdot ∣ E ∣)$

Satz (39) | Satz von Hall | (bipartite Graphen)

(ehemals noch zu finden als ~~heiratssatz~~ ( sofern Literatur diese Bezeichnung noch verwendet) )

[!Definitin] Satz (39)

Sei $G = (A, B, E)$ ein bipartiter Graph mit zwei Partitionen $A, B$ .

Angenommen wir haben in diesem Graphen ein $A$ -Perfektes Matching $M$

was beschreiben wir mit A-perfektem Matching? Was können wir dann über dieses Matching aussagen? #card

Wir nennen ein Matching $M$ $A$ -perfekt (analog $B$ -perfekt), falls es alle Knoten in $A$ ( $B$ ) matched (also alles abdeckt bzw in diesem Kontext ein perfektes Matching ist!)

Sofern also ein solches $A -$ perfektes Matching existiert, $⟺$ ist es gleich damit, dass $∣ N (S) ∣ \geq ∣ S ∣ .\forall S \subseteq A$

Also für jede beliebige Menge aus $A$ können wir dann aussagen, dass die Menge von Nachbarn dieser Menge größer ist, als die Knoten in dieser Menge! (und das gilt für alle!)

(ferner können wir hier also eine Aussage über die Menge von Nachbarn in einer Teilmenge bei einem perfekten Matching treffen!)

Das möchten wir jetzt noch ausführlich beweisen:

Beweis Satz (39) Heiratssatz (bipartite Graphen)

Wir wollen zuerst $⟹$ beweisen: Sei also $S \subseteq A$ eine beliebige Menge aus $A$ !

Da $M$ perfekt ist, ist hier jeder Knoten aus $A$ - also auch die gesamte Teilmenge $S$ zu einem Knoten aus $B$ gematcht!

Es muss dann gelten: $∣ N (S) ∣ > ∣ S ∣$ , denn sonst würde wir einen Knoten aus $B$ doppelt matchen - was dann nicht mehr Matching ist.

Beweis: $⟸$

Wir wissen, dass ein Knoten mindestens einen Nachbar hat. Ist das der Fall, dann matchen wir mit diesem und haben es abgeschlossen.(bauen dann anschließend nach und nach auf und zeigen, dass die Eigenschaft erhalten wird / gilt).

Wir wollen dann also über Induktion über die Menge von Knoten $n = ∣ A ∣$ argumentieren:

IA: $n = 1$ ist trivial, weil weil dieser offensichtlich noch Nachbarn haben muss!

Im Induktionsschritt: Die Teilmenge $A^{'} \subset A$ heißt kritisch, falls $∣ A^{'} ∣= ∣ N (A^{'}) ∣$ ist.

Betrachten wir jetzt zwei Fälle:

Fall-1: Es gibt keine kritische Teilmenge Sei dann $(a_{,}, b^{'}) \in E$ Dann haben wir selbst ohne diese Kante noch genug Nachbarn und verlieren das Matching nicht.

Betrachten wir dann $G^{'} = G (a_{n}, b^{'})$

Wir betrachten jetzt $S = A - (a_{n})$ (also ohne den Knoten) –> Da keine kritische Menge in $G$ existiert, gilt ferner $∣ N (S) ∣ \geq ∣ S ∣$ in $G^{'}$ .

Nach der IA existiert ein perfektes matching für Knoten in $G^{'}$ .

–> Wir erweitern dann das matching mit der folgenden Kante $(a_{nn}, b^{'})$ für G und damit haben wir es entsprechend erweitert.

Fall-2: Es gibt eine kritische Teilmenge

Haben wir jetzt eine kritische Teilmenge $A^{'} = {a_{1}, \dots a_{l}}$ . Es gilt ferner $l < n$ (also es sind weniger Elemente in dieser kritischen Teilmenge).

Dann sie jetzt $G_{s} = [A^{'} \cup N (A^{'})]$ und nach der IA existiert ein perfektes Matching für $G_{s}$

Sei dann aber noch $G_{r} = G ∖ {A^{'} \cup N (A^{'})}, A_{r}, B_{r} sind disjunkte Knotenmengen \in G + r$ Wir betrachten jetzt also die “übrigen Knoten in diesem Graphen”.

Wir behaupten jetzt, dass $∣ N (S) ∣ \geq ∣ S ∣, \forall S \in A_{r}$ gilt (und wenn das so wäre, dann existiert ein perfektes Matching für $G_{r}$ gemäß IA.)

–> Damit würde dann die Kombination wieder ein perfektes Matching erzeugen für den Ausgangsgraphen $G$ .

Wir wollen das auch hier wieder durch einen Widerspruchsbeweis belegen:

Angenommen es existiert $S \in A_{r}$ , sodass dann $∣ S ∣ > ∣ N (S) ∣$
Dann würde aber für Menge $S^{'} = S \cup A^{'}$ in $G$ gelten, dass $∣ S^{'} ∣> ∣ N (S^{'}) ∣$ Was aber in einem Widerspruch steht!

Wir betrachten bei diesem Widersprucht die Originalmenge bzw den originalen Graphen!

Vertex-Cover | Knotenüberdeckung

[!Definition]

Sei $G = (V, E)$ , Eine Menge $S \subseteq V$ heißt Knotenüberdeckung ( VertexCover , falls jede Kante aus $E$ mindestens einen Endpunkt in $S$ besitzt.

(Wir wollen hier halt die minimale Menge von Knoten finden!)

für weitere Erklärung, siehe 111.99_algo_approximationAlgorithms

Satz (40) | Satz von König | bipartite Graphen

Wir wollen jetzt eine Bindung zwischen des Vertex-Covers und des größtmöglichen Matchings betrachten und definieren / zeigen, dass wir hier eine Korrelation zwischen dieser Werte finden können!

[!Definition] Satz von König (1931)

Sei $G = (V = A \cup B, E)$ ein bipartiter Graph mit größtmöglichen Matching $M$ udn kleinstmöglicher Knotenüberdeckung $S$ .

Was gilt dann hier bezüglich der Größe der Menge $M$ und $S$ ? #card

Dann gilt jetzt $∣ M ∣ = ∣ S ∣$

Beweis:

[!Beweis]

Wir beweisen dass das folgend:

Wir definieren eine Knotenmenge $U$ folgend: Sei $e = (a, b)$ Kante aus $M$ .

Wir wissen, dass $U$ vom Matching $M$ abhängig ist - sonst nichts - und baut sich so auf!

Idee: Wir behaupten als nächstes, dass U eine Knotenüberdeckung ist, vorher müssen wir aber noch sagen, dass unsere Menge $U$ das minimale Matching bildet.

Für die obige Kante folgt jetzt:

Ist $b$ erreichbar durch einen alternierenden Pfad, welcher an einem ungematchten Knoten $\in A$ startet, dann ist $b \in U$ , sonst $a \in U$ (also wir zeigen von einer Seite garantiert auf die andere!)

Behauptung: $U$ ist eine Knotenüberdeckung von $G$ (ein Vertex-Cover)

Da jede Überdeckung die Kanten aus $M$ abdecken muss - und ferner keine zwei Kanten aus $M$ einen gemeinsamen Knoten teilen - so muss eine minimale Knotenüberdeckung mindestens $∣ M ∣$ Knoten aufweisen!

Dann können wir jede weitere Kante betrachten:

entweder ist sie im Matching drin! $e \in M$

sie ist nicht drin –> dann ist $(a, b) \in / M$ und somit liegen die beiden Knoten schon in anderen Matching-Kanten und müssen somit nicht mehr abgedeckt werden! –> $M$ ist ja schon größtmöglich und enthält eine Kante $(a^{'}, b^{'}), a^{'} = a \lor b^{'} = b$ –> wir wissen also, dass sie schon enthalten sein muss, bzw ein Äquivalent.

Wir können nun annehme, dass $a^{'} = a$ gilt: (Sonst wäre $a$ unmatched und da $b^{'} = b$ gilt, wäre dann $(a, b)$ ein alternierender Pfad) –> und damit wäre der Endpunkt dieser Kante $(a^{'}, b^{'}) \in M$ , welcher auch in $U$ ist, dann auf jeden Fall $b^{'} = b$

–> Also wir können sagen, dass beim finden eines alternierenden Pfades die andere Kante, die eben noch nicht gematched wurde, von den restlichen Kanten abgedeckt wird und somit nicht nochmal eingefügt werden muss.

Falls dann $a^{'} = a \in / U$ , gilt somit $b^{'} \in U$ und es existiert ein alternierender Pfad $P$ der in $b^{'}$ endet!

–> Dadurch existiert dann auch ein alternierender Pfad $P^{'} = P \cdot b$ - falls $b$ in P - ansonsten folgt $P^{'} = P b^{'} a^{'} b$ (Also wir können sagen, dass durch das “Anknüpfen” eines neuen Pfades and eine existierende Struktur, Punkte, wie $b^{'}$ weiterhin erreichbar sind )

Da $M$ größtmöglich ist, ist $P^{'}$ nicht erweiterbar also muss $b$ gematched sein / werden. und es gilt dann $b \in U$ gemäß unserer Konstruktion

(Spezialfall) $P^{'} = P \cdot b$ - falls $b \in P$ . Wir finden dadurch auch einen erweiternden pfade!

Da unser $M$ größtmöglich ist, darf hier $P^{'}$ kein erweiternder Pfad sein ( nur alternierend) –> denn sonst würde wir keinen größtmögliches Matching haben! Das heißt dann, dass $b$ schon gematched sein muss, und es gilt auch $b \in U$ nach Konstruktion

Wenn die letzte kante keine Matching kante ist ( die erste kante ist auch keine Matching-Kante und da wir hier bipartite sind oszilliert es immer zwischne matched / nicht matched) –> dadurch folgt dann, dass auch die letzte nicht im matching ist ( kann man visualisieren, wenn man Schritt für Schritt durch die einzelen Kanten geht / traversiert )

scattered-lenity

date-created: 2024-06-17 10:24:09 date-modified: 2024-06-24 11:15:30