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
StartseiteMatheForenGraphentheorieTiefensuche/DFS und Isomorphie
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Tiefensuche/DFS und Isomorphie
Tiefensuche/DFS und Isomorphie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Tiefensuche/DFS und Isomorphie: Tipp oder idee
Status: (Frage) beantwortet Status 
Datum: 14:23 Sa 04.10.2008
Autor: Oui

Aufgabe
Gegeben ist der 3-dimensionalen Wuerfelgraph [mm] Q_{3} [/mm] = (V, E) wobei jeder Knoten (i, j, k)  mit der Zahl i + 2j + 4k nummeriert ist.

            
c) Durch Anderung des Startknotens und/oder der Reihenfolge der Nachbarn in der Adjazenzliste kann bei DFS ein Baum entstehen, der nicht isomorph zum DFS-Baum mit dem Startpunkt 0 ist. Wie sieht dieser nichtisomorphe Baum aus?
Woran erkennen Sie die Nichtisomorphie?


Nun ich habe die adjazentslist erstellt und auch den den entstehenden Baum durch tiefensuche erstellt.

Jedoch wenn ich einen andern startpunkt waehle wird der Aufspannende Baum wieder isomorph zu dem Baum mit dem starpunkt 0, denn beides sind einfache Wege. Die struktur bleibt erhalten. nur die benennung ist anders. mir ist nicht ganz klar wie die aussage aus der aufgabe wahr sein soll.

ich bin dankbar fuer jeden Tipp. danke im voraus

oui




______
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.


        
Bezug
Tiefensuche/DFS und Isomorphie: Antwort
Status: (Antwort) fertig Status 
Datum: 14:39 Sa 04.10.2008
Autor: Zorba

Ich kenn mich da überhaupt nicht aus, aber die Aufgabe ist, einen! Startknoten zu finden unter allen Knoten, so dass der Graph nichtisomorph ist. Hast du denn alle Knoten mal durchprobiert?
Wie sieht dein Graph aus?

Bezug
                
Bezug
Tiefensuche/DFS und Isomorphie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 15:36 Sa 04.10.2008
Autor: Oui

Nun wenn man sich den [mm] Q_{3} [/mm]  mal auf papier aufgezeinet hat sieht man, das es einen hamiltonischen kreis gibt.

und es ist unwichtig wo man anfaengt man erhaelt immer einen weg der laenge |V|-1 = 7.

der baum wird immer ein weg.

also ich weiss nicht ganz wie ich das dann zeigen soll.  selbst durch ausprobieren aller knoten (es sind 8 ) komme ich immer auf einen weg der isomorph zu dem mit dem startpunkt 0 ist.

kann mir jemand vielleicht noch einen tipp geben

danke

oui

Bezug
                        
Bezug
Tiefensuche/DFS und Isomorphie: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:30 Mo 06.10.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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