Ucz się szybciej
Testy Fiszki Notatki
Zaloguj  

Fiszki

AISDE LAB5

Test w formie fiszek Lecimy
Ilość pytań: 7 Rozwiązywany: 1578 razy
Algorytm Prima:
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
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
jego złożoność obliczeniowa zależy od ilości krawędzi
Algorytm Kruskala:
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
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
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
Algorytm Boruvki:
tworzy drzewo Steinera
działa tylko dla grafów skierowanych
na początku dokonuje sprawdzenia czy są cykle
nie działa, gdy są cykle
na początku dokonuje sprawdzenia czy są cykle
Algorytm Floyda w stosunku do Dijkstry:
- 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
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
Ogólne pytania:
macierz sąsiedztwa ma wymiar VxE, dla V-liczba wierzchołków, E-liczba 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
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
graf niepełny nieskierowany ma max V*(V-1)/2 krawędzi
Pytanie teoretyczne prawda/fałsz (1pkt) o Floyda
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy najlepiej implementowac na macierzy
czy wagi NIE moga byc ujemne
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy najlepiej implementowac na macierzy
Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek
w grafach planarnych
w grafach zawierajacych cykle
w grafach skieowanych
działać dla krawędzi o ujemnych wagach
w grafach zawierajacych cykle
działać dla krawędzi o ujemnych wagach

Powiązane tematy

#aisde

Inne tryby

Nauka Test Powtórzenie