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

| Starke Zusammenhangskomponenten |

anchored to [[111.00_anchor]] requires [[111.20_Graphen_DFS]]

| Overview |

| SZK | Starke Zusammenhangskomponenten |

Betrachten wir einen Gerichteten Graphen $G=(V,E)$.

[!Definition] Stark zusammenhängend what does it require? #card Wir nennen ihn jetzt stark zusammehängend wenn folgt, dass $$\forall v,w\in V:v⟶w\text{ bzw.}Pfad(v,w)\wedge Pfad(w,v)$$ Also wir können entsprechend zwischen beiden Knoten in dem gegebenen Graphen traversieren. Wir müssen hier also eine direkte Verknüpfung zwischen beiden haben “und hin und her laufen können” ^1704708885738

Anders beschrieben meinen wir damit also einen maximalen, stark zusammenhängenden Teilgraph von G. Also es ist mehr oder weniger eine Submenge unseres großen Graphen, wobei hier wichtig ist, dass innerhalb dessen Alle Knoten auftreten können / und verbunden sind.

[!Example] Betrachtung eines Beispielgraphen und seine Reduktion: ![[Pasted image 20231125194023.png]] Wie können wir diesen jetzt passend reduzieren? und warum geht das? #card ![[Pasted image 20231125194046.png]] Es ist möglich, weil die Knoten $b,d,e,f$ so zusammenhängen, dass sie ein Zykel bilden! ^1704708885744

| Konzepte von | SZK |

Wir können und möchten jetzt weitere wichtige Aspekte von SZK betrachten, die uns diverser Aussagen über diese Treffen lassen.

[!Definition] $v$ als Wurzel eines SZK. wann nenn wir einen Knoten $v$ Wurzel? Was muss gelten? #card Betrachten wir einen SZK von $G$, beschrieben mit $(V^{\prime },E^{\prime })$. Wir nennen darin jetzt einen Knoten $v\in V^{\prime }$ eine Wurzel, wenn gilt: Dieser Knoten $v$ hat die kleinste dfsnum [[111.18_Graphen_Traversieren|siehe exploreFrom]] der Knoten in $V^{\prime }$ Also das heißt, dass bei der Evaluierung bzw beim Durchlaufen des Graphen mit ExploreFrom* die dfsnum, also der Wert, der angibt, wann ein Knoten beim Durchlaufen angefangen wurde, sehr klein war! Wir suchen also den Punkt, wo der Teilgraph mehr oder weniger angefangen hat. ^1704708885750

Wir können aus dieser Grundeigenschaft jetzt bestimmen, dass man alle anderen Knoten innerhalb des Teilgraphen bzw der SZK erreichen kann!

[!Important] $\exists \text{ Wurzel }r⟹$ ? #card Sei wieder $(V^{\prime },E^{\prime })$ ein SZK mit einer bestimmten Wurzel $r$, also einem Knoten der mehr oder weniger den Anfang des Graphen bildet. Es gilt jetzt

Alle Knoten im SZK können von $r$ aus erreicht werden! ^1704708885757

| Aktuell bekannte SZKs finden / betrachten |

Sei jetzt $G_a=(V_a,E_a)$ ein Graph in einem aktuell bekannten Zustand. Wir werden innerhalb dessen jetzt SZK verwalten. Also wir werden uns von jedem SZK, was darin auftritt die Wurzel speichern!

[!Definition] Umsetzung SZK in bekannten Graphen $G_a$ finden wie gehen wir vor, worin unterscheiden wir? #card Umsetzen können wir das, indem wir folgendes durchführen: $V_c=\{a\},E_c=\varnothing$ Folgend möchten wir jetzt die Kanten nach und nach betrachten: und unterscheiden hierbei für $(v,w)$:

-> $(v,w)\in T$, dann fügen wir $w$ zu $V_c$, und es ist eine neue SZK ( wir konnten sie ja erreichen!)

-> $(v,w)\notin T$, dann können wir mehrere SZKs weiterhin zu einer zusammenführen ^1704708885763

| Abgeschlossenheit |

Wir möchten jetzt den Begriff der Abgeschlossenheit für einen SZK einführen:

[!Definition] Definition Abgeschlossenheit was muss gelten? #card Wir nennen einen SZK $K$ abgeschlossen, falls die $dfs(v),\forall v\in K$ auch abgeschlossen sind

Wir wissen, dass bei einer SZK die maximale Zusammenhangskomponente benötigt wird, also bei allen kleineren SZK innerhalb dessen die gleiche Eigenschaft gelten muss! ^1704708885770

| SZK | Bestimmen | Vorgang;

Um entscheiden zu können, ob wir eine SZK gefunden ( oder nur eine Teilmenge davon!) haben, möchten wir ferner betrachten, wie dies durchgeführt werden kann.

Es wird bei dem ganzen Ablauf gefordert, dass wir zwei wichtige Mengen betrachten / haben.

[!Important] Notwendigkeit der Stacks Wurzeln und unfertig zur SZK-Findung warum brauchen wir sie? #card Wir benötigen beide, um entsprechende Zustände wahrnehmen zu können: Wurzeln: Stellt den Stack da, der die Folge der Wurzeln in den nicht abgeschlossenen Komponenten vermerkt. Dabei ist diese Listung in aufsteigender dfsnum!

unfertig: Beschreibt den Stack, der die Folge von Knoten $v$ angibt, für die $dfs(v)$ aufgerufen wurde. Dabei merkt es sich diese, wo die SZK noch nicht abgschlossen wurde. Auch dieser Stack ist aufsteigend geordnet. ^1704708885776

Wir möchten ferner ein Beispiel betrachten:

| Beispiel |

[!Example] SZK Beispiele Betrachten wir folgenden Graphen: ![[Pasted image 20231125205221.png]] Wir möchten jetzt den Stack Unfertig und Wurzeln erfahren und anschließend mit dem Knoten g fortführen was folgt? #card Unfertig = $\{a,b,c,e,g\}$ Wurzeln = $\{a,b,e,g\}$

Was wir zu den Kanten aus g sagen können: 1. $(g,d)$ wird nichts an der SZK ändern ! denn die SZK von $d$ ist abgeschlossen 2. $(g,c)$ vereinigt jetzt die 3 SZKs mit den Wurzeln $b,e,g$ ! Wir könenn sie also zusammenfassen / schrumpfen! –> Lösche jetzt $e$ und $g$. Wir haben dann nur noch die Wurzel $b$ 3. $(g,h)\in T$. Damit ist jetzt $h$ ein SZK und wird jetzt in unfertig und Wurzeln eingefügt ^1704708885782

| SZK Pseudocode |

Betrachten wir jetzt nochmal den Pseudocode für ein DFS: ![[111.20_Graphen_DFS#PseudoCode Kaufmann]]

Wir möchten in folgend erweitern:

in main: Setzen wir:

unfertig = WUrzeln = [] // empty stack! 
for all (v in V) 
	inUnfertig(v) = false // initialize metadata for v
	// indicator whether a note is already done or not 

in $dfs(v)$: Wir ergänzen:

push(v,unfertig) // add v to unfertig
inUnfertig(v) = true 
count1 ++
dfsnum(v) = count1  // setting this according to the number it started at 
S = S and {v} 
push(v,Wurzeln) // add v to Wurzeln 

for all ((v,w)) in E) 
	if w not in S: 
		dfs(w) 
	else if ( inUnfertig(w))
		while( dfsnum(w) < dfsnum(top(Wurzeln))) // comparing against the top most entry in the stack! 
			pop(Wurzeln) // reduce entries
count2 ++ 
compnum(v) = count2 

// abschliesen der SZK mit der Wurzel v
if ( v = top(Wurzeln))
	repeat
		w = top(unfertig) // taking the highest element from the stack! 
		inUnfertig(w) = false 
		pop(unfertig) // remove the element from the stack 
		// why not this ?? 
		w = pop(unfertig) 
		inUnfertig(w) = false 
	until (w = v)
	pop(Wurzeln)

[!Definition] Laufzeit dieser Erweiterung? #card Unter Anwendung von einer modifizierten Variante von DFS resultieren wir mit einer Laufzeit von $$\mathcal{O}(n+m)$$ ^1704708885788