cards-deck: 100-199_university::111-120_theoretic_cs::115_graphentheorie date-created: 2024-06-14 04:03:42 date-modified: 2024-07-04 06:55:11

Euler(sche Graphen) | Königsberger Brückenproblem

anchored to 115.00_graphentheorie_anchor builds upon 115.01_grundlagen

Das Problem wurde etwa in 1736 vorgestellt.

Die grundlegende Frage, die bei diesem Problem gestellt wird: Können wir für einen Graphen eine Tour erzeugen/finden, sodass wir jede Kante nur einmal durchlaufen? (Dabei dürfen Knoten mehrfach verwendet werden, also es geht primär um die Kanten!).

(bisschen wie TSP in seiner Idee, aber nur mit anderer Betrachtung)

[!Definition] Eulerkreis

Wann nennen wir einen Graphen Eulerkreis oder Eulerweg? #card

Kreis: Anfang und Endpunkt sind gleich. Weg: Anfang und Endpunkt sind nicht gleich -> also fangen iwo an und hören iwo anders auf.

Sei $G$ ein Graph, dann nennen wir einen Eulerkreis (Eulerweg) in $G$ einen Kreis (oder Weg), der jede Kante genau einmal durchläuft. ^1720112094848

Aus dieser Definition können wir jetzt die Charakteristik von eulersch definieren:

[!Definition] eulersch(er Graph) Wir nennen nun einen Graph eulersch :: wenn er einen Eulerkreis enthält / aufweist! ^1720112094858

[!Tip] Beweiskonzept von $⟺$ Beweisen von Wenn-dann also $⟺$: Werden durch beweisen von beiden Seiten gezeigt: $⟸$, sowie $⟹$

(3) Satz von Euler | eulersche Graphen $⟷$ alle Knoten haben geraden Grad

[!Satz] Es gilt: $G$ ist eulersch $⟺$ alle Knoten von $G$ haben geraden Grad

Wie können wir das beweisen? #card

Sei dafür $G=(V,E)$ ein zusammenhängende Graph.

Beweis $⟹$: ist er eulersch, dann sind die Grade der Knoten gerade: G hat also einen eulerkreis, das heißt, dass jede Kante genau einmal durchlaufen wird (und wir irgendwo anfangen und aufhören) –> wir kommen also in diesen Knoten “hinein und heraus” ( es brauch also zwei Kanten, sonst funktioniert es nicht). Daraus folgt dann: $⟹$ Grad der Knoten ist gerade -> bei allen!

(oder auch): klar, weiß man x) ^1720112094862

[!Satz]

Es gilt: alle Knoten von $G$ haben einen geraden Grad $⟹$ $G$ ist eulersch

Wie beweisen wir das? #card

Beweis $\iff$:

1. Sei jetzt ein Startknoten $v_0\in V$. (Beliebig) (wichtig ist, dass wir wissen, dass auf jeden Fall $>1$ Knoten existieren müssen)
2. Wir wählen jetzt einen Nachbarknoten (also einen Adjacent $v_1$ und markieren diese Kante als verbraucht -> heißt wir können sie anschließend nicht mehr nutzen.
3. wir wiederholen diesen Schritt bis der aktuelle Knoten $v_e$ nur noch gebrauchte Kanten hat ( wir also iwo am Ende angekommen sind). Ferner muss dabei gelten: alle haben geraden Grad! und somit $v_0=v_k$ Wir haben damit keinen validen Pfad erhalten, aber wir können folgern: $$K=⟨v_0,v_1\dots ,v_{k-1},v_0⟩$$ dadurch ist es dann ein Kreis (es kann sein, dass irgendwo im Graph etwa ein Dreieck auftaucht, was beim traversieren nicht richtig durchlaufen wurde –> dadurch fehlt diese Hälfte noch und deswegen haben wir noch keinen Eulerkreis gefunden.) Diesen Restgraphen müssen wir jetzt noch zusammenstellen. Dafür gibts verschiedene Ansätze: Etwa Backtracking, oder einfach nochmal den Graphen nochmal traversieren –> und dann einfach die fehlenden Kanten anbringen / einfügen –> wichtig es muss nicht zusammenhängend sein ( man muss sie nur mergen können).

[!Tip] Im Restgraphen $(V,E\setminus E(K))$ haben alle Knoten einen geraden Grad (per Voraussetzung!)

Wir durchlaufen jetzt K nochmals, wenn ein Knoten $v$ im Graph ( den wir vielleicht “vergessen haben”) unbenutzte Kanten hat. Wir finden jetzt einen neuen Kreis von $v⟶v$ und fügen ihn dann zu $K$ hinzu. Wir durchlaufen nun den neuen Kreis bis zu $v_0$ und dann werden wir save einen Kreis finden können –> da der Restgraph ja einen geraden Grad haben wird / hat. ^1720112094867

Aus dieser Betrachtung können wir jetzt ferner einen Algorithmus bauen bzw. erzeugen, welcher uns in $\mathcal{O}(E)$ bestätigt, ob ein Graph $G$ eulersch ist oder nicht.

Algorithmus zur Bestimmung von eulerschen Graphen

Testen von eulerschen Graphen und bestimmen in $\mathcal{O}(E)$

[!Satz] testen und bestimmten von eulerschen Graphen #card

Sei $G=(V,E)$ ein zusammenhängender Graph. Dann können wir in der Zeit von $\mathcal{O}(E)$ zwei Dinge bestimmen:

1. testen, ob $G$ eulersch ist
2. einen Eulerkreis finden, wenn $G$ eulersch ist. ^1720112094872

Den ersten Punkt “testen, ob $G$ eulersch ist” können wir relativ einfach zeigen / beweisen.

Beweis (1)

Wir haben zuvor in [(3) Satz von Euler eulersche Graphen $longleftrightarrow$ alle Knoten haben geraden Grad](#(3)%20Satz%20von%20Euler%20eulersche%20Graphen%20%20alle%20Knoten%20haben%20geraden%20Grad) beweisen, dass eine Äquivalenz zwischen der Eigenschaft von “eulersch” und geraden Graden eines Graphen $K$ für alle Knoten besteht.

Wir können ferner also beweisen, dass diese Eigenschaft gilt, indem wir jetzt folgend vorgehen: Wir traversieren jeden Knoten und erörten hierbei seinen Grad. Sobald wir einen Grad, welcher ungerade ist, finden, stoppen wir und können mit $FALSE$ antworten. Anderweitig traversieren wir den ganzen Graphen bzw. dessen Knoten und können am Ende darauf schließen, dass er nur Knoten geraden Grades hat $⟹$ eulersch ist!

Beweis (2)

Unter Betrachtung des Beweises für [(3) Satz von Euler eulersche Graphen $longleftrightarrow$ alle Knoten haben geraden Grad](#(3)%20Satz%20von%20Euler%20eulersche%20Graphen%20%20alle%20Knoten%20haben%20geraden%20Grad) können wir das finden in $\mathcal{O}(E)$ bestimmen / definieren. Wir könne den gesamten Algorithmus jetzt in 3 Bereiche aufteilen:

1. finden eines ersten Kreises
2. Prüfen / Finden von weiteren Kreisen
3. Zusammenfügen des Eulerkreises

Finden eines ersten Kreises

Nach diesem Schritt ist es noch nicht garantiert, dass ein Eulerkreis vorliegt, weil wir u.U. auch einfach nur einen Kreis ohne seine “Neben-Arme” gefunden haben!

Ferner möchten wir also folgende Idee umsetzen:

1. Wir nehmen uns einen Startknoten $w\in V$
2. Wir traversieren jetzt zu dem nächsten Nachbarknoten, dessen Kante noch nicht verbraucht wurde und setzen diese Kante als verbraucht - damit wir sie nicht nochmal traversieren.
3. Von diesem neuen Knoten werden wir jetzt wieder einen Nachbarknoten über eine unverbrauchte Kante besuchen und hier ebenfalls wieder die Kante als verbraucht markieren.
4. wiederhole den Vorgang von (2-3), bis wir wieder am Anfang sind. (wichtig ist, dass hierdurch nicht zwingend ein Eulerkreis gefunden werden muss / kann, wenn man etwa ein Dreieck im Graph hat, wie im ursprünglichen Beweis genannt)
5. Es liegt ein erster Kreis vor - welcher nicht zwingend ein Eulerkreis sein muss.

Hierbei wird die Findung eines Eulerkreises beim ersten Durchlauf nicht garantiert, weswegen empfohlen wird, diesen Algorithmus entsprechend zu erweitern, bzw. zu wiederholen, wenn der erste Kreis gefunden wurde / werden konnte:

Finden weiterer Kreise:

Für jeden Knoten $v$ wird jetzt ein Zeiger $curr[v]$ eingeführt, welcher auf den ersten Nachbarn $w$ zeigt, wo die Kante $e=(v,w)$ noch unbenutzt ist. -> Wenn alle inzidenten Kanten zu $v$ benutzt sind - wir also schon überall durchgelaufen sind- wir der Zeiger auf nil gesetzt. $curr[v]=nil$

[!Tip] Priorisierung der nächsten Kante, die als verbraucht genutzt wird

Durch diese eingeführte Variable können wir immer “tracken”, wo sich ein Ausgang dieser befindet - also wo wir dann auf den nächsten Knoten treffen und somit einen Durchlauf durch all seine Nachbarn abgeschlossen haben.

Aber wir lösen damit noch nicht das Problem, dass wir den großen - kompletten - Eulerkreis finden, sondern nach einem Durchlauf vielleicht nur einen Kreis gefunden haben.

Dafür fügen wir jetzt noch eine Variable v.erledigt $\forall v\in V$ ein, die uns dabei hilft zu checken, ob wir alle Kanten eines Graphen gefunden haben.

Sie wird also genutzt, um im gefundenen Kreis $K$ Knoten zu finden, die inzident zu nicht markierten Kanten sind. Denn, wenn $K\ne E(G)$, dann gehen wir mit einem neuen Zeiger $z$ - welcher bei $v_0$ beginnt - durch den Kreis $K$, bis wir den ersten noch nicht erledigten Knoten finden -> und da dann einen weiteren Kreis - von $v_k$ über andere Knoten bis zu $v_k$ zurück - finden können.

Einfügen der neu gefundenen Kreise:

1. Den neu gefundenen Kreis an einem noch nicht erledigten Knoten $v_k$ - also ein Kreis der bei $v_k$ anfängt und bei $v_k$ endet - können wir dann in den ursprünglichen Kreis $K$ hinzufügen.
2. Anschließend werden wir den Zeiger $z$ dann zum nächsten unerledigten Knoten fortbewegen, und wieder den Kreis konstruieren und einfügen.
3. Wiederhole also bis, $\forall v\in V:v.erledigt=true$ bzw $K=E(G)$

der Zeiger $z$ geht im Verlauf durch $K$, bis er wieder beim Startknoten $v_0$ ist. Dabei wird also jede Kante genau $1x$ betrachtet.

Laufzeit des Algorithmus

Wir können aus den einzelnen Operationen jetzt eine gebündelte Laufzeit finden:

[!Definition] Laufzeit zur Bestimmung eines Eulerkreises wie ist sie? #card

Wir müssen durch die Zusatzoperationen diverse Zeitaufwände mit einbeziehen:

• Vorrücken des Zeigers $z$ $\mathcal{O}(E)$
• Aufrechterhaltung des “erledigt”-Flags: $\mathcal{O}(V)$
• Extraaufwand - Konstruktion/ zusammenfügen des Kreises $K$ : $\mathcal{O}(E)$ Es folgt ferner eine Laufzeit von: $$\mathcal{O}(E)$$ ^1720112094877

Bemerkung: Betrag $E$, $V$ in zusammenhängenden Graphen

[!Definition] Größenverhältnis zwischen $E,V$ in zusammenhängenden Graphen #card

In zusammenhängenden Graphen gilt bzgl. der Größenverteilung der Menge von Kanten und Knoten folgend: $$\begin{array}{r}>\mid E\mid \ge \mid V\mid -1\\ >\mathcal{O}(V)\subseteq \mathcal{O}(E)>\end{array}$$ ^1720112094882