ASD ew( 06 2005 3

5. (1+1+3+1)

Dany jest graf niezorientowany G, którego wierzchołkami są liczby naturalne 1,2,3,4,5,6,7, a krawędzie, to zbiór par (x,y) takich, że (x+y) mod 3 >0.

(a)    Przedstaw ten graf w postaci macierzowej wiedząc, że waga krawędzi (x,y) wynosi w(x,y)= (x+y) mod3 .

(b)    Ile miejsca zajmie zakodowanie macierzy tego grafu, jeśli użyjemy kodu ASCII?

(c)    Znajdź drzewo kodu prefiksowego Hufmana. Przedstaw etapy tworzenia drzewa kodowego.

(d)    Ile miejsca zajmie zakodowanie tej macierzy, jeśli do zakodowania użyjemy znaleziony kod Huffinana?

6. (1+3+1)

Niech będzie dany graf G przedstawiający sieć dróg między miastami A,B,C,D.E,F. Na każdej krawędzi zaznaczono długość odpowiadającej jej drogi.

(a)    Zapisz graf G w postaci tablicy list incydencji.

(b)    Znajdź najkrótszą drogę z miasta A do miasta D (Przez jakie wierzchołki przechodzi i jaki jest jej koszt).Opisz zastosowaną metodę postępowania i przedstaw kolejne kroki działania algorytmu.

(c)    Jeśli wykonano polecenie w punkcie (b), to jaki będzie koszt znalezienia najkrótszej drogi z A do C?