Tiefensuche/DFS und Isomorphie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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?
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:30 Mo 06.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
