notes/school/di-ma/20181121_1-eulertouren.md

title	date
Eulertouren	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|)