badopy 2.2

71. Podaj przykład zastosowania algorytmu wyznaczania drzewa ekonomicznego.

Budowa sieci dróg łączących miasta, budowa sieci połączeń miedzy komputerami

72. Wymień znane ci algorytmy wyznaczania najtańszego karkasu grafu.

Algorytm Prima i Algorytm Kruskala

73. Co to jest długość drogi łączącej wybrane wierzchołki w grafie?

Ilość gałęzi wchodzących w skład tej drogi

74. Co to jest maksymalny dendryt dróg najkrótszych w grafie?

Spójny digrafi unigraf bez pętli, mający jeden wierzchołek zwany wierzchołkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi do początku dendrytu do poszczególnych wierzchołków są drogami najkrótszymi

75. Co to jest maksymalny dendryt dróg najdłuższych w grafie?

Spójny digrafi unigraf bez pętli, mający jeden wierzchołek zwany wierzchołkiem dendrytu (bez poprzedników) i pozostałe wierzchołki mające po jednym następniku. Drogi do początku dendrytu do poszczególnych wierzchołków są drogami najdłuższymi

76. Co decyduje o wyborze algorytmu wyznaczania dróg ekstremalnych w sieciach?

Dane wejściowe. (skierowanie lub jego brak, cykliczność lub acykliczność w sensie dróg)

77. Wymień etapy algorytmu wyznaczania dróg ekstremalnych w sieciach acyklicznych

- stwierdzenie cykliczności sieci - przedstawienie digrafu w postaci warstwowej - metodą programowania dynamicznego wyznaczenie wartości zmiennych decyzyjnych optymalizacyjnych długość dróg.

78. W jakich sieciach możemy stosować metodę dekompozycji przy wyznaczaniu dróg ekstremalnych w sieciach?

W sieciach spójnych.

79. Jakim grafem powinna być opisana sieć czynnościowa w metodzie CPM/PERT?

Unigrafem skierowanym, nie zawierającym dróg cyklicznych.

80. Co reprezentuje łuk w metodzie CPM/PERT?

Skierowanie łuku wskazuje kierunek przebiegu czynności. (czynność konieczną do wykonania projektu)