| Autor |
Beitrag |
    
Sabile (Sabile)
Junior Mitglied
Benutzername: Sabile
Nummer des Beitrags: 7
Registriert: 12-2003
| | Veröffentlicht am Mittwoch, den 21. Januar, 2004 - 19:43: | 
|
HAT EINER VILEICHT EINE AHNUNG WIE ICH DAS LÖSEN KAN ??
Geben Sie einen konkreten Graphen an, so dass
zwei verschiedene Adjazenzlistendarstellungen (d.h. verschieden bzgl. der Reihenfolge
in den Listen) zu nichtisomorphen DFS{Baumen führt. Zeigen Sie das analoge Ergebnis
für BFS{Bäume. |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 224
Registriert: 10-2001
| | Veröffentlicht am Donnerstag, den 22. Januar, 2004 - 11:00: |
|
Hmpf, erstmal mußt du das Latein ins Deutsche übersetzen, dann wirds einfach.
nichtisomorph
- meint, die hängen in keinster weise zusammen und man kommt von Baum 1 nicht zu Baum 2 (oder umgekehrt)
DFS - DepthFirstSearch
BFS - BroadFirstSearch
- sind verschiedene Verfahren um durch den Graphen durchzuwandern
- da solltest Du mal in diversen Algorithmenbüchern nachlesen (zum Empfehlen Corman, Leiserson "Introduction to Algorithms")
Adjazenzlistendarstellung
- ist nichts weiter als eine Speichermatrix, in der die Verbindung der Knoten eines Graphen gespeichert sind
Bsp:
....K1 K2
K1 1 1
K2 1 0
- heißt:
* K1 zeigt auf sich selbst und K2
* K2 zeigt nur auf K1
Zurück zur Aufgabe:
Soll also heißen, Dein Graph enthält eine KnotenMenge A und eine Menge B, welche keine Verbindung zueinander haben.
Am einfachsten wäre ein Graph mit 2 Knoten, welche keine Verbindung haben.
Dann wendest Du das DFS-Verfahren auf Menge A und B an und zeigst das diese nicht zusammenhängen (das selbe mit dem BFS)
Dann schreibst Du noch die Beziehungen als Adjazenzmatrix auf und Deine Aufgabe ist gelöst.
Cu Onkel Murray
|
Sabile (Sabile)
Junior Mitglied
Benutzername: Sabile
Nummer des Beitrags: 8
Registriert: 12-2003
| | Veröffentlicht am Freitag, den 23. Januar, 2004 - 11:23: |
|
hi nochmals ich verstehe immer noch nicht genau wie ich den Graphen wählen muss , praktich einen mit 2 Knoten die nicht zusammenhängen ..wie kan das den ausziehen  |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 225
Registriert: 10-2001
| | Veröffentlicht am Samstag, den 24. Januar, 2004 - 15:08: |
|
Hallo Sabile,
scheint so als hätte ich erstmal einen Denkfehler. Ich hab sicherheitshalber nochmal nach der Defintion von "isomorph" - grob bedeutet das, das Zwei graphen dann isomorph sind, wenn sie ineinader überführt werden können.
Soll heißen, daß die zwei Graphen die gleiche Anzahl Knoten mit der gleichen Anzahl Kanten pro Knoten haben.
Kompliztiert ausgedrückt gibt es eine bijektive Funktion mit der jeder Knoten von G1 in G2 überführbar ist und umgekehrt.
Was Dein Problem natürlich ungleich schwerer macht und dir mit dem letzen "Mist" kaum geholfen ist - entschuldige.
Also erstmal eine Adjazenzliste von einem einfachen Graphen:
1 => 2
2 => /
In diesem Graph zeigt Knoten 1 auf 2 und 2 auf keinen Knoten. Der DFS-Algorithmus beginnt immer mit dem ersten Knoten (bitte selbst nachschauen, ist zu aufwendig zu erklären) und sieht für obiges Beispiel so aus:
1 (1/4), 2 (2/3)
Nun verdreht man die Reihenfolge (wie oben gewünscht)
2 => /
1 => 2
Und bestimmt nochmal neu den DFS Baum.
2 (1/2), 1 (3/4)
Nach meinem Verständnis sind das jetzt zwei nichtisomporphe DFS-Bäume.
Onkel Murray
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 227
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 27. Januar, 2004 - 06:57: |
|
Hallo Sabile,
irgendwie hat mich das Problem nicht losgelassen, jetzt habe ich wie es scheint eine Lösung.
Zunächsteinmal nehmen wir als Voraussetzung nur ungerichtete Graphen, denn nur so funktioniert ein BFS immer.
Dann möchte ich gerne das Wort "symmetrischer Graph" definieren - es gibt sicher einen anderen Namen in der Fachsprache dafuer, aber ich definiere es mir ja :-).
Def.: Ein symmetrischer Graph ist ein Graph, bei dem die Anzahl der Kanten an jedem Knoten gleich ist.
Bsp.: Einen symmetrischen Graph mit 2 Kanten kann man sich wie einen Kreis vorstellen auf welchem die Knoten liegen und verbunden sind.
Adjazenzliste (N=4):
1 => 2,4
2 => 1,3
3 => 2,4
4 => 1,3
Bsp.2: Jeder Knoten ist mit jedem Knoten verbunden.
Adjazenzliste (N=4):
1 => 2,3,4
2 => 1,3,4
3 => 1,2,4
4 => 1,2,3
Alle symetrischen Graphen sind bezueglich (Deiner Aufgabenstellung) BFS-Baeumen und DFS-Baeumen bei Vertauschung der Reihenfolge in der Adjazenzliste isomorph.
D.h. wenn man den BFS oder DFS ansetzt, kommt man auf die gleiche Nummerierung der Knoten.
Notiz: Es scheint auch ersichtlich, da ja alle Knoten "gleich" sind.
Bsp.:
Adjazenzliste (N=3)
1 => 2,3
2 => 1,3
3 => 1,2
BFS: 1 (0), 2 (1), 3 (1)
DFS: 1 (1/6), 2 (2/3), 3 (4/5)
Adjazenzliste (N=3)
3 => 1,2
1 => 2,3
2 => 1,3
BFS: 3 (0), 1 (1), 2 (1)
DFS: 3 (1/6), 1 (2/3), 2 (4/5)
Notiz: Die Zahlen in den Klammern bedeuten die Nummerierung der Knoten in den jeweiligen Baeumen. Hier sieht man gut das diese immer gleich bleibt, egal mit welchem Knoten man startet.
Vermutung:
Alle nichtsymetrischen Graphen sind bezueglich (Deiner Aufgabenstellung) BFS-Baeumen und DFS-Baeumen bei Vertauschung der Reihenfolge in der Adjazenzliste nichtisomorph.
Notiz: Das brauchen wir zum Glück nicht zu beweisen, Du brauchst ja nur ein Beispiel - ehrlich gesagt wäre ich damit auch erstmal überfordert .
Ich schneide aus unserem Beispiel einfach eine Kante heraus - die Verbindung von 2 zu 3.
Adjazenzliste (N=3)
1 => 2,3
2 => 1
3 => 2
BFS: 1 (0), 2 (1), 3 (1)
DFS: 1 (1/6), 2 (2/3), 3 (4/5)
(das sieht aus wie ein Binärer Baum mit 2 Blättern)
Adjazenzliste (N=3)
3 => 2
1 => 2,3
2 => 1
BFS: 3 (0), 1 (1), 2 (2)
DFS: 3 (1/6), 1 (2/5), 2 (3/4)
(das sieht aus wie eine Menge von Knoten an einem Seil)
Tja, thats it.
Als allgemeines Beispiel wäre der Baum zu nennen. (ist ja recht beliebt in der Informatik )
Wenn Du einen beliebigen Baum (mit mindestens 3 Knoten - 2 Knoten sind ja symmetrisch) hernimmst und für BFS und DFS jeweils einen anderen Startknoten nimmst, bekommst Du immer nichtisomorphe Darstellungen.
Wenn Du also Deinen Prof. beeindrucken willst nimmst Du eben einen Baum (Graph) mit 10 Knoten
Cu Onkel Murray |
|
