111 lines
3.0 KiB
Markdown
111 lines
3.0 KiB
Markdown
|
---
|
||
|
|
title: Eulertouren
|
||
|
|
date: 2018-11-21
|
||
|
|
---
|
||
|
|
|
||
|
|
**Frage**: Gibt es einen Rundweg, auf dem man jede Brücke genau einmal
|
||
|
|
überquert?
|
||
|
|
|
||
|
|
Entspricht der Frage, ob es in dem Graph (der leider kein Graph in unserem
|
||
|
|
Sinne ist) einen Weg gibt, der
|
||
|
|
|
||
|
|
i) jede Kante enthält
|
||
|
|
i) Start- und Endknoten gleich sind
|
||
|
|
|
||
|
|
# Definition (Eulertour)
|
||
|
|
|
||
|
|
Sei $G=(V,E)$ ein zusammenhängender Graph.
|
||
|
|
|
||
|
|
i) Eine **Eulertour** in $G$ ist ein Weg, der jede Kante genau einmal
|
||
|
|
durchläuft und bei dem Start- und Endknoten gleich sind
|
||
|
|
|
||
|
|
i) Ein Graph, der eine Eulertour enthält, heißt **eulersch**
|
||
|
|
|
||
|
|
|
||
|
|
**Beispiel**:
|
||
|
|
|
||
|
|
a)  ist eulersch, da
|
||
|
|
$(1,4,3,2,6,4,5,2,1)$ eine Eulertour ist
|
||
|
|
|
||
|
|
a)  enthält zwar einen Weg, der
|
||
|
|
alle Kanten genau einmal besucht, aber **keine** Eulertour $\Rightarrow$ nicht
|
||
|
|
eulersch.
|
||
|
|
|
||
|
|
Warum nicht eulersch?
|
||
|
|
|
||
|
|
Betrachte Knoten $1$, $deg(1) = 3$
|
||
|
|
|
||
|
|
1) Falls $1$ Startknoten ist, dann kann $1$ nicht Endknoten sein, da es
|
||
|
|
keine nicht benutzte Kante mehr gibt, die zu $1$ hinführt, nachdem $1$
|
||
|
|
2-mal besucht wurde
|
||
|
|
|
||
|
|
2) Falls $1$ nicht Startknoten, dann endet die Tour entweder in $1$ oder
|
||
|
|
eine zu $1$ inzidente Kante wird nicht besucht
|
||
|
|
|
||
|
|
$\Rightarrow$ Falls $G$ eulesch gilt $2 | deg(v), \forall v \in V$
|
||
|
|
|
||
|
|
Diese Bedingung ist nicht nur notwendig, sondern auch hinreichend.
|
||
|
|
|
||
|
|
|
||
|
|
# Satz
|
||
|
|
|
||
|
|
Sei $G=(V,E)$ ein zusammenhängender Graph. Dann ist $G$ eulersch, genau dann,
|
||
|
|
wenn $2 | deg(v), \forall v \in V$ ($deg(v)$ ist gerade).
|
||
|
|
|
||
|
|
|
||
|
|
# Beweis
|
||
|
|
|
||
|
|
"$\Rightarrow$" siehe oben
|
||
|
|
|
||
|
|
"$\Leftarrow$" Sei $G=(V,E)$ ein zusammenhängender Graph mit $2 | deg(v),
|
||
|
|
\forall v \in V$. Wir müssen zeigen, dass $G$ eine Eulertour enthält. Wir
|
||
|
|
konstruieren diese wie folgt:
|
||
|
|
|
||
|
|
* wähle einen beliebigen Knoten $v_0 \in V$ und setzen $W_0 = (v_0)$, $i
|
||
|
|
\leftarrow 0$
|
||
|
|
|
||
|
|
* solange (es gibt noch eine Kante, die in $W_i$ nicht besucht wurde)
|
||
|
|
|
||
|
|
i) wähle Knoten $v_k \in W_i$, der zu einer Kante $\{v_k,u\}$ inzident ist,
|
||
|
|
die noch nicht besucht wurde
|
||
|
|
|
||
|
|
i) konstruiere einen Weg $W' = (v_k, u=u_0,u_1,...,u_s,v_k)$ aus Kanten,
|
||
|
|
die in $W_i$ noch nicht benutzt wurden und der wieder in $v_k$ endet
|
||
|
|
|
||
|
|
i) setze $W_{i+1}$ auf den aus $W_i$ und $W'$ zusammengesetzten Weg, d.h.
|
||
|
|
für $W_i = (v_0,...,v_0)$ setze $W_{i+1} =
|
||
|
|
(v_0,...,v_k,u_0,...,u_s,v_k,v_{k-1},...,v_0)$
|
||
|
|
|
||
|
|
i) setze $i \leftarrow i + 1$
|
||
|
|
|
||
|
|
|
||
|
|
Der Algorithmus ist korrekt, denn
|
||
|
|
|
||
|
|
i) bei Terminierung ist $W_i$ eine Eulertour
|
||
|
|
|
||
|
|
i) Der Weg $W'$ kann immer konstruiert werden, da
|
||
|
|
|
||
|
|
a) Die Anzahl der besuchten Kanten in $W_i$ ist für jeden Knoten gerade. Da
|
||
|
|
$deg(v)$ gerade ist, ist auch die Anzahl der nicht besuchten Kanten pro
|
||
|
|
Knoten gerade
|
||
|
|
|
||
|
|
a) Daher können wir aus jedem besuchten Knoten in $W'$ weiterlaufen, bis
|
||
|
|
wir wieder in $v_k$ landen.
|
||
|
|
|
||
|
|
$$
|
||
|
|
\tag*{$\Box$}
|
||
|
|
$$
|
||
|
|
|
||
|
|
|
||
|
|
**Beispiel**: 
|
||
|
|
|
||
|
|
* starte mit $(1)$
|
||
|
|
* dann $W' = (1,3,2,1)$, $W_1 = (1,3,2,1)$
|
||
|
|
* dann $W' = (2,4,5,2)$, $W_2 = (1,3,2,4,5,2,1)$
|
||
|
|
* dann $W' = (3,5,6,4,3)$
|
||
|
|
|
||
|
|
$\Rightarrow$ $W_3 = (1,3,5,6,4,3,2,4,5,2,1)$ als Eulertour in $G$.
|
||
|
|
|
||
|
|
|
||
|
|
**Laufzeit**: $O(|E|)$
|