112 lines
2.9 KiB
Markdown
112 lines
2.9 KiB
Markdown
---
|
|
title: Zusammenhangskomponenten
|
|
date: 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$
|