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
StartseiteMatheForenGraphentheorieHamiltonscher Graph, wieviele?
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - Hamiltonscher Graph, wieviele?
Hamiltonscher Graph, wieviele? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hamiltonscher Graph, wieviele?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:12 Di 13.12.2011
Autor: studentxyz

Hallo,

laut Skript gibt es [mm] \bruch{(n-1)!}{2} [/mm] hamiltonsche Kreise in Kn.

Also gibt es [mm] \bruch{(4-1)!}{2} [/mm] = 3 hamiltonsche Kreise in K4

Wenn man sich jetzt zu diesem K4:

[Dateianhang nicht öffentlich]

den Knoten links oben als a, rechts oben als b, links unten als c, rechts unten als d vorstellt gibt es meiner Meinung nach diese hamiltonschen Kreise:

abcda
bcdab
cbadc
dabcd
adcba

das sind aber 5, wo liegt der Fehler?





Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
        
Bezug
Hamiltonscher Graph, wieviele?: Antwort
Status: (Antwort) fertig Status 
Datum: 11:21 Di 13.12.2011
Autor: felixf

Moin!

> laut Skript gibt es [mm]\bruch{(n-1)!}{2}[/mm] hamiltonsche Kreise
> in Kn.
>  
> Also gibt es [mm]\bruch{(4-1)!}{2}[/mm] = 3 hamiltonsche Kreise in
> K4
>  
> Wenn man sich jetzt zu diesem K4:
>  
> [Dateianhang nicht öffentlich]
>  
> den Knoten links oben als a, rechts oben als b, links unten
> als c, rechts unten als d vorstellt gibt es meiner Meinung
> nach diese hamiltonschen Kreise:
>  
> abcda
>  bcdab
>  cbadc
>  dabcd
>  adcba
>  
> das sind aber 5, wo liegt der Fehler?

Du hast fuenfmal den gleichen Kreis aufgelistet ;-)

Jeder Kreis kann auf verschiedene Wege beschrieben werden (du hast vier verschiedene Startpunkte und zwei verschiedene Richtungen, womit du acht Beschreibungen finden kannst - fuenf davon hast du bereits). Es geht hier aber um die Anzahl der Kreise, nicht um die Anzahl der Beschreibungen von Kreisen durch geschlossene Wege.

LG Felix


Bezug
                
Bezug
Hamiltonscher Graph, wieviele?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:26 Di 13.12.2011
Autor: studentxyz


> Du hast fuenfmal den gleichen Kreis aufgelistet ;-)
>  
> Jeder Kreis kann auf verschiedene Wege beschrieben werden
> (du hast vier verschiedene Startpunkte und zwei
> verschiedene Richtungen, womit du acht Beschreibungen
> finden kannst - fuenf davon hast du bereits). Es geht hier
> aber um die Anzahl der Kreise, nicht um die Anzahl der
> Beschreibungen von Kreisen durch geschlossene Wege.

Ok, dann habe ich keine Idee wie die anderen beiden Kreise aussehen müssten.
Was bleibt einem denn übrig ausser die Reihenfolge der Knoten zu variieren?


Bezug
                        
Bezug
Hamiltonscher Graph, wieviele?: Antwort
Status: (Antwort) fertig Status 
Datum: 12:20 Di 13.12.2011
Autor: felixf

Moin!

> > Du hast fuenfmal den gleichen Kreis aufgelistet ;-)
>  >  
> > Jeder Kreis kann auf verschiedene Wege beschrieben werden
> > (du hast vier verschiedene Startpunkte und zwei
> > verschiedene Richtungen, womit du acht Beschreibungen
> > finden kannst - fuenf davon hast du bereits). Es geht hier
> > aber um die Anzahl der Kreise, nicht um die Anzahl der
> > Beschreibungen von Kreisen durch geschlossene Wege.
>  
> Ok, dann habe ich keine Idee wie die anderen beiden Kreise
> aussehen müssten.
>  Was bleibt einem denn übrig ausser die Reihenfolge der
> Knoten zu variieren?

Der offensichtlichste Kreis ist doch abdca: einmal aussen um das Quadrat herum.

LG Felix


Bezug
                                
Bezug
Hamiltonscher Graph, wieviele?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:34 Di 13.12.2011
Autor: studentxyz

Das ist richtig, wie oben beschrieben soll K4 aber 3 hamiltonsche Kreise enthalten.

Bezug
                                        
Bezug
Hamiltonscher Graph, wieviele?: Antwort
Status: (Antwort) fertig Status 
Datum: 13:39 Di 13.12.2011
Autor: wieschoo

Lauf mal über
ac ....

Bezug
                                                
Bezug
Hamiltonscher Graph, wieviele?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:02 Di 13.12.2011
Autor: studentxyz

?

Bezug
                                                        
Bezug
Hamiltonscher Graph, wieviele?: Antwort
Status: (Antwort) fertig Status 
Datum: 15:19 Di 13.12.2011
Autor: Al-Chwarizmi


> [mm] $\mbox{\Huge{?}}$ [/mm]


Na, du bist ja ziemlich kurz angebunden.

Um einen Hamiltonweg zu beschreiben, kannst du
immer z.B. beim Punkt a starten. Von da aus kannst
du entweder zu b, zu c oder zu d weiterschreiten:

ab...
ac...
ad...

Dann hast du nochmal die Wahl, ob du z.B.  den
Anfang  ab...  mit c oder mit d fortsetzen willst:

abc...   oder abd...

Der Rest ist dann aber jedenfalls eindeutig festgelegt:

abcda  oder abdca

Nun machst du dies für die anderen möglichen Anfänge
ebenfalls, musst dann aber noch darauf achten, dass
jeweils 2 der notierten Wege nur als einer gelten, weil
sie denselben Weg nur in umgekehrter Durchlaufrichtung
beschreiben. Daher kommt auch der Nenner 2 in der Formel.

LG    Al-Chw.




Bezug
                                                                
Bezug
Hamiltonscher Graph, wieviele?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:14 Mi 14.12.2011
Autor: studentxyz

Das werden ja dann 3 Kreise pro Startpunkt, also 12?


Warum benutzt du das Wort Weg in zusammenhang mit Hamiltonkreis?
Im Skript ist ein Weg(nicht zusammenhängend) etwas anders als ein Kreis.

Die Definition bei mir im Skript für Hamiltonkreis:

Ein Kreis in einem Graphen G = (V,E)
heißt Hamiltonkreis, wenn er jeden Knoten von G (genau einmal) enthält. Ein Graph wird Hamiltonsch genannt, wenn er einen Hamiltonkreis enthält.


Bezug
                                                                        
Bezug
Hamiltonscher Graph, wieviele?: Antwort
Status: (Antwort) fertig Status 
Datum: 17:39 Mi 14.12.2011
Autor: Al-Chwarizmi


> Das werden ja dann 3 Kreise pro Startpunkt, also 12?

Nein, einen "Startpunkt" habe ich nur benützt, um die
Kreise zu beschreiben. Die Kreise

    abcda, bcdab, cdabc, dabcd,
    adcba, badcb, cbadc, dcbad

sind aber als identisch zu betrachten. Auch auf einem
(geometrischen) Kreis in der Ebene benützen wir ja
einen "Startpunkt" nur etwa zum Zweck einer Parametri-
sierung, also auch Beschreibung der Durchlaufung.
  

> Warum benutzt du das Wort Weg in zusammenhang mit
> Hamiltonkreis?

>  Im Skript ist ein Weg(nicht zusammenhängend) etwas anders
> als ein Kreis.

Ein Kreis ist nur ein Spezialfall eines Weges:   []Pfade, Zyklen und Kreise

> Die Definition bei mir im Skript für Hamiltonkreis:
>  
> Ein Kreis in einem Graphen G = (V,E)
>  heißt Hamiltonkreis, wenn er jeden Knoten von G (genau
> einmal) enthält. Ein Graph wird Hamiltonsch genannt, wenn
> er einen Hamiltonkreis enthält.

LG   Al-Chw.


Bezug
                                                                                
Bezug
Hamiltonscher Graph, wieviele?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:17 Di 20.12.2011
Autor: studentxyz

Danke für die Hilfe, irgendwann ist mir dann ein Licht aufgegangen.

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


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