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 Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

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
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. Informatik • Physik • Technik • Biologie • Chemie
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.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]