TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 304

Man untersuche, ob der Graph $G_{14}$ eine Eulersche Linie besitzt, und bestimme gegebenenfalls eine.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

Eulersche Linie

Euler'sche Linie

Eine Kantenfolge in einem (gerichteten oder ungerichteten) Graphen $G$ heißt Euler'sche Linie, wenn sie jeden Knoten und jede Kante enthält, und zwar jede Kante genau einmal. Ein Graph wird Euler'scher Graph genannt, wenn er eine Euler'sche Linie besitzt.

Es gibt zwei Arten von Euler'schen Linien in einen Graphen, eine geschlossene Euler'sche Linie, wo Start- und Endknoten überein stimmen, und eine offene Euler'sche Linie, wo diese veschieden sind.

Bei einen ungerichteten Graphen gilt:

• Eine geschlossene Euler'sche Linie gibt es in einem Graphen ungerichteten $G$, wenn $G$ zusammenhängend ist und alle Knotengrade $d(\omega )$ mit $\omega \in V(G)$ gerade sind.

• Eine offene Euler'sche Linie gibt es in einem Graphen ungerichteten $G$, wenn $G$ zusammenhängend ist und mit der Ausnahme von zwei Knoten $\omega _{1},\omega _{2}\in V(G)$ mit ungeradem Knotengrad alle übrigen Knotengrade $d(\omega )$ mit $\omega \in V(G)\backslash \{\omega _{1},\omega _{2}\}$ gerade sind.

Bei einen gerichteten Graphen gilt:

• Eine geschlossene Euler'sche Linie gibt es in einem Graphen gerichteten $G$, wenn $G$ schwach zusammenhängend ist und für alle Knoten $\omega$ mit $\omega \in V(G)$ der Hin- und Weggrad gleich sind: $d^{+}(\omega )=d^{-}(\omega )$

• Eine offene Euler'sche Linie gibt es in einem Graphen gerichteten $G$, wenn $G$ schwach zusammenhängend ist und mit der Ausnahme von zwei Knoten $v_{1},v_{2}\in V(G)$, für die $d^{+}(\omega _{1})=d^{-}(\omega _{1})+1$ und $d^{+}(\omega _{2})=d^{-}(\omega _{2})-1$ gilt, für alle übringen Knoten der Hin- und Weggrad $\omega \in V(G)\backslash \{\omega _{1},\omega _{2}\}$ gleich sind: $d^{+}(\omega )=d^{-}(\omega )$

Lösungsvorschlag von Gamer199

Zuerst müssen die Knotengrade bestimmt werden.

Man erkennt es gibt nur gerade Knotengrade, die Ausnahme sind genau 2 Knoten mit einem ungeraden Knotengrad. Daraus erkennt man es gibt eine offene Euler'sche Linie.

Um diese nun zu Konstruieren muss man jede Kante einmal verwenden und jeden Knoten erreichen. Man beginnt bei einem Knoten mit einem ungeraden Knotengrad und hört bei dem zweiten Knoten mit ungeradem Knotengrad wieder auf.

Ein Beispiel für eine Euler'sche Linie ist in folgender Grafik zu finden, wenn es eine Euler'sche Linie gibt, kann man auch viele weitere Euler'sche Linien finden.

$1\Rightarrow 2\Rightarrow 3\Rightarrow 1\Rightarrow 4\Rightarrow 3\Rightarrow 5\Rightarrow 6\Rightarrow 7\Rightarrow 8\Rightarrow 9\Rightarrow 10\Rightarrow 11\Rightarrow 9\Rightarrow 12\Rightarrow 11\Rightarrow 13\Rightarrow 12\Rightarrow 7\Rightarrow 13\Rightarrow 10\Rightarrow 14\Rightarrow 13\Rightarrow 6\Rightarrow 14\Rightarrow 15\Rightarrow 2\Rightarrow 4\Rightarrow 15\Rightarrow 16\Rightarrow 14\Rightarrow 5\Rightarrow 16\Rightarrow 4$