Kategorie:Eulersche Linie

Euler'sche Linie[Bearbeiten | Quelltext bearbeiten]

Eine Kantenfolge in einem (gerichteten oder ungerichteten) Graphen ${\displaystyle 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 ${\displaystyle G}$, wenn ${\displaystyle G}$ zusammenhängend ist und alle Knotengrade ${\displaystyle d(\omega )}$ mit ${\displaystyle \omega \in V(G)}$ gerade sind.

• Eine offene Euler'sche Linie gibt es in einem Graphen ungerichteten ${\displaystyle G}$, wenn ${\displaystyle G}$ zusammenhängend ist und mit der Ausnahme von zwei Knoten ${\displaystyle \omega _{1},\omega _{2}\in V(G)}$ mit ungeradem Knotengrad alle übrigen Knotengrade ${\displaystyle d(\omega )}$ mit ${\displaystyle \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 ${\displaystyle G}$, wenn ${\displaystyle G}$ schwach zusammenhängend ist und für alle Knoten ${\displaystyle \omega }$ mit ${\displaystyle \omega \in V(G)}$ der Hin- und Weggrad gleich sind: ${\displaystyle d^{+}(\omega )=d^{-}(\omega )}$

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