Strona 1
AISDE LAB5
Pytanie 1
Algorytm Prima:
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
Pytanie 2
Algorytm Kruskala:
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
jego złożoność obliczeniowa zależy od ilości krawędzi
Pytanie 3
Algorytm Boruvki:
działa tylko dla grafów skierowanych
nie działa, gdy są cykle
na początku dokonuje sprawdzenia czy są cykle
tworzy drzewo Steinera
Pytanie 4
Algorytm Floyda w stosunku do Dijkstry:
- może działać dla krawędzi o ujemnych wagach
- może znajdować długości cykli
- działa niezależnie od liczby krawędzi grafu
może działać nieprawidłowo dla grafu o wagach dodatnich nienaturalnych
Pytanie 5
Ogólne pytania:
gdy wszystkie wagi grafu są różne, to istnieje tylko 1 drzewo rozpinające
macierz sąsiedztwa ma wymiar VxE, dla V-liczba wierzchołków, E-liczba krawędzi
złożoność pamięciowa Floyda wynosi V^2
graf niepełny nieskierowany ma max V*(V-1)/2 krawędzi
Pytanie 6
Pytanie teoretyczne prawda/fałsz (1pkt) o Floyda
czy najlepiej implementowac na macierzy
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy wagi NIE moga byc ujemne
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
Pytanie 7
Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek
działać dla krawędzi o ujemnych wagach
w grafach planarnych
w grafach zawierajacych cykle
w grafach skieowanych