ASD ep 08 2005 6

6. (I+3+1+1)

Pewien zbiór miast, oznaczonych liczbami 1,2,3,4,5,6, chcemy połączyć autostradami w taki sposób, aby z dowolnego miasta można było przejechać, korzystając tylko z autostrad, do dowolnego innego. Numer 5 oznacza stolicę. Dla dowolnych dwóch miejscowości x, y, koszt wykonania autostrady, która by je połączyła bezpośrednio wynosi (x +y) mod 6+1. Przedsiębiorstwo AUTOSTRADA, wykonujące całość zadania, musi wybudować autostrady w taki sposób by droga, którą trzeba pokonać z dowolnego miasta do stolicy była jak najkrótsza. Oczywiście, przedsiębiorstwo jest też zainteresowane zminimalizowaniem kosztów całej budowy (tzn. nie będą budowane odcinki autostrad, które nie są konieczne, by sprostać postawionym wymaganiom). Problem polega na tym jak wybrać miejscowości, które powinny być bezpośrednio połączone.

Zadanie właściwe:

(a)    Wskaż algorytm, która pozwoli rozwiązać ten problem (w tym i w dowolnym innym przypadku).

(b)    Przedstaw kolejne etapy działania zaproponowanego algorytmu na podanym przykładzie. Wskaż kolejność, w jakiej zatwierdzane są krawędzie budowanej sieci.

(c)    Narysuj otrzymaną sieć autostrad.

(d)    Oblicz koszt budowy całej sieci.