4736387691

kawałki firma powinna pociąc pręty, aby zmarnować jak najmniej materiału. W jaki sposób można ten problem przetłumaczyć na problem plecakowy?

8. Minimalne drzewa rozpinające

Rozwiązanie zadań z tego podrozdziału sprowadza się do znalezienia minimalnego drzewa rozpinającego pewnego grafu. Odpowiedni przykład został szczegółowo omówiony na wykładzie.

1. Firma telekomunikacyjna chce połączyć pewne miejscowości siecią telefoniczną. W poniższym grafie przedstawione zostały koszty utworzenia połączeń między poszczególnymi miastami. Znajdź sieć połączeń z minimalnym kosztem.

2. Podać przykład spójnego nieskierowanego grafu ważonego G takiego, że |F(G)| > 6 oraz

(a)    istnieje dokładnie jedno minimalne drzewo rozpinające grafu G;

(b)    istnieją co najmniej dwa różne minimalne drzewa rozpinające grafu G.

3. Znaleźć (w książce lub w internecie) algorytm znajdowania minimalnego drzewa rozpinającego (różny od algorytmu Kruskala) oraz zastosować go do rozwiązania poprzednich zadań.

9. Najkrótsze drogi

Rozwiązanie zadań z tego podrozdziału sprowadza się do znalezienia najkrótszej drogi w grafie. Odpowiednie przykłady zostały szczegółowo omówione na wykładzie.