notes/school/di-ma/20181106_1-zusammenhangskomponenten.md

---
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**: ![Beispiel Graph](20181106_1-weg_pfad_kreis.png)

* $(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**: ![Beispiel Graph](20181106_1-zhk.png)
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$