2.9 KiB
| title | date |
|---|---|
| Zusammenhangskomponenten | 2018-11-06 |
Definition (Weg, Pfad, Kreis)
Sei G=(V,E) ein Graph.
a) Ein Weg w = (v_0, v_1, ..., v_{l-1}) (der Länge l) ist ein Tupel mit
v_i \in V und \{v_i, v_{i+1}\} \in E, \forall i \in \{0, ... l-2\}
b) Ein Pfad ist ein Weg ohne Kontenwiederholung, d.h. $p = {v_0, v_1, ...
v_{l-1}}$ mit v_i \in V, ${v_i, v_{i+1}} \in E, \forall i \in
{0,...,l-2}$ und v_i \neq v_j, \forall i = j
c) Ein Kreis ist ein Pfad k = (v_0, ... v_{l-1}) mit \{v_{l-1}, v_0\} \in E
Beispiel: 
(1,2,3,2,1,3)Weg, aber kein Pfad(3,1,2,4)Weg und Pfad, aber kein Kreis(2,4,1)Weg, Pfad und Kreis
Definition (Verbindbar)
Sei G=(V,E) und u,v \in V, dann heißen u und v verbindbar, falls es
einen Weg von u nach v gibt.
Verbindbar ist eine Relation auf der Menge der Knoten. Bei u verbindbar mit
v: u \sim v
Diese Relation ist
a) reflexiv: u \sim u, \forall u \in V (durch den Punktpfad (u))
a) symmetrisch: Falls u \sim v, dann auch v \sim u (da Graph
ungerichtet)
a) transitiv: Falls u \sim v und v \sim w, dann gilt auch $u \sim w$
(hängen die Wege von u nach v und v nach u aneinander)
\Rightarrow Verbindbar ist eine Äquivalenzrelation
Es gibt Äquivalenzklassen. Für u \in V betrachte $[v] = {v \in V | u \sim
v}$ Äquivalenzklasse von u. Es gilt für u,v \in V
[u] \cap [v] = \begin{cases}
\emptyset & \lnot (u \sim v) \\
[u] = [v] & u \sim v
\end{cases}
und \bigcup\limits_{u \in V} [u] = V, d.h. Äquivalenzklassen bilden Partition
von V.
Definition (Zusammenhangskomponente)
Sei G=(V,E) ein Graph. Die Untergraphen G[[u]], u \in V heißen
Zusammenhangskomponenten von G. G heißt zusammenhängend, falls er nur aus
einer Zusammenhangskomponente besteht, d.h. [u] = V, \forall u \in V
Beispiel: 
Hat 3 Zusammenhangskomponenten:
\begin{align*}
[1] &= &\{ 1,2,3,4 \} \\
[2] &= [3] = [4] = &\{ 1,2,3,4 \} \\
[5] &= [7] = &\{ 5,7 \} \\
[6] &= &\{ 6 \} \\
\end{align*}
Satz
Jeder Graph G=(V,E) hat mindestens |V| - |E| Zusammenhangskomponenten.
Beweis
Per Induktion über die Anzahl der Kanten |E|.
Für |E| = 0 hat G=(V,E) |V| Komponenten. Sei der Satz richtig für alle
Graphen mit |E| \geq m. Betrachte nun G=(V,E) mit |E| = m+1.
Sei e = \{u,v\} \in E und G' = G \setminus \{e\} = (V, E'), dann gilt $|E'|
= m$ und nach Voraussetzung hat G' mindestens $|V| - |E'| = |V| - m$
Komponenten.
2 Fälle:
a) u und v liegen in der gleichen Zusammenhangskomponente von G', dann
hat G die gleichen Zusammenhangskomponenten wie G'
a) u und v liegen un zwei verschiedenen Zusammenhangskomponenten von G',
dann hat G eine Zusammenhangskomponente weniger, als G'
\tag*{$\Box$}
Folgerung: Für jeden zusammenhängenden Graph G=(V,E) gilt $|E| \leq
|V|-1$