Seite 1 von 2

Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 13:27
von ^Lara^
Was genau bedeutet:
"..., kann die Menge E' nicht durch eine Breitensuche als Kantenmenge E_pi des Vörgängerbaums von G produziert werden." ?

Also wir haben jetzt einen Vorgängerbaum mit BFS erstellt.. nach was sollen wir jetzt schauen? wie genau ist die Aufgabe zu verstehen?

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 13:29
von Mspringer
Finde die Teilmenge von E, die eben nicht durch ne Breitensuche so gefunden werden kann. Es gibt 2 davon, als Tipp.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 14:51
von Tigger
Mspringer hat geschrieben:Finde die Teilmenge von E, die eben nicht durch ne Breitensuche so gefunden werden kann. Es gibt 2 davon, als Tipp.
Sicher? ich meine es sind 6. So wie ich das sehe gibt es nur 2, die als Vorgägerbaum in frage kommen.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 15:10
von Mspringer
Haste recht. Sind mehr. Hups ^^

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 16:01
von Ambush
hmm, ich sehe leider nur 2 Lösungen. Die Pfade müssen ja eindeutig sein also es darf keine 2 Pfade von s zu einem v geben richtig ? es dürfen auch keine knoten in G' von s aus unerreichbar sein welche in G erreichbar sind oder ?
kann mir jemand ein tip geben, wo die anderen 4 lösungen sind ?

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 16:06
von s!mon
Welche anderen 4 Lösungen? Bei mir sinds auch nur 2..

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 16:37
von Ambush
Tigger hat geschrieben:
Mspringer hat geschrieben:Finde die Teilmenge von E, die eben nicht durch ne Breitensuche so gefunden werden kann. Es gibt 2 davon, als Tipp.
Sicher? ich meine es sind 6.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 18:44
von Mspringer
Es gibt 4 Möglichkeiten, die man nicht durch Breitensuche bekommt, wenn ich mich nicht verzählt habe. Und die sind auch alle Eindeutig.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 19:19
von Wang Tang
Es gibt insgesamt nur 4 Möglichkeiten E' zu wählen, die eindeutig sind und alle Knoten umfassen. Zwei davon fallen durch Breitensuche weg, bleiben zwei übrig.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 20:32
von Stumpf.Alex
Wang Tang hat geschrieben:Es gibt insgesamt nur 4 Möglichkeiten E' zu wählen, die eindeutig sind und alle Knoten umfassen. Zwei davon fallen durch Breitensuche weg, bleiben zwei übrig.
Sehe ich allerdings genauso...also der jenige, der 6 Lösungen hat, könnte er bitte einen Hinweis geben wie er auf 6 Möglichkeiten kommt?

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 20:52
von Tigger
Ich korrigiere mich. Hatte in der Aufgabenstellung überlesen, dass die Pfade eindeutig sein müssen. In dem Fall gibts wirklich nur 4 Möglichkeiten von denen 2 wegfallen. Asche auf mein Haupt :oops:

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 19. Mai 2008 21:28
von s!mon
Na gut, hatte schon an meinem Verstand gezweifelt :P

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 20. Mai 2008 17:34
von mariusssl
unter 2 "lösungen" versteht ihr 2 pfade oder?
wenn ja hab ich die aufgabe gecheckt :D

mfg

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 20. Mai 2008 17:41
von Stumpf.Alex
1 Lösung hat zwei Pfade. Es gibt aber dennoch 2 Lösungen mit je zwei Pfaden zu jeweils x und w.

Re: Übung 5 H2 2. Verständnisproblem

Verfasst: 20. Mai 2008 21:43
von Mira`
Ich korrigiere mich. Hatte in der Aufgabenstellung überlesen, dass die Pfade eindeutig sein müssen. In dem Fall gibts wirklich nur 4 Möglichkeiten von denen 2 wegfallen. Asche auf mein Haupt :oops:
Aus welchem Kontext nimmst du das? Das die Pfade eindeutig sein müssen steht für mich nur im Aufgabenteil 1, aber nicht im Teil 2...oder seh ich das falsch?