cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

| MST | M inimal S panning T rees

anchored to [[111.00_anchor]] proceeds from [[111.13_Graphen_basics]] and [[111.23_Graphen_ZHK]]

Wir möchten das Prinzip eines MST durch ein Beispiel näher bringen. Betrachten wir ein Netz von Computern. Wir möchten jetzt ein Netzwerk bauen, bei welchem alle Computer verbunden sind, und dabei die Kosten gering bleiben. Also wir wollen einen Teilgraph des Gegebenen betrachten, sodass wir darin dann die minimalste Verbindung finden können

[!Example] Beispiel MST ( rot ) in einem Graphen ![[Pasted image 20221121141641.png]] Zu erkennen sind hier folgende Eigenschaften des Baumes:

erst ist azyklisch ( also wir haben keine Zykel in der Verbindung) [[111.18_Graphen_Traversieren]]

ist der günstigste Weg, der in diesem Graph möglich ist \

[!Important] ein MST ist immer ein [[111.08_algo_datastructures#Trees Grundlegende Definition|Tree]] warum ist das so? #card Wenn man die Knoten, die durch einen MST genommen werden, betrachtet, dann wird man hier immer einen BAUM erhalten. -> Dabei hat jeder Knoten $n$ viele Leafs, die dann wieder welche haben können Aber es kann hier keine Zykel geben, also wird dieser Baum nur in die Tiefe ausgebaut, aber nicht mehr nach oben verlinken. ( Es ist einfach eine Baum-Struktur D: ) ^1704708900392

| Historische Betrachtung von MST |

Für eine historische Betrachtung der Konzeptionen zur Findung von MST können wir folgend betrachten:

Kruskal’s algorithm -> published in 1956
Union-Find data structure (by Fisch, Galler) -> published in 1964
- there are still improvements and publication happening for this structure now!
Prim’s algorithm ->published 1957
- R. Prim - shortest connection networks and some generalizations.
- ((maybe already invented by V. Jarnik 1930))

| Definition | MST |

Wir wollen ferner noch definieren, was einen MST ausmacht.

[!Definition] Definition MST was ist ein MST von einem Graphen $G$ ? 3 Eigenschaften #card Sei $G = (V, E)$ ein ungerichteter Graph mit $n$ Knoten und $m$ Kanten. Wir benennen jetzt einen Teilgraph $T = (V^{'}, E^{'})$ mit $V’ \subset V, E’ \subsetE$ als aufspannenden Baum, wenn folgendes für $T$ gilt: 1. T ist azyklisch (acyclic)

2. $V^{'} = V$ , also der Teilgraph beinhaltet alle Knoten aus dem originalen Graph

3. $∣ E^{'} ∣= n - 1$ , also die Menge der Kanten ist minimal und damit eigentlich 1 kleiner, als die Menge der Knoten ^1704708900404

[!Important] Kosten beim MST wie sind die Kosten des Teilbaumes /Graphen $T$ definiert? #card Betrachten wir den entstehenden Teilgraphen $T$ , dann werden dessen Kosten $c (T)$ folgend definiert: $e \in E^{'} \sum c (e)$ Also die Kosten aller Kanten werden einfach summiert.

Wichtig ist, dass die Kosten hier minimal sein müssen! ^1704708900412

Betrachten wir dafür noch ein Beispiel, damit die Intuition innerhalb eines Graphen etabliert und verstanden werden kann.

| Nicht-Eindeutigkeit |

Sofern bei einem Graphen $G$ mehrere kürzeste Pfade zu bestimmten Knoten existieren, können diese mehreren Pfade auch angewandt werden, um etwa einen MST verschieden aufzuspannen.

[!Definition] MST sind nicht zwingend eindeutig warum? #card Sofern unser Graph mehrere kürzeste Pfade zu bestimmten Punkten hat, kann ein MST auch aus diesen einzelnen Pfaden aufgebaut werden.

Somit gibt es dann mehrere MST für einen Graphen $G$ –> Sie sind also nicht zwingend eindeutig in ihrer Definition ! ^1704708900421

| Beispiele für MST |

| Beispiel 1

[!Example] Graph und dessen MST ![[Pasted image 20231208200034.png]] Wie könnte in diesem Graph ein MST aussehen? #card ![[Pasted image 20231208200104.png]] -> Dieser Graph ist Zykelfrei! er hat die kürzesten Pfaden drin ^1704708900429

| Beispiel 2

Wir können noch ein Beispiel betrachten:

[!Example] ![[Pasted image 20221121151340.png]] ![[Pasted image 20221121151346.png]] ![[Pasted image 20221121151355.png]]

| MST | Bestimmen / Finden |

Wir möchten jetzt verschiedene Wege finden, um einen MST bestimmen und aufbauen zu können.

| Kruskal’s Algorithmus | Greedy | #refactor

Wir möchten dafür zuerst einen [[111.39_greedyAlgorithm|Greedy Algorithmus]] betrachten, welcher Schritt für Schritt die beste Option für einen MST sammeln wird.

[!Definition] Kruskal’s Algorithmus wie funktioniert dieser, was macht er? #card
\begin{algorithm} 
  \caption{Kruskal's Algorithmus} 	
	\begin{algorithmic} 
	\State $\text{sort edges in nondecreasing order by weight w} e_1,\dots,e_m \text{ so dass} c(e_1) \leq c(e_2) \leq \dots \leq c(e_m)$
	\State initialize  $E_{T} = \emptyset$ 
	\For{$i = 1, \dots,m$} 
	\Comment{traverse all edges from graph}
		\If{$E_{T} \cup \{ e_{i} \} acyclic$}
			\State $E_{T} = E_{T} \cup \{ e_{i} \}$ 
			\Comment{also immer die nächst kleinere Kante übernehmen, und schauen, dass es azyklisch bleibt}
		\EndIf
	\EndFor
	\end{algorithmic} 
\end{algorithm}
Intuition: Der Algorithmus sucht also von der geringsten zur höchsten Wichtung der Kanten, immer die heraus, sodass folgende Eigenschaften erhalten werden:

der Graph bleibt azyklisch ( wir schauen also, dass der entstehende Graph sich nicht looped)

der Graph bleibt minimal ^1704708900437

Intuition von Kruskal’s Algorithmus :

Wir fangen also mit einem leeren Baum an, den wir jetzt immer mit der günstigsten Kante füllen wollen
- wir fügen jetzt immer die günstigste Kanten zum Baum hinzu und schauen, dass kein Zykel entsteht
Wenn alle Knoten erreicht werden beenden wir den Algorithmus

[!Error] Kruskal ist ein dezentraler Algorithmus, also er sucht global eine Lösung und fügt sie anschließend zusammen

[!Important] Korrektheit von Kruskal’s Algorithmus | warum ist dieser Algo korrekt? #card Mit jeder Iteration, suchen wir von den geringsten Kanten ( deren Gewichten ) diese, die man in den neuen Graphen ( dem MST) aufnehmen kann, ohne dabei ein Zykel zu erzeugen. Das heißt also: Jede minimale Verbindung zwischen zwei Knoten wird betrachtet und anschließend übernommen. Wenn sie dann ein Zykel bildet, heißt das, dass wir in einer vorherigen Iteration ( wo die Gewichte kleiner waren!) schon eine Verbindung dahin gefunden haben, also schon die geringste Verbindung besteht!

Dadurch wird der Algorithmus mit jeder Iteration diese Eigenschaft des minimalsten Spannbaumes erhalten! ^1704708900447

Wir möchten bei dem Beweis der Korrektheit des Algorithmus einer bestimmten Intuition folgen:

–> Bedeutung “gut”: eine Menge $E^{'}$ nennen wir jetzt gut, wenn sie zu einem MST erweitert werden kann ( also minimal ist und azyklisch ist!)

| Nitpick | Finden von guten Kanten |

Wir können bestimmte Paradigmen betrachten, um solche guten Kanten in einem Graphen finden zu können. Mehr dazu findet sich hier [[111.29_Graphen_MST_find_safe_edges]]

| Beweis der Korrektheit |

[!Important] Ansatz des Korrektheitsbeweises Sei $E^{'}$ eine gute Teilmenge und sei hier $e$ die billigste Kante, so adss $E^{'} \cup e$ azyklisch ist (bleibt). Aus dieser Betrachtung folgt jetzt, dass $E^{'} \cup e$ weiterhin gut ist

Mit dieser Annahme können wir jetzt folgend die Korrektheit beweisen:

Sei jetzt $E^{''}$ die Erweiterung von $E^{'}$ zu einem MST.

Ist jetzt $e \in E^{''}$ , so ist $E^{'} \cup {e}$ auch gut -> also stimmt unsere Behauptung
Ist jetzt $e \neq \in E^{''}$ dann betrachten wir $H = (V, E^{'} \cup E^{''} \cup {e})$
- in dieser Betrachtung enthält dann H einen Zykel –> denn $E^{'}$ ist schon ein MST, brauch aber scheinbar $e$ nicht -> also wird er schon von einer anderen Kante abgedeckt
- Da auch $E^{'} \cup {e}$ azyklisch ist, gibt es in dem Zykel eine Kante $e^{'} \neq = e$ , die nicht in $E^{'}$ liegt Da wir $e$ entsprechend gewählt haben: $c (e) \leq c (e^{'})$ ( weil wir ja von geringer, nach höherer Wichtung sortiert haben!) -> Da $E^{'} \cup E^{''}$ ein MST ist, so erhalten wir auch einen MST, wenn $e^{'}$ durch $e$ ersetzt wird ( da die beiden Eigenschaften erhalten werden!)

Beispiel Anwendung | Kruskal |

Betrachten wir folgenden Graphen, dann möchten wir hier als Beispiel Kruskals-Algorithmus zum bestimmen eines MST anwenden:

[!Example] Betrachte folgenden Graphen: ![[Pasted image 20221121142820.png]] Unter Anwendung von Kruskal: wie könnte ein möglicher MST aussehen? #card Wir würden chronologisch die kleinsten Kanten nacheinander betrachten und dann einen MST bauen können: mögliche Konstruktion:

B–>C

C–>D

C–>F

F–>E

D–>A ^1704708900457

| Kruskal | Implementieren |

Vorbetrachtung: Wenn wir den Algorithmus tatsächlich implementieren wollen, müssen wir bestimmte Dinge beachten und prüfen:

Testen, ob eine neue potentielle Kante $e_{j}$ ein Zykel erzeugen würde, oder nicht
wir müssen die Kanten nach Gewicht ordnen

[!Definition] Ein möglicher Ansatz zum Verhindern von Zykeln Wir könnten uns Partitionen $V_{1}, \dots, V_{k}$ der Knoten $V$ erzeugen, sodass die Kanten aus $E_{T}$ (also dem zu erzeugenden Baum) immer auf die Knotenmenge $V_{j}$ induzieren. Durch diese Betrachtung: Hängen dann für $1 \leq i, j \leq k$ die Teilmengen $V_{i}, V_{j}$ nicht zusammen Wir können so also zum Anfang eine eine Partitionierung, folgend aufbauen: ${{1}, {2}, \dots, {n}}$ –> also für jeden Knoten ein eigenes Set ( eigene Partition aufmachen).

| Kruskal’s Algorithmus | UNION <> FIND |

Durch diesen Ansatz Zykel zu verhindern müssen wir jetzt folgend zwei Operationen definieren:

Find(x) –> liefert den Namen der Menge ( Partition) $V_{j}$ , wo der gesuchte Knoten $x$ drin ist –> damit wir wissen, ob er sich in einer Partition befindet, die wir schon haben / oder nicht
Union(A,B) –> Wir vereinigen zwei Mengen (Partitionen) $A$ und $B$ zu einer einzigen!
- damit werden dessen Inhalte also zusammengefasst ( und wir wissen, dass da kein Zykel ist!)

[!Important] Intuition dieser Implementierung wenn wir Find und Union einbringen und alles in Partitionen aufteilen, was ist es dann für ein Algorithmus? #card Wir haben hier mehr oder weniger Union-Find aufgebaut, wo wir quasi Schritt für Schritt kleine “Blasen” von Knoten nacheinander verbinden und zu einer großen Zusammenführen.

Dadurch haben wir am Ende eine Implementation, die folgend den MST aufgebaut hat! ^1704708900465

Ferner wollen wir die Erweiterung zu Union-Find betrachten wie funktioniert dieser ALgorithmus? #card

\begin{algorithm} 
	\caption{erweiterer Kruskal Algorithmus}
	\begin{algorithmic} 
	\State $\text{sort edges in nondecreasing order by weight w} e_1,\dots,e_m \text{ so dass} c(e_1) \leq c(e_2) \leq \dots \leq c(e_m)$
 		\State initialize  $E_{T} = \emptyset$ 
 		\Comment{der Anfang ist also gleich, wie vorher!}
 		\For{$i = 1,\dots, m$}
	 		\State sei $e_{1}= (v,w)$
	 		\Comment{also wir schauen, uns die Verbindenden Knoten der Kante e an!}
	 		\State $A = Find(v)$
	 		\State  $B = Find(w)$ 
	 		\If{($A \neq B$)}
		 		\State $E_{T}= E_{T} \cup \{ e_{i} \}$
		 		\State $Union(A,B)$
		 		\Comment{Wir haben zwei unverbundene Partitionen gefunden, also kein Zykel, wenn wir sie verbinden!}
	 		\EndIf
 		\EndFor
	\end{algorithmic}
	\end{algorithm}

Wir wollen hier noch betrachten, wie dann die Funktionen Find und Union aussehen müssen: Dafür müssen wir uns folgende Struktur für eine solche Partition überlegen: ^1704708900474

[!Definition] Forderung für die Abbildung $R$ wie sehen die Funktionen Find / Union für Union-Find aus? Was brauchen sie? #card $R : V \to {1, \dots, n}$ , so dass $R (x) \to Name der Menge, wo x drin ist$ Also sie muss bei einem gegebenen Knoten sagen können, wo dieser drin ist.

Daraus können wir jetzt Union und Find ableiten und definieren:
\begin{algorithm} 
\caption{Find(x)} 
  \begin{algorithmic} 
  	\Return $R(x)$ 
  	\Comment{find(x) gibt also einfach den Wert, der sich in R befindet }  
  	\end{algorithmic} 
\end{algorithm} 
und weiter noch $U ni o n (A, B)$
\begin{algorithm}
\caption{Union(A,B)}
\begin{algorithmic} 
\For{$i = to~ n$} 
\If{$R(i) = A$}
\State $R(i) = B$
\Comment{Wenn der Knoten i in A ist, dann setzen wir ihn auf B}
\EndIf 
\EndFor 
\end{algorithmic}
\end{algorithm} 

^1704708900483

| Laufzeit 2. Kruskal’s Algorithmus |

Wir möchten jetzt für die erweiterte Struktur die Laufzeit betrachten und evaluieren:

[!Tip] Laufzeit-Betrachtung mit Erweiterung durch Find / Union wie ist die Laufzeit beider Implementationen? #card Wir wissen:

dass $F in d (x) O (1)$ ist, da es nur einen Wert ausgeben muss, der sofort abrufbar ist

dass $U ni o n (A, B) O (n)$ -> da es jeden einzelnen Knoten durchgeht und zu B hinzufügt, wenn er in A ist ! Weiterhin schauen wir jetzt, wie oft wir diese beiden FUnktionen ausführen:

$2 \cdot m F in d (X)$ -> weil wir alle $m$ Kanten betrachten

$n - 1 U ni o n (A, B)$ -> weil wir nach und nach von N viele Partitionen in eine einzige Reduzieren werden!

Dadurch resultiert folgende Laufzeit: $O (m + n^{2} + m lo g m)$ ^1704708900493

Ein Problem was hier auftritt: Union ist zu langsam mit $O (n)$ ! -> Um das zu lösen könnte man beispielsweise die Namesänderung proportional zur Größe der kleineren Menge machen und somit den Namen der größeren beibehalten ( dadurch müssen wir nicht alles traversieren)

| Verbessern von $U N I ON (A, B)$ |

Aus der Betrachtung heraus, dass unser angepasster Kruskal-Algorithmus aufgrund der Union-Funktion relativ langsam werden kann, möchten wir eine bessere Implementation betrachten, den den obigen Vorschlag einbezieht, dass man die Namensänderung proportional zur Größe der kleineren Menge umsetzt.

[!Definition] Anpassung von $U ni o n (A, B)$ für eine schnellere Union/Find Implementation was müssen wir jetzt für die Partitionen weiter betrachten, um sie schneller zu bekommen? #card Für die neue Implementation brauchen wir folgende Grundstrukturen:

die Mengen ( Partitionen) sollen jetzt Listen sein. Ihre Größe muss gemerkt werden (damit wir sie später vergleichen können!)

die Größe soll mit $s i ze (A)$ abgerufen werden können!

die Abbildung $R$ soll weiterhin erhalten bleiben, also für $f in d (x)$ ! ^1704708900501

[!Important] Es müssen jetzt folgende Anpassungen für den PseudoCode von Kruskal eingebracht / umgesetzt werden: welche 2 sind es? #card

initialisieren der Größe jeder Partition am Anfang des Algorithmus!

die Union-Funktion muss angepasst werden, sodass sie nach der Größe entsprechend zusammenfässt

$f in d (x)$ bleibt gleicht ^1704708900514

| Aktualisierter PseudoCode | Was müssen wir mit unserer neuen Implementation ändern? Wie sieht jetzt $U ni o n (A, B)$ aus? #card

\begin{algorithm} 
	\caption{erweiterter Union / Find Algorithmus }
	\begin{algorithmic} 
		\Procedure{initializePartition}{}
			\For{$i = 1,\dots,n$}
				\State $R(i) = i$ 
				\State $Elem(i) = i$
				\State $size(i) = 1$
				\Comment{Wir initialisieren hier die Partitionen und setzen ihre Größe auf 1} 
			\EndFor 
		\EndProcedure
	
		\Procedure{find}{x}
			\Return $R(x)$
		\EndProcedure
		
		\Procedure{Union}{A,B}
			\If{$size(A) < size(B)$} 
				\State tausche A und B 
			\EndIf 
			\For{all $x \in Elem(B$}
				\State $R(x) = A$
				\State append(x,Elem(A)) 
				\Comment{we are now expanding A with all entries of B}
				\Comment{For that reason we are also swapping A and B, in case B is larger; we always append the smaller partition to the larger one} 
			\EndFor
		\EndProcedure
	\end{algorithmic} 
	
\end{algorithm}

^1704708900523

| Laufzeit von $U N I ON (A, B)$ |

Wir haben durch diese Anpassung jetzt eine neue Laufzeit für Union etablieren können.

[!Definition] Laufzeit vom neuen $U ni o n (A, B)$ warum ist es jetzt schneller, was ist besser? #card Da wir jetzt bei Union nicht mehr alles durchlaufen, sondern nur die Elemente der kleineren Menge, können wir entsprechend reduzieren, wie viele Knoten wir per Durchlauf anschauen müssen!

Es folgt eine neue Laufzeit: $O (min (∣ A ∣, ∣ B ∣))$ ^1704708900530

| Verbesserte Laufzeit von Kruskal’s Algorithmus mit neuem $U ni o n$ |

Da wir jetzt die Laufzeit reduzieren bzw von den Größen der Partitionen abhängig machen, können wir in der allgemeinem Implementation [[#Kruskal’s Algorithmus UNION <> FIND]] eine neue Laufzeit betrachten.

[!Tip] Laufzeit des Algorithmus ( $n - 1$ Unions werden ausgeführt) inwiefern ist jetzt die Laufzeit anders, wenn wir den neuen Union-Algo nutzen? #card Die insgesamt $n - 1$ Unions, die wir im Algorithmus ausführen, haben jetzt folgende Laufzeit: $O (i \sum n_{i})$ wobei hier $n_{i}$ die Größe der kleineren Partition ist, bei der $i$ -ten Iteration des Algorithmuses ( das kommt daher, dass wir ja immer nur die kleinere Menge in den großen einfügen müssen, und somit nur diese Einträge durchlaufen und aktualisiert werden müssen!)

Es gilt jetzt folgend: $O (i \sum n_{i}) = O (j \sum r_{j})$ wobei jetzt $r_{j}$ die Zahl der Mengenwechsel für $j$ angibt. ^1704708900539

Wir können daraus folgende Behauptung entnehmen / betrachten: Behauptung: $r_{j} \leq lo g n$ für $j = 1, \dots, n$ a ( also jedes Element wird $\leq lo g n$ ) mal seine Menge (Partition) wechseln wie können wir das beweisen? #card Beweis: Wenn $j$ die Partition wechselt, und vorher in einer Menge mit $k$ Einträgen ( Knoten) war, dann die neue Menge die Größe $\geq 2 k$ . Gleichzeit haben wir nach $I$ wechseln dann eine Größe von $\geq 2^{I} \leq n$ aufgebaut und daraus folgt jetzt: $⟹ I \leq lo g n$ –> Es folgt also daraus, dass wir immer größere Mengen erhalten und die kleinen Partitionen in die größeren fallen, dann der Fall, dass jeder Eintrag $\leq lo g n$ mal die Partition / Menge wechseln wird / kann! ^1704708900547

[!Definition] aktualisierte Laufzeit von Kruskal’s Algorithmus | Union Find Es resultiert eine Laufzeit $O (m + n lo g n + m lo g n) = O (E lo g V)$

( es ist hier die amortisiert Analyse von Union-Find)

| Prim’s Algorithmus | Dijkstra aber für MST |

Neben Kruskal können wir jetzt noch eine Implementation betrachten, welche in ihrem Prinzip [[111.22_Graphen_SSSP_dijkstra]] ähnelt.

-> [[111.27_Graphen_MST_Prims_Algorithm]]

scattered-lenity