Algorytmika, II semestr, studia niestacjonarne II stopnia,

Systemy Informatyczne

J.Koszelew

Temat nr 3: Algorytmy aproksymacyjne dla trudno rozwi zalnych problemów

grafowych

Zadanie 1

Zaimplementuj jeden algorytm przybli ony rozwi zuj cy metryczn wersj problemu

komiwoja era (patrz wykład pkt 2a)

Zadanie 2

Zaimplementuj jeden algorytm przybli ony rozwi zuj cy problem kolorowania grafu (patrz

wykład pkt 2b)

Zadanie 3

Zaimplementuj jeden algorytm przybli ony rozwi zuj cy problem minimalnego pokrycia

wierzchołkowego (patrz wykład pkt 2c2)

Zadanie 4

Zaimplementuj jeden algorytm przybli ony rozwi zuj cy problem drzewa Steinera (patrz

wykład pkt 2d)

Uwaga do wszystkich wariantów zadania!!!

Je eli zostanie zaimplemetowany algorytm omawiany na wykładzie, to maksymalna

liczba punktów za zadanie wynosi 10.