date-created: 2024-05-27 08:09:06 date-modified: 2024-07-07 04:55:51

Zusammenhängende Graphen | Betrachten der Kanten

anchored to 115.00_graphentheorie_anchor

proceeds from 115.07_Satz_Von_Menger_Zusammenhängende_Graphen and 115.05_Kontraktion

Wir kennen schon die Zusammenhangszahl, welche also angibt, wie viele Knoten wir entfernen müssten, um einen Graphen in einen anderen aufzuteilen. Selbige Idee können wir jetzt auch für

Ferner werden wir sehen, dass man in dieser Betrachtung auch den Satz von Menger nochmal aus Sicht der Kanten definieren kann!

Kanten(zusammenhangs)zahl

Die Kantenzusammenhangszahl ( nicht die Knotenzusammenhangszahl) $\lambda (G)$ eines Graphen $G$ ist die kleinste Anzahl an Kanten, deren Entfernung den Restgraphen trennt. Ist jetzt $\lambda (G)\ge k$, dann ist $G$ auch $k$-kantenzusammenhängend. Für unzusammenhängende Graphen gilt dann $\lambda (G)=0$

Also der Kantenzusammenhang möchte Kanten entfernen, um einen Zusammenhang zu zerstören, während der Knotenzusammenhang dafür eben Knoten entfernt, um selbiges zu erzielen. Daraus können wir jetzt ein folgendes Lemma darstellen:

Lemma (23) | Unterschiede der Trennenden Charakteristiken

[!Lemma]

$K(G)\le \lambda (G)\le mi{n}_{u\in V}\mathrm{deg}(u)$ was sagt uns dieses Lemma aus, wie können wir die drei Betrachtungen beweisen? #card

1. $\lambda (G)\le mi{n}_{u\in V}\mathrm{deg}(v)$ Ist einfach, weil wir einfach die Kanten des Knotens mit dem geringsten / kleinsten Grad entfernen können ( somit ist er isoliert vom rest und somit geteilt)
2. $K(G)\le \lambda (G)$ Können wir in der Betrachtung lösen: Betrachte eine Menge von Kanten die entsprechend teilen, also wir haben eine bestimmte Kantenzahl. Dann können wir jetzt für jede Kante zwei Knoten betrachten ( wobei diese auch in gleiche andere Kante binden können, also zwei Kanten etwa in einem Knoten übergehen) und dadurch folgt dann, wenn wir einfach die Knoten entfernen, die durch diese Kanten verbunden sind, dann folgt $K(G)\le \lambda (G)$

Kantengraphen

Die Übersetzung eines Graphen mit Knoten und Kanten in einen Kantengraph ist der Vorgang, bei welchem jede Kante einem Knoten entspricht und eine Kante in dem neuen Graphen daher auftritt, wenn zwei Kanten aus dem Ursprung mit demselben Knoten verbunden sind.

Ferner wollen wir also definieren:

[!Definition] Kantengraphen

Betrachten wir einen $G=(V,E)$ und möchten dafür jetzt einen Kantengraphen bilden.

Wie würden wir vorgehen, um den Kantengraphen entsprechend zu konstruieren? #card

Um den Kantengraphen $L(G)$ vom Graphen $G=(V,E)$ bilden zu können, wird dieser für jede Kanten $e\in E$ einen Knoten $v\in L=(V^{\prime },E^{\prime })$ enthalten. Ferner sind zwei Knoten $\in L$ dann mit einer Kante verbunden, wenn diese beiden Kanten $e,f\in E$ die mind. einen gleichen Knoten haben. Bzw anders formuliert müssen $e,f\in G$ adjazente Kanten sein.

Visuell können wir etwa folgendes Beispiel betrachten:

Satz (24) | Menger für Kantenzusammenhänge

[!Definition] Ein Graph ist genau dann $k$-kantenzusammenhängend, wenn folgend gilt:

Was musse nach dem Satz von Menger gelten? #card

Es müssen je zwei Knoten durch mindestens $k$ kantendisjunkte Wege verbunden sind.

Kantendisjunkter Weg: Bedeutet wir benutzen disjunkte Kanten, um zwei Knoten zu verbinden. Hierbei darf man Knoten wiederverwenden, aber Kanten nicht.

Betrachten wir etwa folgenden Graphen, dann können wir hier genau diese Eigenschaft mit $k=3$ einsehen:

Beweis:

Es gibt die kleinste Mächtigkeiet einer $a$ von $b$ in $G=(V,E)$ trennenden Kanten Menge $X\subseteq C$ ist gleich der größþen Mäçhtigkeit einer Menge von kantendisjunkten $a-b$-Wegen Wir wende da den Satz von Menger Satz (20) Satz von Menger auf den Knotengraph von $G$ an, mit $A=E(a)$ ( alle zu $a$ inzidenten Knaten und) $B=E(b)$ was somit entsprechend des Satzes ist.

H-Wege

Wie definieren wir einen H-Pfad? #card Sei $H$ ein Graph, wir nennen einen Pfad $\pi$ einen H-Weg, wenn $\pi$ nicht trivial ist und den Graphen $H$ in genau seinen Endknoten $u$ und $v$ $(u\ne v)$ trifft. Ein H-Weg der Länge $1$ ist also eine Kante, die man im Graph $H$ noch nicht hatte.

• Wichtig ist, dass wir einen solchen H-Weg nur durch hinzufügen neuer Kanten und Knoten einbringen –> also eine Verbindung zwischen zwei Punkten ist dann eben noch nicht im Urprungsgraphen

Das brauchen wir in der Anwendung immer dann,

Lemma (25) | Kreis um $H$-Wege erweitern

[!Lemma] Kreis um $H$-Wege erweitern

Betrachte einen Kreis (welcher 2-zmhg ist) und füge jetzt $H-$Wege ein, was erhalten wir, wenn wir den Prozess wiederholen. Warum gilt das? #card

Wenn man von einem Kreis ausgehend jeweils zu einem bereits konstruierten Graphen $H$ einen H-Weg hinzufügt, erhält man induktiv genau alle $2$-zusammenhängende Graphen.

Das kommt daher, dass der Kreis in seiner Grundform schon 2-zusammenhängend ist. Ferner, wenn wir einen $H$-Weg hinzufügen, werden wir eine Verbindung von Knoten - oder mehreren, die wir dazu konstruieren - bauen die von Knoten in unserem Ursprungsgraphen zu einem anderen Knoten in diesem führen wird. Dabei wissen wir also, dass die Verbindung zwischen diesen “passiert” und ferner jeder neue Knoten - da er ein Pfad von $a\to b$ ist - genau 2 Kanten haben muss / wird.

Betrachten wir etwa einen Graphen der ein Viereck bildet. Wenn wir jetzt die zwei Diagonalen einfügen - sie sind $H$-Wege im Kontext des Originalgraphen -, dann erhalten wir einen $3-$-zusammenhängenden Graphen, aber dieser ist eben auch 2-zusammenhängend!

Beweis [Lemma (25) Kreis um $H$-Wege erweitern](#Lemma%20(25)%20Kreis%20um%20$H$-Wege%20erweitern)

Zu Zeigen ist: Alle so konstruierten Graphen sind $2$ zusammenhängend

Wir starten mit dem Startzustand des Kreises. Dieser ist alleinig schon 2 zusammenhängend!

Sei nun $H$ ein so konstruierter Graph und wir fügen jetzt H-Wege hinzu. Wir erhalten den Graphen $H^{\prime }$

Zuvor war $H$ schon 2-zusammenhängend und das heißt, wenn $H^{\prime }$ einen Schnittknoten enthält, müsste dieser auf dem $H-Weg$ liegen. Das kann kein Schnittknoten für $H^{\prime }$ sein

Sei jetzt $G$ ein 2-zusammenhängender Kreis:
Dadurch enthält $G$ einen Kreis und ferner enthält $G$ einen maximalen Teilgraph ($H$) der, wie obig durch die H-Wege konstruiert ist. Für jede Kante $(xy)\in E(G)\setminus E(H)$ ist dann ein H-Weg und ist somit der induzierte Untergraph.

Sei dann jetzt $H\ne G$ Dann ist die Kante $uv$ mit $u\in H,ve\in G\setminus H$ Aber da wie obige gesagt $G$ 2-zusammenhängend ist, gibt es einen Weg $\pi$ in $G\setminus u$ von $v$ zu $H$ . Dann ist $uv\pi$ aber ein H-Weg in $G$ und $H\cup uv\pi$ dann größer als der Teilgraphen von $G$ –> was ein Widerspruch ist, weil wir gesagt haben, dass $H$ maximal ist. ( Das heißt es würde hier quasi noch einen neuen H-Weg geben, den wir zuvor nicht “gesehen” hatten)

Idee Starte mit 2zsm Kreis, bilde jetzt einen Teilgraphen und dann nehmen wir nach und nach heraus -> wollen widerlegen, dass man dann noch einen neuen H-Weg finden kann.

3-Zusammenhang

Lemma (26) | 3-Zusammenhängend $\to$ eine Kante kann entfernt werden

[!Lemma] Sei $G=(V,E)$ und weiter $\mid V\mid >4$ und $G$ ist 3-zusammenhängend

Was lässt sich aus dieser Prämisse im Kontext von Kanten in $G$ folgern? #card

Gelten die obigen Eigenschaften, dann hat $G$ eine Kante $e$, sodass dann $G\setminus e$ weiterhin 3-zusammenhängend ist!

Das können wir folgend beweisen:

Beweis dur h Widerspruch:

Für jede Kante $(x,y)\in G$ gilt folgend: $G/(x,y)$ hat dann eine trennende Knotenmenge $S$ mit $\mid S\mid \le 2$ Es gilt nun ferner: $v_{xy}\in S$ ( was der kontrahierte Knoten ist, aus der Kante $(x,y)$) und ferner auch $\mid S\mid =2$

Sei nun $S=\{z,v_{xy}\}$ dann gilt: $S^{\prime }=\{x,y,z\}$ ist die trennende Knotenmenge in $G$. ( da wir sie ja ohne den kontrahierten Knoten konstruieren konnten / können) Dadurch folgt jetzt: Jeder Knoten aus $S^{\prime }$ hat einen Nachbar $\in G\setminus S^{\prime }$ ( also der Graph ohne die Knoten und Kanten, die mit der Menge definiert bzw zu dieser verbunden sind.) Ferner heißt das also, dass sie einen Nachbar zu jeder Komponente des Graphen hat.

Wir wollen jetzt den Widerspruch konstruieren:

Wähle jetzt $x,y$ und $z$, sodass die Komponente möglichst klein ist. ( das soll die kleinste mögliche Schnittkomponente sein). Wenn wir jetzt aber $z,v,w$ gefunden / gewählt wird, dann ist diese Komponente kleiner ( das machen wir indem wir vom Originalgraphen starten und hier neu kontrahieren, sodass wir diese kleinere Menge konstruieren können)

Sei $v$ der Nachbar von $z$ in $C$: C ist dabei die Komponente, die wir sehr klein konstruieren. $G/zv$ ist nicht 3-zsh - nach der Annahme.

Es gibt jetzt ferner wieder eine Menge $\{z,v,w\}$ die $G$ trennt und jeder dieser Knoten hat einen Nachbarn in $G\setminus \{z,v,w\}$ Da jetzt $x,y$ benachbart sind , gibt es ferner eine Komponente $D$ in $G\setminus \{z,v,w\}$ mit $D\cap \{x,y\}=/\varnothing$ ( also es ist eine andere Menge! und somit sind sie fremd zueinander) Jeder Nachbar von $v$ in $D$ ist dann in C, aufgrund von $v\in C$

Weiter aber: $D\cap C\ne \varnothing$ und damit gilt auch, dass $D\subset C$ **was im Widerspruch zur Annahme / Konstruktion von $x,y,z$ **

Der Widerspruch kommt durch die Wahl von $z,x,w$, da sie scheinbar nicht die kleinste Komponente bilden ( wie wir aber angenommen bzw sie konstruiert haben).

Satz (27) | Satz von Tutte

Zuvor haben wir bereits den $2$-Zusammenhang angeschaut und gezeigt, dass man einen Kreis einfach mit $H$-Wegen erweitern kann, um dann jeden 2ZSM-Graph darstellen zu können.

Wir wollen jetzt betrachten, wie / wann ein Graph $G=(V,E)$ $3$-Zusammenhängend ist.

[!Definition] Satz von Tutte 1961

wann nennen wir einen Graphen 3-zusammenhängend? Wie kann aus einer Folge $G_0,\dots ,G_K$ dann der 3-zusammenhängende Graph gebildet werden? #card

Ein Graph $G=(V,E)$ ist genau dann 3-zusammenhängend, wenn eineFolge $G_0,\dots ,G_k$ von Graphen existiert, die die folgenden Eigenschaft einhält:

1. $G_0=K_4,\wedge G_k=G$ -> also wir fangen garantiert mit dem vollständen $K_4$ Graphen an
2. $\forall i,k$ enthält jetzt $G_{i+1}$ eine Kante $(x,y)$ wobei für ihre Knoten gilt: $deg(x),deg(y)\le 3$ und weiterhin gilt: $G_i=G_{i+1}\setminus (x,y)$ ( mit jeder weiteren Folge haben wir also eine weitere Kante, mit spezifischen Eigenschaften, die aber bei der ersten noch nicht gilt)

Es folgt hieraus generell gesagt: Alle Graphen $G_0,\dots ,G_k$ sind 3-zusammenhängend sein!

[!Attention] Wir können generell folgern, dass man immer auf einen $K_4$ endet, wenn man einen minimalen $3$-zsh Graphen erhalten möchte. Das folgt daraus, dass bei dieser Konstruktion und der Kontraktion eines Graphen immer passieren wird, dass man für einen 3zsh Graphen dann einen K4 brauch.

Beweis

Eine Richtung ist aufgrund des [Lemma (26) 3-Zusammenhängend $to$ eine Kante kann entfernt werden](#Lemma%20(26)%203-Zusammenhängend%20%20eine%20Kante%20kann%20entfernt%20werden) möglich.

$G$ ist 3-zusammenhängend, dann folgt aufgrund des Lemmas: $⟹G_0,G_1,\dots ,G_k$ existieren. (DIese Konstruktion haben wir zuvor gezeigt). Es ist nicht notwendig zu zeigen, dass die Grade immer $3\le$ sind, denn das folgt implizit aus der Annahme selbst! ( Wenn der beginnende Graph schon $3-ZSH$) ist.

Rückrichtung: $\Leftarrow$ Zu Zeigen ist jetzt: Aus $G_i$ ist 3-zusammenhängend, folgt $G_{+1}$ ist auch 3-zusammenhängend.

WIr wollen das auch wieder durch einen Widerspruch beweisen: Wir betrachten $G_i$ und nehmen an: $$G_i=G_{i+1}/(x,y)$$ und ferner $G_{i+1}$ ist nicht 3-zusammenhängend.

Sei jetzt $S$ die trennende Knotenmenge mit $\mid S\mid \le 2$ ( wie in [Lemma (26) ](#Lemma%20(26)%203-Zusammenhängend%20%20eine%20Kante%20kann%20entfernt%20werden)) Seien dann jetzt $C_1,C_2$ Komponenten von $G_{i+1}\setminus S$ (Also die Komponenten, die durch entfernen der trennenden Menge entsthe / auftreten!)

Ohne Betrachter der Allgemeinheit folgt dann daraus: $V(C_1\cap \{x,y\}=\varnothing )$ ( wobei $V(C_1)$ die Knotenmenge von $C_1$ darstellt) Was wir damit sagen wollen: Wir haen die Schnittmenge, die den Graphen in Menge $C_1,C_2$ aufteilt. Wir sagen jetzt, dass eine der beiden Komponenten jetzt nicht $x,y$ (Knoten) enthält. Es können nicht beide diese Knoten enthalten!

Wir wollen sagen, dass $x,y$ nicht gleichzeitig in einer Menge sein können, sondern einer in der Schnittmenge enthalten sein muss. Sonst könnte man mit diesen Knoten kontrahiert wieder einen Schnitt erzeugen

Ferner $C_2$ enthält weder ($x$ und $y$) noch einen anderen Knoten $v\notin \{x,y\}$ denn sonst wäre $v_{x,y}$ ( also beide Knoten kontrahiert! ) oder nur $v$ durch 2 Knoten von $C_1$ getrennt. –>

Dann folgt: $C_2$ enthält entweder nur $x$ oder nur $y$, woraus dann folgt: $$deg(x),deg(y)\ge 3$$ was im Widerspruch steht!

Ohrenzerlegung

Es lässt sich jetzt noch eine Operation durchführen - und dafür ein Algorithmus bestimmen - welche einen Graphen in einer bestimmten Struktur aufteilen kann / wird.

115.12_Ohrenzerlegung

Satz (33) | Kettenzusammenhang <-> 2-zsh

[!Definition]

Sei jetzt $C=\{C_1,\dots ,C_{\mid E\mid -\mid V\mid +1}\}$ eine Kettenzerlegung eines einfachen Graphen $G=(V,E)$. Dann ist $G$ genau dann 2-zsh, wenn folgend gilt:

was muss folgen? Wie könnte man das beweisen? #card

Wenn jeder Knoten mindestens von Grad 2 ist und $C_1$ der einzige Kreis in der Kettenzerlegung von $G$ ist.

–> Beweis-Idee:

• Man könnte die Konstruktion eines H-weges auf einen Kreis als Konstruktion betrachten und mit dieser Information dann nach und nach den Graphen $G$ rekonstruieren, wobei ein H-Weg dann immer einer Kettenzerlegung entspricht.
• Wenn er 2-zsh ist, dann kann man ihn Schrittweise in einen Kreis und zusätzliche H-Wege aufteilen, was genau die Kettenzerlegung darstellt.

Beweis | Einfache Berechnung der ohrenzerlegung

Die Idee baut darauf auf, dass wir zeigen, dass eine Kante $v$ eine schnittkante ist ( also eine Kante, wenn man sie entfernt, dann zerteilt sich der Graph) genau dann, wenn

Angenommen $v$ ist nicht inzident zur Brücke bzw der Schnittkante ()

$St$-Nummerierung

[!Definition] $St$-Nummerierung

Sei $G=(V,E)$ ein einfacher 2-zusammenhängender Graph und $s,t$ eine Kante in $E$.

wie kann nun eine st-Nummerierung vorgenommen werden, was fordert sie? #card

Eine $st$-Nummerierung von $G$ ist eine Nummerierung der Knoten $V$, sodass dann folgt:

• $s$ hat die Nummer 1 ( der Startende Knoten im Graphen)
• $t$ hat die Nummer $n$ (–> hier also die höchste mögliche in der Nummerierung des Graphen)
• für alle anderen Knoten gilt: $v\in V\setminus \{s,t\}$ ist adjazent zu einem Knoten mit kleinerer und mit einem Knoten mit größerer Nummer

Also in der Betrachtung haben wir also einen Graphen, der wo wir nach und nach nummerieren und immer fordern, dass ein Graph zu einem mit höherer und und niedriger Nummer haben Betrachten wir etwa folgendes Beispiel:

man sieht, dass mehrfache Bindung ok ist. Es muss von beiden mindestens eine Verbindung geben.

Beweis-Idee: Man kann das etwa damit beweisen, dass man einen Kreis betrachtet, der 2-zsh ist, dann gilt diese Eigenschaft für alle (bis auf den schließenden Part s und t ( aber die werden ja nicht genau betrachtet)) also ist die Eigenschaft dafür erfüllt!

[!Satz] Folgerung aus $st$-Nummerierung

Ein Graph $G=(V,E)$ hat genau dann eine $st$-Nummerierung, wenn er 2-zsh ist!

warum folgt das? #card

$St$-Orientierung

Wir möchten noch die St-Orientierung als Verarbeitung eines Graphen betrachten, wobei wir hier auch bestimmte Aussagen treffen können:

[!Definition] $St$-Orientierung

Betrachten wir einen einfachen Graph $G=(V,E)$ und eine Kante $(s,t)\in E$ Wir nennen eine $st$-Orientierung (oder auch bipolare Orientierung ) von G, wenn folgende Eigenschaften erfüllt werden.

welche Eigenschaften müssen folgen. Was ähnelt diese Struktur? #card

eine $st$-Orientierung ordnet jeder Kante $\in E$ eine Richtung zu, sodass $G$ am Ende ein gerichteter azyklischer Graph mit $s$ als einziger Quelle und $t$ als einziger Senke(Ziel) ist. folgend etwa ein Beispielgraph:

Auch hieraus können wir dann eine spezielle Folgerung ziehen

Lemma (31) | Folgerung St-Orientierung und St-Nummerierung

[!Lemma]

Ein Graph hat eine $st$-Nummerierung, genau dann, wenn er eine $st-$Orientierung hat.

wieso folgt die Aussage, was ähnelt diese Struktur #card

Durch die azyklische Eigenschaft können wir fordern, dass eine kleinere Zahl nicht nochmal von einem späteren Knoten berührt werden kann (und somit vielleicht nur kleinere Knoten hat und keinen gröseren adjazent hat. ).

Am Ende ist es einfach eine topologische Sortierung von Graphen.

Beweis-Idee: Eine st-Nummerierung erhält man aus einer st-Orientierung, durch das topologische Sortieren.

Eine st-Orientierung erhält man aus st-Nummerierung dadurch, dass Kanten von dem mit der niedrigeren

$st$-Nummerierung Aus Ohrenzerlegung

Man kann jetzt ferner aus einer Ohrenzerlegung heraus noch eine gültige $st$-Nummerierung erzeugen:

[!Definition] st-Nummierung durch Ohrenzerlegung

Sei $G=(V,E)$ ein einfacher 2-zsh Graph und ferner eine Kante $(s,t)\in E$

Annahme: Man kann die Ohrenzerlegung so berechnen, dass hierbei $s,t\in P_0$ (also dem Kreis).

wie würden wir vorgehen, wieso benötigen wir die st-Orientierung? #card

Um das zu lösen: Bestimmen wir die st-Orientierung:

• Orientiere $(s,t)$ von $s\to t$ und die anderen Kanten in $P_0$ ebenfalls in Richtung $s\to t$.
• Orientiere $P_i=(u,\dots ,w)$ von $u\to w$, wenn $u$ vor $w$ liegt (in der Ordnung, die soeben haben).

Daraus folgt dann ein entsprechender Baum:

Unabhängige Spannbäume

Betrachte hierfür nochmal 111.26_Graphen_MST (wobei das ein Spezialfall, dem kleinsten Spannbaum, ist).

[!Definition] Unabhängige Spannbäume:

Wir wollen Spannbäume eines Graphen als unabhängig definieren, wenn folgendes gilt:

welche zwei Eigenschaften sollen gelten? #card

1. alle haben dieselbe Wurzel $r$
2. für jeden Knoten $x\ne r$ sind die Pfade von $r\to x$ in jedem Spannbaum kreuzungsfrei (also dass die Pfade knotendisjunkt sind bis auf den Endknoten)

Anders gesagt verläuft jeder Spannbaum so, dass er sich niemals mit einem anderen kreuzt, außer halt im Ursprung un dessen Ende ( weil er ja jeden Knoten erreichen muss). –> Wir sehen, es muss also mehrere Wege zu einem Knoten geben und das für jeden!

Visuell etwa mit folgendem Graph darstellbar: Wir sehen hier, dass jede Verbindung von der Wurzel zu einem Knoten im Graphen niemals zwei Pfade hat, die sich schneiden. (Sie dürfen die gleichen Kanten verwenden, aber sie dürfen sich eben nicht schneiden!)

Hieraus kann man dann eine Vermutung mit Bezug auf k-zusammenhängende Graphen bilden:

[!Important] Annahme (Itai, Rodeh (1984)):

Es besteht die Annahme, dass jeder k-zusammenhängende Graph auch $k$ unabhängige Spannbäume enthält.

Weswegen folgt das? #card

Idee: Wir wissen, dass zu jedem Knoten $k$ Kanten führen, also können wir dann auch davon ausgehen, dass es $k$ Spannbäume gibt, die jeweils diese Kanten ausnutzen, um einen Spannbaum zu bauen.

Spezialfall | 2-zsh

[!Information]

Jeder 2-zsh Graph enthält zwei unabhängige Spannbäume. (Was aus der obigen, allgemeinen Aussage folgt).

wie können wir das konstruieren? Inwiefern kann man hier die st-Nummerierung nutzen? #card

theoretisch könnten es auch mehr Spannbäume sein, also eher ein mindestens (Wenn er etwa höher zusammenhängend ist, kann es ab und zu noch einen weiteren Spannbaum geben. Aber wenn er 2zsh ist, dann wird es halt nur 2 geben!)

• Wir können jetzt die St-Nummerierung berechnen
• Für jeden Knoten $x\ne \{s,t\}$ verbinden wir diese mit dem Nachbar mit der kleinsten / größten Nummer –> es finden sich somit zwei Spannbäume!

Visuell etwa so: