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
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Hamiltonkreis
Hamiltonkreis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hamiltonkreis: Hamiltontour und Eulferpfad
Status: (Frage) beantwortet Status 
Datum: 21:03 Mo 09.02.2015
Autor: Mopsi

Aufgabe
(b) Welche besitzen einen offenen Euler-Pfad?
(c) Welche besitzen eine Euler-Tour?
(d) Welche besitzen eine Hamilton-Tour?

Die Graphen:
http://www11.pic-upload.de/09.02.15/p8d654e4c52y.png




Hallo :)

zu b)
Ein Graph besitzt einen offenen Eulferpfad, falls alle bis auf zwei Ecken ungeraden Grad haben.
Das wäre dann nur bei G1 der Fall.

zu c)
Ein Graph besitzt eine Eulertour, falls alle Ecken geraden Grad haben.
Das müsste dann bei G2,G3,G4 der Fall sein. Denn alle haben folgende Gradfolge (2,2,2,2,2,2,2,2,4,4,4,4).

zu d)
Hier bin ich ehrlich überfragt, ich habs jetzt einfach mal bei allen ausprobiert, aber finde nichts. Nun ist das ja kein Beweis dafür, dass es keinen gibt. Habt ihr irgendwelche Tricks oder Herangehensweisen dafür?
Vielleicht kann man ja durch bestimmte Gradfolgen ausschließen, dass es eine Hamiltontour gibt.

Vielen Dank für jede Hilfe :)

        
Bezug
Hamiltonkreis: Antwort
Status: (Antwort) fertig Status 
Datum: 11:06 Di 10.02.2015
Autor: MacMath


> (b) Welche besitzen einen offenen Euler-Pfad?
>  (c) Welche besitzen eine Euler-Tour?
>  (d) Welche besitzen eine Hamilton-Tour?
>  
> Die Graphen:
>  http://www11.pic-upload.de/09.02.15/p8d654e4c52y.png
>  
>
>
> Hallo :)
>  
> zu b)
>  Ein Graph besitzt einen offenen Eulferpfad, falls alle bis
> auf zwei Ecken ungeraden Grad haben.
>  Das wäre dann nur bei G1 der Fall.

Ich vermute du hast dich hier nur verschrieben, oder?

> zu c)
>  Ein Graph besitzt eine Eulertour, falls alle Ecken geraden
> Grad haben.
>  Das müsste dann bei G2,G3,G4 der Fall sein. Denn alle
> haben folgende Gradfolge (2,2,2,2,2,2,2,2,4,4,4,4).

Ich stimme zu.

> zu d)
>  Hier bin ich ehrlich überfragt, ich habs jetzt einfach
> mal bei allen ausprobiert, aber finde nichts. Nun ist das
> ja kein Beweis dafür, dass es keinen gibt. Habt ihr
> irgendwelche Tricks oder Herangehensweisen dafür?
>  Vielleicht kann man ja durch bestimmte Gradfolgen
> ausschließen, dass es eine Hamiltontour gibt.

Es gibt ein paar Sätze zu notwendigen Kriterien. Welche kennst du?
Was kann man über Ecken vom Grad 2 und ihre inzidenten Kanten sagen?
Damit wird das Problem schon viel kleiner ;)

> Vielen Dank für jede Hilfe :)


Bezug
                
Bezug
Hamiltonkreis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:33 Di 10.02.2015
Autor: Mopsi

[mm]K_{n,m}[/mm]> > zu b)
> > Ein Graph besitzt einen offenen Eulferpfad, falls alle
> bis
> > auf zwei Ecken ungeraden Grad haben.
> > Das wäre dann nur bei G1 der Fall.

>

> Ich vermute du hast dich hier nur verschrieben, oder?

Ja, ich meine natürlich geraden Grad haben. :P

> > zu d)
> > Hier bin ich ehrlich überfragt, ich habs jetzt einfach
> > mal bei allen ausprobiert, aber finde nichts. Nun ist das
> > ja kein Beweis dafür, dass es keinen gibt. Habt ihr
> > irgendwelche Tricks oder Herangehensweisen dafür?
> > Vielleicht kann man ja durch bestimmte Gradfolgen
> > ausschließen, dass es eine Hamiltontour gibt.

>

> Es gibt ein paar Sätze zu notwendigen Kriterien. Welche
> kennst du?

Im Skript habe ich jetzt nur das gefunden: Während [mm] K_{n,m} nach Satz [/mm] 3.8 genau dann eine Euler-Tour besitzt, wenn sowohl m als auch n gerade ist, hat [mm] K_{n,m} [/mm] genau dann einen Hamiltonkreis, wenn m mit n übereinstimmt. Ein Hamilton-Pfad existiert auch für den Fall, dass sich m und n um 1 unterscheiden.

Und was genau meinen die jetzt mit [mm] K_{n,m}? [/mm] In Satz 3.8 steht nur, dass alle Ecken geraden Grad haben müssen.

> Was kann man über Ecken vom Grad 2 und ihre inzidenten
> Kanten sagen?

Ich weiß es leider nicht :( Kannst du es mir verraten?

Bezug
                        
Bezug
Hamiltonkreis: Antwort
Status: (Antwort) fertig Status 
Datum: 12:33 Di 10.02.2015
Autor: MacMath


> Im Skript habe ich jetzt nur das gefunden: Während
> [mm]K_{n,m} nach Satz[/mm] 3.8 genau dann eine Euler-Tour besitzt,
> wenn sowohl m als auch n gerade ist, hat [mm]K_{n,m}[/mm] genau
> dann einen Hamiltonkreis, wenn m mit n übereinstimmt. Ein
> Hamilton-Pfad existiert auch für den Fall, dass sich m
> und n um 1 unterscheiden.
>  
> Und was genau meinen die jetzt mit [mm]K_{n,m}?[/mm] In Satz 3.8
> steht nur, dass alle Ecken geraden Grad haben müssen.

[mm]K_{n,m}?[/mm] ist der vollständige bipartite Graph, wobei eine Partition m, die andere n Ecken hat. Das nützt hier nichts.

> > Was kann man über Ecken vom Grad 2 und ihre inzidenten
>  > Kanten sagen?

>  Ich weiß es leider nicht :( Kannst du es mir verraten?

Nehmen wir an, eine Ecke x hat Grad zwei:

a - x - b (wobei uns die anderen Nachbarn von a und b nicht interessieren).
Dann muss doch jeder Hamiltonkreis (falls es einen gibt) das ganze Wegstück a-x-b enthalten, da wir sonst x nicht mitnehmen.
Damit kann man hier schon viel erreichen.

Bezug
                                
Bezug
Hamiltonkreis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:51 Di 10.02.2015
Autor: Mopsi


> a - x - b (wobei uns die anderen Nachbarn von a und b nicht
> interessieren).
> Dann muss doch jeder Hamiltonkreis (falls es einen gibt)
> das ganze Wegstück a-x-b enthalten, da wir sonst x nicht
> mitnehmen.
> Damit kann man hier schon viel erreichen.

Ich soll mir nun also alle Ecken x mit Grad 2 ansehen und schauen, ob das Wegstück a-x-b im Kreis enthalten ist.

Also bei G1 habe ich mal die Ecke ganz oben links ausgewählt. Schaue ich mir das Wegstück an fällt mir auf das die Ecke ganz oben rechts gar nicht mehr erreicht werden kann, also besitzt G1 keine Hamiltontour? Jedoch einen Hamiltonweg, man kann ja einfach außen rumgehen, oder?

Bei G2 und G3 habe ich eine Hamiltontour gefunden.

Bei G4 besteht das selbe Problem, wie bei G1, also keine Hamiltontour in G4.

​Richtig?

Bezug
                                        
Bezug
Hamiltonkreis: Antwort
Status: (Antwort) fertig Status 
Datum: 13:02 Di 10.02.2015
Autor: MacMath

Prima!

Bezug
                                                
Bezug
Hamiltonkreis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:23 Di 10.02.2015
Autor: Mopsi


> Prima!

Yuhuuuu :) Danke MacMath! :)

Eine letzte Frage zu dem Thema habe ich noch. Der Aufgabenteil a) lautet: Welche der Graphen sind isomorph zueinander.

Nun habe ich da schon rumprobiert, aber noch immer meine Probleme.

Also eine Invariante ist ja die Kantenanzahl, nun hat G1 13 und die anderen alle 16 Kanten, also können wir G1 ganz ausschließen. Die restlichen Graphen haben aber auch dieselbe Gradfolge :/ Die letzte Invariante, die ich kenne sind Anzahl der Vielecke.

Hilft mir das hier weiter?
Wie soll ich genau vorgehen? Alle möglichen Vielecke suchen? Das dauert doch und wenn die so überkreuz gehen die Kanten dann kann mir das oft nicht richtig vorstellen, wie viele Ecken da jetzt zusammenhängen.

​Ich komme zum Beispiel bei G4 auf vier Vierecke, bei G3 und G2 nur auf drei. Also kann G4 auch ausgeschlossen werden?

Bezug
                                                        
Bezug
Hamiltonkreis: Antwort
Status: (Antwort) fertig Status 
Datum: 14:58 Di 10.02.2015
Autor: MacMath

Invariant unter isomorphen Graphen ist eigentlich fast alles. Die Anzahl der Wege einer festen Länge, Durchmesser...alles was nicht von der Darstellung (zB Einbettung in der Ebene) abhängt.

Wenn du dich nicht verzählt hat, hast du ein passendes Argument gefunden.

Um zu zeigen, dass zwei Graphen isomorph sind, musst du einen Isomorphismus angeben.

G1 fliegt wegen eigener Kantenzahl raus. gut.

G3 ist nicht isomorph zu G4, denn in G3 gibt es 4 Kanten, deren beide inzidenten Ecken Grad 2 haben. Das gibt es in G4 nur 2mal.

In G2 gibt es das ebenfalls 4mal. Ist also G2 isomorph zu G3?

Beide haben (gleiche Gradfolge) jeweils 4 Ecken vom Grad 4. In G3 gibt es einen 4-Kreis durch diese Ecken. In G2 nicht.

Oder anders. Wir betrachten jeweils den durch diese 4 Ecken induzierten Teilgraphen. Der ist in G2 bipartit, in G3 nicht.

Bezug
                                                                
Bezug
Hamiltonkreis: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:50 Di 10.02.2015
Autor: Mopsi

Toll erklärt, danke MacMath :)
Das Prüfen auf Bipartitheit ist ein toller Trick (y)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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