---
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) ![Eulerscher Graph](20181121_1-euler.png) ist eulersch, da
$(1,4,3,2,6,4,5,2,1)$ eine Eulertour ist

a) ![Haus vom Nikolaus](20181121_1-nikolaus.png) 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**: ![Doppelter Nikolaus](20181121_1-doublenikolaus.png)

* 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|)$