matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieHamiltonkreis Eulertour
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Graphentheorie" - Hamiltonkreis Eulertour
Hamiltonkreis Eulertour < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hamiltonkreis Eulertour: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:02 Mi 12.03.2014
Autor: mathlooser

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

        
Bezug
Hamiltonkreis Eulertour: Antwort
Status: (Antwort) fertig Status 
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]
Bezug
                
Bezug
Hamiltonkreis Eulertour: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:27 Sa 22.03.2014
Autor: mathlooser

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?

Bezug
                        
Bezug
Hamiltonkreis Eulertour: Antwort
Status: (Antwort) fertig Status 
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]
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]