View Full Version : [Frage] UE-Test vom 11.12.03 /Bsp. 3
hallo!
hat vielleicht irgendjemand schon den test gemacht und könnte die Lösung vom Beispiel 3a) und 3b) posten?? Ich bin mir nämlich nicht sicher, ob ich das richtig verstanden habe.
lg
Ich habe von
0 nach 3 weiss
0 nach 4 weiss
0 nach 6 weiss
von
1 nach 0 grau
1 nach 2 weiss
1 nach 3 grau
von
2 nach 3 grau
2 nach 5 weiss
2 nach 6 schwarz
2 nach 7 weiss
von
3 gehts nirgends hin
von
4 nach 8 weiss
4 nach 9 weiss
5,6,7,8,9 nirgendwo hin
bei b)
von 1= i gehts weiss nach k=2 und von dort gleich weiter nach 3=J mit weiss
von 1 nach 3=j grau
von 3=j dann zurück nach 2=k mit grau
Hier hab ichs gezeichnet...
clemensp
18-05-2004, 16:07
für welche gruppe hast du das gemacht für a ?
dann hast du nämlich den pfeil von 0 nach 2 übersehn
und generell hab ich ne andre lösung...
das kommt dann aber evtl daher dass du den 2er übersehn hast
clemensp
18-05-2004, 16:17
führ b gibt imho mehr lösungen :)
zumindest wenn meine annahme stimmt das wenn man das ganze jetz für den knoten 1 aufruft und der alle seine knoten abklappert... wenn dann noch nicht alle knoten markiert sind... dann wird ja das ganze für den niedrigstn nicht markierten knoten nochmal aufgerufn oda ?
dann kann man das ganze auch so lösen denk ich :
1: k
2: J
3: i
adjazenzmatrix :
* k j i
k 0 0 0
j 1 0 0
i 0 1 0
AmaNoGawa
18-05-2004, 16:36
Ich habe von
0 nach 3 weiss
0 nach 4 weiss
0 nach 6 weiss
mhm.. und warum hast du nicht auch 0 nach 2?
das ändert halt deinen rest dann...
von 2 nach 6 würd ich weiß machen weil 6 ja noch nicht entdeckt wurde... oder?
du hast das überhaupt komisch aufgschrieben.. das is doch tiefensuche...
das heisst ich geh von 0 nach 2 von 2 nach 3 von 2 nach 5.. von 2 nach 6.. von 2 nach 7.. wieder zurück auf die 0.. dann geh ich von der null auf die 3.. wieder zurück auf die null.. von der null auf die 4... von der 4 auf die 8.. von der 4 auf die 9.. wieder zurück auf die 0.. von der null auf die 6.. wieder zurück auf die null.. geht nirgendwohin mehr... ich geh auf die 1.... oder?!
clemensp
18-05-2004, 16:46
bin deiner meinung
aber er hat nur die kanten hingeschriebn welche farben sie haben
und den 2er hat er wirkli übersehn
i schreibs mal wie ichs hab (das is nicht die reihenfolge in der man durchgeht sondern nur die kantenfarbe)
von knoten
0 nach
-------
2 weiß
3 schwarz
4 weiß
6 schwarz
1 nach
-------
0 grau
2 grau
3 grau
2 nach
-------
5 weiß
6 weiß
7 weiß
3 hat keinen
4 nach
-------
8 weiß
9 weiß
5 hat keinen
6 hat keinen
7 hat keinen
8 hat keinen
9 hat keinen
ich hoff i hab nix vergessa ^^
von knoten
0 nach
-------
2 weiß
3 schwarz
4 weiß
6 schwarz
kannst du mir kurz erklaeren wie du auf die ersten vier knotenfarben kommst- habs sonst genau wie du!
gibt es einen unterschied in der Vorgehensweise, wenn die Grafen nicht gerichtet gewesen wären? vom Alg her denke ich nicht, nur das mehrere Kanten zu untersuchen sind
lg
clemensp
18-05-2004, 17:03
naja das ganze is ja tiefensuche das heist man geht immer sofort tiefer in den graphen hinein
bei 0 fang ich an der erste knoten zu dem ich hinkann ist nummer 2
der ist "noch nicht markiert" deswegen wird die kannte weiß
jetz geht man von 2 aus weiter zu 3 weil ja tiefensuche
3 wird markiert... kante von 2 zu 3 ist weiß
von dort komm ihc nirgends hin also mach ich von 2 aus den nächsten knoten der is 5 kante wird der nächste ist jetz 6 !!! der wird markiert kante weiß
wenn man jetzt mal alles soweit abgehandelt hat dass man wieder beim knoten 0 weitermacht
dann ist der nächste knoten von 0 aus der knoten 3
AHA der ist aber schon markiert
ABER unser knoten 0 ist VOR dem knoten 3 markiert worden deswegen wird die kante nicht grau sondern schwarz (das ist eben einer der anderen fälle ^^)
das gleiche gilt dann für die kante (0,6)
die kannte (0,4) is weiß
e klar ^^
für welche gruppe hast du das gemacht für a ?
dann hast du nämlich den pfeil von 0 nach 2 übersehn
und generell hab ich ne andre lösung...
das kommt dann aber evtl daher dass du den 2er übersehn hast
ich glaub eh a
stimmt, ahb ich übersehn ;)
clemensp
18-05-2004, 17:21
^^ dann bin i beruhigt *g*
musst scho genau aufpassen, merlin!
Versteh nicht ganz wann man graue Kanten verwendet. Besser gefragt, was verstehen die unter einem Vorgänger im DFS-Wald ?
julian
clemensp
18-05-2004, 20:45
wenn v vorher vom algorithmus schon entdeckt wurde bevor u entdeckt wurde ist v ein vorgänger von u :)
@Merlin ... dein Graph stimmt aber nicht oder??
1 ist doch vor der 3 markiert worden also muss die Kante 1,3 doch eigentlich schwarz sein oder??
hab mal meine Lösung angehängt
floevents
18-05-2004, 21:25
habts ihr nicht grau und schwarz vertauscht
die kanten (1,0) (1,2) (1,3) müssten doch schwarz sein
punkt 1 wird ja nie besucht
ich bezieh mich auf 3.A
clemensp
18-05-2004, 21:32
doch punkt 1 wird besucht
und zwar ganz zum schluss
angabe:
gehen sie davon aus, dass der dfs alogrithmus für alle noch nicht besuchten knoten in der reihenfolge der knotennummern aufgerufen wird
d.h. man ruft den algorithmus mit knoten 0 auf
der ruft dann rekursiv alle knoten einmal auf mit denen er verbunden ist
dann bleibt 1 übrig
der ist noch nicht besucht wurden
also ruft der algorithmus den knoten 1 auch auf weil... siehe oben ^^
Puka Ch'ullu
19-05-2004, 00:40
doch punkt 1 wird besucht
und zwar ganz zum schluss
angabe:
gehen sie davon aus, dass der dfs alogrithmus für alle noch nicht besuchten knoten in der reihenfolge der knotennummern aufgerufen wird
d.h. man ruft den algorithmus mit knoten 0 auf
der ruft dann rekursiv alle knoten einmal auf mit denen er verbunden ist
dann bleibt 1 übrig
der ist noch nicht besucht wurden
also ruft der algorithmus den knoten 1 auch auf weil... siehe oben ^^
Dann gibt es also überhaupt keine schwarzen Kanten?
clemensp
19-05-2004, 00:42
doch 0 3 und 0 6
hab ich oben schon wo beschriebn warum die schwarz sind
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.