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