2 Wege und Zusammenhang
Definition
- Kantenfolge (walk): Folge der beliebigen verbundenen Knoten / Kanten
- Kantenzug (circuit/trail): unterschiedliche Kanten, beliebige Knoten
- Weg (path): unterschiedliche Knoten/Kanten
- Kreis (circle/loop): ein Weg, dessen Anfangs- und Endknoten verbunden sind
- Dreieck (triangle): ein Kreis der (minimalen) Länge 3.
Definition
- Zwei oder mehr Wege heißen kreuzungsfrei (edge-disjoint paths), wenn keiner einen inneren Kanten eines anderen enthält.
- Zwei \(a-b-\)Wege sind genau dann kreuzungsfrei, wenn sie bis auf a und b disjunkt sind.
- Seien \(P, Q\) kreuzungsfreie \(a-b-\)Wege mit der Länge des Weges \(l(P) + l(Q) ≥ 3\). Dann heißt \(P \cup Q\) ein Kreis (circle).
- Die Länge eines Kreises ist die Anzahl seiner Knoten (und bei Kreise auch Anzahl Knoten).
Satz 2.8
Graph mit \(d(G) \geq 4k\) hat einen \(k\)-zusammenhängenden Teilgraph.
Definition (trennende Menge)
Sei \(G=(V,E)\) ein Graph und \(A,B\subseteq V\).
Eine Teilmenge \(X\subseteq V \times E\) heißt ein A-B-Trenner in \(G\), wenn jeder \(A\)-\(B\)-Weg in \(G\) mindestens einen Punkt aus \(X\) enthält.
Bemerkung
- Aus der Definition folgt, dass \(A\cap B\subseteq X\), da für jeden \(c\in A\cap B\) der triviale Weg \(P_0 = \{c\}\) existiert.
- Das Entfernen eines Trenners in G erhöht die Anzahl der Zusammenhangskomponenten von G.
Definition (Trennung zweier Knoten)
Eine Teilmenge \(X\subseteq V\cup E\) trennt Knoten \(a,b\in V\), wenn
- \(a \neq b\),
- \(a, b \notin X\)
- \(X\) trennt \(\{a\}\) und \(\{b\}\).
Definition
- Einer Artikulation / Gelenkpunkt / Schnittknoten entspricht ein Trenner \(Z=(X,Y)\) mit \(X=\{v\}\) und \(Y=\emptyset\).
- Einer Brücke entspricht ein Trenner \(Z=(X,Y)\) mit \(X=\emptyset\) und \(Y=\{e\}\).
Beispiel
- Der Graph \(K_2\) hat eine Brücke, aber keine Artikulation.
- Der zweite Graph auf dem Bild hat zwar eine Artikulation, aber keine Brücke.
Bemerkung
- Ist \(v\in V\) eine Artikulation, dann trennt \(v\) zwei Knoten, die zur selben Zusammenhangskomponente des Graphen gehören.
- Besitzt ein zusammenhängender Graph eine Artikulation, so ist seine Knotenzusammenhangszahl gleich 1 und er wird als separabel bezeichnet.
- Ist \(\{a,b\} \in E\) eine Brücke, dann trennt \(e\) die Endknoten \(a, b\).
- Besitzt ein zusammenhängender Graph eine Brücke, so ist seine Kantenzusammenhangszahl gleich 1.
Lemma
Ist G ein Graph und \(e \in E(G)\), so
- Die Zahl der Zusammenhangskomponenten erhöht sich durch Entfernen der Kante \(e\) um höchstens 1: \[c(G) \leq c(G - e) \leq c(G) + 1\]
- \(e\) gehört zu einem Kreis von \(G\) genau dann, wenn \[c(G) = c(G - e)\]
Folgerung
Es sei \(e\) eine Kante eines Graphen G. Dann ist folgendes äquivalent:
- \(e\) ist Brücke
- \(c(G) < c(G - e)\)
- \(c(G - e) = c(G) + 1\)
- \(e\) gehört zu keinem Kreis von G