Hamiltonkreis Eulertour < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Jeder Hamiltonkreis ist eine Eulertour.
Moeglich Antworten:
- Ja
- Nein |
Hallo,
die Antwort lautet "nein".
Ich bin aber der Meinung, das die Antwort "Ja" lauten muesste.
Begruendung:
Nicht jeder Hamiltonkreis in einem bel. Graphen G ist eine Eulertour, weil Hamiltonkreise auch in Graphen mit ungeradem Grad der Knoten existieren koennen. Beispiel ein Rechteck (R): Alle Knoten haben ungeraden grad (3), R hat mehrere Hamiltonkreise aber keine Eulertour.
Wenn es also heissen wuerde:
Jeder Hamiltonkreis in einem Graphen G ist auch eine Eulertour,
so waere die Antwort "nein".
Die Frage lautet jedoch wie oben. Das wuerde bedeuten der Ausgangsgraph besteht aus einem Hamiltonkreis, dieser aber erfuellt die Voraussetzung fuer eine Eulertour. Somit muesste die Richtige Antwort "Ja" lauten.
Wo ist der Haken?
Gruss
mathlooser
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:03 Fr 21.03.2014 | | Autor: | Ladon |
Hallo,
ich weiß nicht, ob du noch an einer Antwort interessiert bist. Das Bild von einem Graphen im Anhang verdeutlicht noch mal, dass nicht jeder Hamilton-Kreis eine Eulertour ist, da die Definition gerade besagt, dass ein Elementarkreis in einem Graphen G, der alle Knoten von G durchläuft, Hamiltonkreis heißt. Demgegenüber heißt ein Kantenzug, der jede Kante eines Graphen G enthält, Eulersche Linie (oder Eulertour) von G. Der Hamiltonkreis muss aber nicht alle Kanten enthalten!
Ich weiß nicht, ob ich damit deine Frage
> Wenn es also heissen wuerde:
>
> Jeder Hamiltonkreis in einem Graphen G ist auch eine
> Eulertour,
>
> so waere die Antwort "nein".
>
> Die Frage lautet jedoch wie oben. Das wuerde bedeuten der
> Ausgangsgraph besteht aus einem Hamiltonkreis, dieser aber
> erfuellt die Voraussetzung fuer eine Eulertour. Somit
> muesste die Richtige Antwort "Ja" lauten.
>
> Wo ist der Haken?
beantworte, aber dass der Hamiltonkreis in einem Graphen G liegen muss, sollte aufgrund der Definition klar sein. 
MfG Ladon
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Hallo Ladon,
vielen Dank, dass du dich noch meiner Frage angenommen hast.
Der Unterschied zwischen einer Eulertour und einem Hamiltonkreis war mir klar, trotzdem danke fuer deine ausfuehrliche und anschauliche Antwort.
Ich hatte nur Probleme mir der Formulierung der Frage.
Wenn es klar ist, dass jeder "Hamiltonkreis in einem Graphen" gemeint ist, schliesst das aber ja nicht die Tatsache aus, dass es sich bei dem Graphen um einen Hamiltonkreis handelt.
Bsp:
Nehmen wir an wir haben einen Graphen, der aus einem Hamiltonkreis besteht: z.B. ein Rechteck.
Dann handelt es sich immer auch um eine Eulertour, weil wie du bereits geschrieben hast eben alle Kanten durchlaufen werden und alle Knoten bis auf den n-1 sten Knoten nur genau einmal "beruehrt" werden.
Es ist also ausschlaggebend ob es sich bei dem Hamiltonkreis - in einem Graphen - um einen echten Teilgraphen handelt oder nicht.
Echter Teilgraph => Die Aussage stimmt nicht.
Hamiltonkreis = Graph => Die Aussage stimmt.
Die Formulierung
Jeder Hamiltonkreis ist eine Eulertour ist also nicht eindeutig. Oder uebersehe ich etwas?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:48 So 23.03.2014 | | Autor: | Ladon |
Hallo,
ich verstehe, was du meinst. Diese Problematik, die du aufzeigst, hast du z.B. nicht, wenn du die umgekehrte Implikation betrachtest:
Jede Eulertour ist Hamiltonkreis.
Z.B. findest du bei unten stehenden Graphen eine Eulertour a-b-c-c-d, die garantiert kein Hamilton-Kreis ist und wo der Graph und die Eulertour identisch sind.
Ich kann mir nur denken, dass die Aufgabensteller bei der Beantwortung von
"Richtig oder Falsch? Jeder Hamiltonkreis ist Eulertour."
mit falsch davon ausgehen, dass bei der Definition ein Hamiltonkreis als Elementarkreis in einem Graphen G definiert wird, der alle Knoten von G durchläuft und insbesondere nicht mit dem Graphen G identisch sein muss.
Einen Hamiltonkreis aber ohne gegebenen Graphen zu betrachten bzw. nur für den Spezialfall Graph = Hamiltonkreis macht wohl keinen Sinn.
Allerdings muss ich dir z.T. recht geben, dass man die Aufgabe evtl. etwas genauer oder eindeutiger formulieren könnte. Soweit meine (vielleicht unbefriedigende) Antwort. 
MfG Ladon
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
|
