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

| 2-fache Zusammenhangskomponenten (2ZHK) |

anchored to [[111.00_anchor]] proceeds from [[111.24_Graphen_SZK]] and [[111.23_Graphen_ZHK]]

| Overview |

Als erweiterte Betrachtung zu normalen Zusammenhangskomponenten möchten wir uns jetzt noch 2-fache ZHK anschauen.

Diese bauen grundlegend auf dem Verständnis von ZHK auf, aber betrachten diese in einem zusammenhängenden Kontext zwischen des Graphen:

[!Definition] Definition | 2ZK | 2fache Zusammenhangskomponente | was ist relevant bei der Betrachtung eines Graphen? #card Betrachten wir einen ungerichteten Graphen $G = (V, E)$ . Wir nennen ihn jetzt 2-fach zusammenhängend, wenn $\forall v \in V :$ gilt, dass der Graph ohne diesen Knoten immernoch zusammenhängend ist. Also $\forall v \in V : G ∖ {v} = zusammenh \overset{a}{¨} ngend$ ^1704708892493

[!Important] Folgerungen für eine 2fache Zusammenhangskomponenten | was wird der entstehende Teilgraph sein? #card ein entstehender Teilgraph einer 2fachen Zusammenhangskomponente ist ebenfalls ein maximaler 2-fach zusammenhängender Teilgraph! Das heißt, dass auch dieser die Eigenschaft aufweisen kann, und dabei dann der maximale Teilgraph mit dieser Eigenschaft sein wird. ^1704708892502

| Artikulationspunkte |

[!Tip] | Definition eines Artikulationspunktes | was beschreiben wir als Artikulationspunkt, was erzeugt er? #card Sprechen wir von einem Artikulationspunkt, dann beschreiben wir hiermit einen Knoten $v \in V$ wenn gilt ,dass dann der Graph $G ∖ {v}$ nicht mehr zusammenhängend ist. Das heißt, wenn wir einen solchen Punkt finden, dann wird durch Entfallen dessen der Graph nicht mehr zusammenhängend sein –> wir haben also einen zentralen Knotenpunkt gefunden, der wahrscheinlich wichtig ist, um daen Graphen zusammen zuhalten! ^1704708892513

| Beispiel |

[!Example] Beispiel 2ZK | Betrachten wir folgenden Graphen, dann möchten wir in diesem jetzt wichtige Eigenschaften identifizieren und beschreiben können. ![[Pasted image 20231201141542.png]] Wo finden wir 2ZK ? Gibt es Artikulationspunkte? #card 2ZK wären etwa ${a, b, e, d}, {d, c, f}, {c, g}$ und wir haben hier zwei Artikulationspunkte: $c, d$ ^1704708892521

Zuvor haben wir bereits das durchlaufen [[#Prinzip des Durchmustern von Graphen|“Durchmustern”]] von Graphen betrachten und dabei zwei mögliche Varianten kennengelernt. Wir möchten jetzt DFS nochmal betrachten und die Eigenschaften die anschließend erhalten werden, evaluieren und später erweitern, sodass wir solche Komponenten finden können.

Wir erhalten hierbei jetzt folgendes:

gibt uns die Tree-nodes ( [[111.20_Graphen_DFS#T,F,B,C Partitionen im Graph]])
backwards-nodes ( also wie wir von einem Punkt zurückspringen können) was wir nicht erhalten:
forward-nodes
cross-nodes

[!Idea] Idee um jetzt Artikulationspunkte zu finden: was können wir aus den Partitionen des DFS schließen und wie können wir damit Artikulationspunkte finden? #card Wir können aus der Betrachtung folgern, dass $v$ kein Artikulationspunkt ist, wenn der Tree-Nachfolger $w$ eine Rückwärtskante vor $v$ aufweist. Visuell: ![[Pasted image 20231201143540.png]]

Das heißt also etwa: wir können ausschließen, dass ein bestimmter Knoten $v$ ein Artikulationspunkt ist, wenn die nachfolgenden Punkte sich irgendwie mit den vorherigen Punkte nvon $v$ verbinden. ^1704708892528

| Konstruktion der Berechnung |

Aus der vorherigen Betrachtung möchten wir jetzt ein Vorgehen konstruieren, was uns dabei helfen kann, Artikulationspunkte in einem Graphen finden zu können.

[!Definition] | Betrachtung zur Bestimmung von Artikulationspunkten | wie können wir aus dem vorherigen Informationen jetzt schauen, ob $v$ ein Artikulationspunkt ist? #card

Wir betiteln jetzt einen Knoten $v$ als Artikulationspunkt, wenn es von diesem einen Zweig gibt, der nicht in den vorherigen Teil ( also vor $v$ ) zurückspringt. Das heißt man kann ihn nur über v erreichen!

Für diese Wurzel $v$ des Baumes gilt dann, dass $v$ ein Artikulationspunkt ist, wenn es mehr als einen Zweig von ihn gibt. –> vereinfacht: Wenn wir sehen, dass unser Knoten einen Baum mit mehr als einen Ast aufspannt, dann ist dieser ein Artikulationspunkt, sofern man von diesen Zweigen nicht mehr vor den Knoten $v$ kommen kann. ^1704708892536

[!Example] | Beispiel Artikulationspunkt | ![[Pasted image 20231201144923.png]] Warum ist hier v ein Artikulationspunkt und wofür ist er es? #card Der linke Arm/Zweig kann nur von $v$ aus erreicht werden und somit sit $v$ ein Artikulationspunkt, weil wir keinen zusammenhängenden Baum mehr hätten, würde dieser fehlen! ^1704708892546

| PseudoCode Finden von Artikulationspunkten |

Wir möchten jetzt [[111.20_Graphen_DFS|DFS]] so anpassen, dass wir damit Artikulationspunkte finden können.

Dafür möchten wir zuvor eine bestimmte Funktion betrachten, die wir später anwenden werden:

def low(u): Optional = 
	min ( dfsnum(u),
	min_v{ dfsnum(v) mit Pfad u => *tm z => bv} // also wir können den Pfad von u nach v mit einem Zwischenpfad konstruieren.
	// minimum von:
	// - dfsnummer des derzeitigen Knoten 
	// - dfsnummer mit Pfad von u nach v  
	)

[[111.20_Graphen_DFS#PseudoCode Kaufmann]]

PseudoCode für DFS, wir möchten jetzt folgend den vorher bestimmten Pseudocode erweitern:

T = tree-edges // also alle die, mit dem wir einen Baum aufbauen!
F = forward-edges // alle die, wo wir von einem Zwei in einen anderen kommen
B = backwards-edges // alle die, die von einem Zweig zu einem vorherigen Knoten zurückspringen 
C = cross-edges // alle die, die außerhalb oder zu einem Punkt springen 

def DFS(v): Unit = 
	for all ( ( v,w ) in E)
		if w not in S 
			S = S mit w // adding w as node that we now have traversed ( because we have to track the ones we have visited already!)
			dfsnum(w) = count1  // indicating that we have called node _w_ at which step 
			// --- updating according to previously defined traits!
			low(w) = dfsnum(w) 
			
			// this could be at the beginning or later within another recursion --> this helps to keep track when we traverse a node!
			count1 ++ //
			DFS(w) // calling recursively to explore within the available neighbors of this node!
			if(low(w) < low(v)) 
				low(v) = low(w) // wir haben mit low(w) einen kleinere dfsnummer gefunden!, die wir setzen möchten.
			if( low(w) >= dfsnum(v) )
				artikulationspunkt(v) = true // gefunden, setzen wir jetzt!
			else
				if( dfsnum(w) < low(v) )
					low(v) = dfsnum(w)

In dieser Betrachtung partitionieren wir später nicht mehr in einzelne Kompartments, weil wir diese Information nicht benötigen.

[!Important] Erklärung der Änderungen im PseudoCode:was bewirken die drei if-statements, die wir in unserem modifizierten Code einbringen? #card
if(low(w) < low(v)) 
  low(v) = low(w) // wir haben mit low(w) einen kleinere dfsnummer gefunden!, die wir setzen möchten.
Dieses If: setzt den low-Wert von $w$ für $l o w (v)$ , falls er kleiner ist.
if( low(w) >= dfsnum(v) )
  			artikulationspunkt(v) = true // gefunden, setzen wir jetzt!
Dieses If: berücksichtigt mögliche backwards-edge von $v ⟹ w$ !
if( dfsnum(w) < low(v) )
  				low(v) = dfsnum(w)
Dieses If erkennt weiterhin, ob ein Zweig von $v ⟹ w$ keine backwards-edge vor $v$ hat –> denn dann haben wir einen Artikulationspunkt für $v$ gefunden!

^1704708892554

Es gibt hier noch einen Spezialfall den wir betrachten können:

[!Definition] Spezialfall $v$ Wurzel mit kleinster dfsnum was machen wir dann? #card Wenn $dfs\num(v) =1 \land \exists w_{1},w_{2}: (v,w_{1}),(v,w_{2})\in T$ dann folgt daraus: $v$ ist ein Artikulationspunkt! und somit $a r t ik u l a t i o n s p u nk t (v) = t r u e$ ^1704708892562

Aus dieser Betrachtung heraus haben wir jetzt einen Algorithmus geschaffen / konstruiert, der es uns ermöglicht in geringerZeit Artikulationspunkte von einem Graphen zu finden.

| Laufzeit |

Wir betrachten noch die Laufzeit dieses Algorithmus:

[!Important] Laufzeit | Artikulationspunkt-Finder | welche Laufzeit erhalten wir für den modifizierten DFS? #card Wir haben den DFs modifiziert und dabei seine Laufzeit auf $O (n + m)$ optimieren können. [[111.20_Graphen_DFS#Betrachtung der Laufzeit|Laufzeit plain DFS]] ^1704708892570

[!Defintion] Aus diesem Algorithmus können wir jetzt relativ einfach 2ZKs bestimmen / in einem Graphen finden!

scattered-lenity