Eulerlinie und Hamiltonkreis

Aufrufe: 52     Aktiv: vor 2 Wochen

0

Zu folgender Skizze sollen wir die Anzahl der Eulerlinien bzw. Hamiltonkreise angeben. Die Lösung verstehe ich noch nicht ganz...: 

Ecken mit geradem Grad spielen keine Rolle (warum?) und deshalb ersetzen wir diese Ecken durch Kanten und erhalten den rechten Graph.

Und zwar sollen es zwei Möglichkeiten geben: 

- Einmal, dass die Pfade entweder immer im Uhrzeigersinn laufen oder immer gegen dem Uhrzeigersinn. Das habe ich soweit verstanden. 

- Dann soll es noch die Möglichkeit geben, dass der Pfad mind. einmal die Richtung ändert... Das macht für mich aber irgendwie keine Sinn, da wir in der Eulerlinie jede Ecke nur einmal durchlaufen dürfen? Würde der Pfad die Richtung ändern, hätten wir zum Beispiel: (1, 2, 1, 3) Oder was ist damit gemient?

Danke für jede Antwort schonmal :)

 

gefragt vor 2 Wochen
a
anonymouss,
Punkte: 67

 

was suchst Du denn? Eulerkreis oder Hamiltonkreis? Das sind zwei versch. Dinge.

  ─   mikn, vor 2 Wochen

In der Aufgabenstellung wird nach beidem gefragt. Aber es gibt ja nur einen Hamiltonkreis. Mein Problem ist "nur" das festgedruckte bei der Suche nach der Anzahl der Eulerlinien.

  ─   anonymouss, vor 2 Wochen

Bin verwirrt. Du redest von nur einem Hamiltonkreis (woher weiß man das?) aber suchst die Anzahl der Eulerlinien?! Es gibt sehr wohl einen Eulerkreis.

  ─   mikn, vor 2 Wochen

Vielleicht drücke ich mich schlecht aus, sorry :D
Also: Es gibt nur einen Hamiltonkreis, da in der Aufgabe gesagt wird, dass zwei eulersche Linien (bzw. hamiltonsche Kreise) als gleich angesehen werden sollen, wenn sie sich nur durch den Startpunkt oder die Laufrichtung unterscheiden. Einen zweiten bzw. weiteren Hamiltonkreis gibt es somit doch gar nicht?
Und: Mein Problem ist eher, dass fettgedruckte, also warum man die Richtung des Pfades ändern kann im rechten Graph und es trotzdem eine Eulerlinie bleibt. Denn ändert man die Richtung einmal, kommt man wieder bei der Anfangsecke an, was dann keine Eulerlinie mehr ist...

  ─   anonymouss, vor 2 Wochen

Den Rückschluss aus der Aufgabenstellung würde ich nicht ziehen. Es könnte durchaus mehrere versch. H-Kreise geben.
Beim Fettgedruckten bist Du also auf der Suche nach nem Eulerkreis, nicht Hamiltonkreis, wenn ich es recht verstehe. Aber bei einer Eulerlinie wird nicht unbedingt jeder Knoten nur einmal durchlaufen (das wäre beim H-Kreis so). Bin weiterhin verwirrt.

  ─   mikn, vor 2 Wochen

Jetzt bin ich auch verwirrt.. :D Kann man in einer Eulerlinie die Knoten mehrmals durchlaufen? Wenn ja, dann hat sich die Frage geklärt... :D Oh man...
Und: Wie finde ich denn heraus, ob es nicht mehrere Hamiltonkreise gibt? Es gibt doch nur einen, dachte ich..

  ─   anonymouss, vor 2 Wochen
Kommentar schreiben Diese Frage melden
1 Antwort
0

Im Eulerkreis werden alle KANTEN genau einmal durchlaufen, über die Knoten ist nichts gesagt. Beim Hamiltonkreis werden alle KNOTEN genau einmal durchlaufen, über die Kanten ist nichts gesagt.

Einen Eulerkreis gibt es, da jeder Knoten geraden Grad hat. Dafür gibt es Algorithmen (z.B. Hierholzer). Hamiltonkreise sind eine ganz andere Spielklasse, ob es hier einen, oder mehrere, gibt, weiß ich nicht. Ich würde das ausprobieren.

geantwortet vor 2 Wochen
m
mikn
Lehrer/Professor, Punkte: 4.12K
 

Danke:)

  ─   anonymouss, vor 2 Wochen
Kommentar schreiben Diese Antwort melden