graf z wagami

macko88 · Post autor: **macko88** » 1 wrz 2009, o 02:55

zad. Rozważ graf G z wagami przedstawiony na poniższym rysunku.

(a) (4 pkt) Stosując dowolny algorytm znajdź minimalne drzewo spinające grafu G. Podaj
nazwę algorytmu i opisz jego kolejne kroki (samo podanie rozwiązania - 1 pkt).
(b) (1 pkt) Czy minimalne drzewo spinające dane jest jednoznacznie?
(c) (5 pkt) Stosując algorytm Dijkstry znajdź najkrótszą drogę od wierzchołka S do
wierzchołka M. Opisz kolejne kroki algorytmu (samo podanie rozwiązania - 1 pkt).
(d) (1 pkt) Jaka jest waga znalezionej najkrótszej drogi?

Dumel · Post autor: **Dumel** » 4 wrz 2009, o 12:59

a) zastosuj algorytm Kruskala lub algorytm Prima
b) nie, co łatwo można sprawdzić przy jego konstrukcji
c) jeśli znasz algorytm Dijkstry to nie wiem w czym problem
jeśli nie znasz algorytmu to nie będe pisał rozwiązania bo byłoby to dosyć dziwne, ale podam odpowiedź:
d) 4

miodzio1988 · Post autor: **miodzio1988** » 4 wrz 2009, o 13:16

Dumel pisze:a) zastosuj algorytm Kruskala lub algorytm Prima
b) nie, co łatwo można sprawdzić przy jego konstrukcji

No b tak się lekko czepne.
Tw.
Drzewo T wybrane przez algorytm Kruskala jest najtańszym drzewem rozpinającym w G.
Zgadzasz się z tym twierdzeniem? Tak tylko się pytam dla uściślenia Twojej wypowiedzi. Bo można jednoznaczność roznie interpretować.

Dumel · Post autor: **Dumel** » 4 wrz 2009, o 15:56

zgadzam się
oczywiście miałem na myśli niejednoznacznie wyznaczone krawędzie drzewa

macko88 · Post autor: **macko88** » 5 wrz 2009, o 15:25

moglbym prosic kogos o rozwiazanie tego zadania?

miodzio1988 · Post autor: **miodzio1988** » 5 wrz 2009, o 15:26

Dumel pisze:a) zastosuj algorytm Kruskala lub algorytm Prima
b) nie, co łatwo można sprawdzić przy jego konstrukcji
c) jeśli znasz algorytm Dijkstry to nie wiem w czym problem
jeśli nie znasz algorytmu to nie będe pisał rozwiązania bo byłoby to dosyć dziwne, ale podam odpowiedź:
d) 4

Kolega Ci powiedział co masz zrobić. Jaki masz dalej problem?