MST Beispiel

[Hagbard]

hallihallo!

kann mir jemand bei diesem beispiel unter die arme greifen ich häng mich irgendwie bei der gradbeschränkung von d = 3 auf wäre nett wenn mir wer helfen könnte

auf was muss ich bei der kantenauswahl achten
bitte hilfe!

mfg hagbard

[Boromir]

Habs glaub ich verstanden, im Skriptum auf Seite 113 im oberen Absatz steht die Lösung.

Der Knotengrad ist definiert als d(v) und bezeichnet die Anzahl seiner (ausgehenden bzw. eingehenden) inzidenten Kanten.

Bedeutet also, wenn im Beispiel d = 3 ist, dann darf es bei jedem Knoten nur maximal 3 Kanten geben, welche den MST aufspannen. 2 Heiße Kandidaten dafür sind Knoten J, I und C. Es gehen bei jenen zwar 4 Kanten weg, es dürfen aber nur 3 in den MST aufgenommen werden.

Plausible Idee, oder?

Die Frage b.) auf dem Zettel hab ich mit nein beantwortet. Stell dir vor du hast 6Knoten, einer in der Mitte welcher mit den anderen Verbunden ist

B C
\ /
A---- F------D
|
E


[EDIT]
Sorry die Zeichnung ist etwas versaut, aber man kanns noch erkennen was ich gemeint habe. :ahhh:
Jetzt ist es nicht möglich mit Kruskal einen MST zu basteln, da ja eigentlich alle Knoten erreicht werden müssten, unsere Gradbeschränkung von 3 hindert uns daran.

Wenn Wolti das ganze noch absegnet bin ich glücklich :verycool:

[Hagbard]

danke jetzt macht das ganze sinn für mich :)

danke boromir, sohn gondors http://hades.gothic.at/iforum/images/smilies/jump.gif

mfg hagbard

mal sehen vielleicht schaut ja wolti noch vorbei

[kenokb]

O je o je kann jemand die Aufgabe richtig lösen, ich bin ganz durcheinander, und blick da jetzt garnichts. Danke!!!

[the_unclean]

danke boromir, sohn gondors http://hades.gothic.at/iforum/images/smilies/jump.gif


Boromir(II) is genaugenommen Sohn Denethors II ;)
Nur der Vollständigkeit halber

also die Kanten hab ich in der Reihenfolge rausbekommen:
LM
BH
DE
AD

wie man sehen kann, gibt es grad mal einen pfad von A nach E, boromir hat recht
mfg
maz

[mrerdbeercombin]

also ich komm da irgendwie auf folgende lösung für a:

1, 2, 3, 4, 5, 9, 12, 13, 15, 16, 17, 18

kann dassein!?

[Hagbard]

würd sagen das passt so komme auch auf das ergebnis

mfg hagbard

[the_unclean]

würd sagen das passt so komme auch auf das ergebnis

mfg hagbard

ok ihr habts mich überzeugt ;)

[Hagbard]

hat jemand vielleicht noch eine schöne antwort auf frage b) ?

Findet der Algorithmus immer einen gradbeschränkten spannenden Baum?


mfg hagbard

[wolti]

naja. solange drei knoten nicht nur von einem knoten aus erreichbar sind würde ich sagen schon. denn wenn r,s,t knoten nur von einem knoten y aus erreichbar sind, so brauchst du eine kante wo zu y hinführt -> d(y)=1. da du aber drei kanten von y wegbrauchst um r,s,t zu erreichen, kommst du wenn du die knoten verbinden willst auf einen grad von 4 im knoten y. das ist ein fall wo er nicht existieren kann. In allen anderen Fällen kannst du so einen zeichen.

Grüße,
wolti

[yrucrem]

Er findet einen ja, aber er soll ja den minimalen gradbeschraenkten aufspannenden Baum finden. Zum Beispiel zu folgendem Graph:

<{A, B, C, D, E}, {[A, B], [A, C], [B, C], [C, D], [C, E], [D, E]}, w>

mit

w([A, B]) = 4
w([A, C]) = 1
w([B, C]) = 2
w([C, D]) = 3
w([C, E]) = 1
w([D, E]) = 10

und unter der Annahme, dass de Gradbeschraenkung d = 3 gilt, wuerde dieser Algorithmnus die Kante [B, C] nehmen und muesste dann -- um auch den Knoten D zu erreichen -- die Kante [D, E] nehmen. Das Gesamtgewicht des Baumes den dieser Algoritmus findet waere 14. Es existiert aber auch ein Baum mit Gewicht 9, naemlich die Kanten [A, B], [A, C], [C, D] und [C, E].

[zungerl]

hallihallo!

kann mir jemand bei diesem beispiel unter die arme greifen ich häng mich irgendwie bei der gradbeschränkung von d = 3 auf wäre nett wenn mir wer helfen könnte

auf was muss ich bei der kantenauswahl achten
bitte hilfe!

mfg hagbard

und wie sieht jetzt die richtige Lösung dieses Beispiels aus??

lg, Z

[-gero-]

also ich komm da irgendwie auf folgende lösung für a:

1, 2, 3, 4, 5, 9, 12, 13, 15, 16, 17, 18




wurde mehrmals bestätigt .... ich komme auf selbe Lösung ..... dürfte also stimmen :devil:

[zungerl]

wurde mehrmals bestätigt .... ich komme auf selbe Lösung ..... dürfte also stimmen :devil:

ok, vielleicht bedarf ich ja noch einer näheren Erläuterung, warum gerade diese Kanten aufgenommen wurden!

z.b. Kante 1: die geht doch von C und von I weg, und C hat 4 weggehende Kanten und I sogar 5

und d ist ja 3;

außerdem, was hat das zu bedeuten:
... nach oben auf einen Maximalgrad von d > 2 beschränkt...

:bounce:

irgendwie steh ich da auf der Seife

Z

[-gero-]

sorry , dachte du brauchst nur Lösung

folgendes

billigste Kante wird immer hinzugenommen

CI 1 <--- Wert der Kante
JM 2
IH 3
EJ 4
JI 5


Soweit so gut Kante JF mit Wert 6 würde die 4. Kante sein die von J weggeht. Also wird sie nicht hinzugenommen da ja d=3 ( max 3 Kanten von Knoten weg).

Die nächste Kante die in dieses Schema passt is Kante LM mit Wert 9.
Kante IL 10 wird wieder nicht hinzugenommen da es sonst nicht mehr kreisfrei wäre.

Unter der Berücksichtigung dieser Aspekte kommst du dann auf die Lösung.

Hoffe ich konnte helfen :)

[zungerl]

Hoffe ich konnte helfen :)

Ja, danke! Sehr sogar!
Ich bin da ursprünglich einem groben Denkfehler unterlegen;
ich nahm an, man darf nur Knoten bzw. deren Kanten aufnehmen,
wo maximal 3 Kanten weggehen!
außerdem bin ich wie wild durch den Baum gehüpft, ohne zu bedenken, daß man ja eigentlich von A nach B, von B nach C, von C nach D, usw... gehen sollte, aber wie schon das 11. Gebot besagt:
"Du sollst dich nicht täuschen!" :D

:bounce:

und was bedeutet dieses Maximalgrad > 2 ??

lg, Z

[-gero-]

und was bedeutet dieses Maximalgrad > 2 ??

lg, Z

Wenn ich mich nicht täusche ist das die Definition für einen gradbeschränkten aufspannenden Baum.

d=1 wär Blödsinn und d=2 scheint auch net zielführend zu sein. :devil:

[Scorpion123]

Eine Frage!
Müssen beim minimalen Spannbeuam immer alle Knoten vorhanden sein????

[onagero]

Das MST-Problem
Gegeben ist ein zusammenhängender und gewichteter (ungerichteter) Graph ... blaZusammenhängend & ungerichtet impliziert dass der MST alle Knoten beinhalten muss. Egal wo du beginnst (Prim), es gibt einen Pfad zu jedem Knoten, bei einem solchen Graphen is ja alles in der selben Zusammenhangskomponente.

[Venefica]

das gab es allerdings schon
http://www.informatik-forum.at/showthread.php?t=31415

dort steht ua. auch die lösung