PRIMENE RAČUNARA - septembar 2002.

1. Dokazati da u povezanoj planarnoj mapi postoji bar jedan čvor stepena manjeg od šest. REŠENJE: Posmatrajmo povezanu planarnu mapu sa |V | čvorova (temena), |E| grana (ivica). Neka je |F | broj oblasti na koje je ravan podeljena ivicama. Prema Ojlerovoj formuli važi jednakost

|V | + |F | = |E| + 2

. Pretpostavimo suprotno: ne postoji takav čvor, tj.

d_{i} ≥ 6, i = 1..|V |

Dakle,

2|E| = ∑_{i=1}^{|V |} d_{i} ≥ 6|V |

. Odavde,

|V | ≤ \frac{|E|}{3}

Svaka oblast koju odredjuje graf u ravni je ograničena sa najmanje tri grane, a svaka grana se pojavljuje po 2 puta kao granica (za 2 različite oblasti ili za istu oblast (most)). Dakle,

2|E| ≥ 3|F |

Odnosno

|F | ≤ \frac{2}{3}|E|

.

Ali,tada je po Ojlerovoj formuli

2 = |F | − |E| + |V | ≤ \frac{2}{3}|E| − |E| + \frac{|E|}{3} = 0

Dakle, polazna pretpostavka nije tačna.

2. Dat je usmereni graf G = (V, E) sa skupom čvorova V = {0,1,2,3,4,5,6} i skupom grana E sa dužinama redom

\begin{aligned}E = \{ & (0,1), & (0,3), & (1,3), & (1,4), & (2,0), & (2,5) , & (3,2), & (3,4), & (3,5) , & (3,6), & (4,6), & (6,5)\} \\ & 2 & 1 & 3 & 10 & 4 & 5 & 2 & 2 & 8 & 4 & 6 & 1 \end{aligned}

Odrediti najkraće puteve od čvora 0 do ostalih čvorova ovog grafa. REŠENJE: Primenom algoritma (nedavno preminulog) Edsger Dijkstra za nalaženje dužina najkraćih puteva od zadatog čvora do svih ostalih čvorova u grafu, dobija se:

0 1 2 3 4 5 6
3 0 2 ∞ 1 ∞ ∞ ∞
1 0 2 3 1 3 9 5
2 0 2 3 1 3 9 5
4 0 2 3 1 3 8 5
6 0 2 3 1 3 6 5

3. Koja funkcija je donja granica složenosti algoritama za sortiranje n elemenata, ako su algoritmi zasnovani na uporedjivanju? Odgovor obrazložiti.

4. Konstruisati algoritam za odredjivanje maksimalnog od datih n brojeva (ne nužno različitih) na modelu CRCW, tako da vreme izvršavanja algoritma bude O(1) i da koristi najviše n^{2} procesora .

REŠENJE: Koristi se n(n − 1)/2 procesora. Svakom od datih brojeva x_{i} pridružuje se po jedna (deljena) memorijska lokacija v_{i}. Svakom paru {i, j} zadatih brojeva se pridružuje procesor P_{ij}, a najpre se u sve lokacije v_{i} upisuje vrednost 1. U sledećem koraku algoritama, procesor P_{ij} poredi elemente x_{i} i x_{j}; ako je jedan od njih manji onda u njegovu odgovarajuću lokaciju upisuje se vrednost 0; ako su x_{i} i x_{j} jednaki onda ako je i < j onda se 0 upisuje u v_{i}, a inače se 0 upisuje u v_{j}. Nakon toga samo u jednoj od lokacija v_{i} ostaje upisana vrednost 1. Detektuje se kojem je zadatom elementu pridružena ta lokacija. Taj broj je maksimum zadatih vrednosti.

Nezavisno od n, algoritam zahteva dva koraka, dok je broj procesora koji se koristi n(n − 1)/2. Otuda, vreme izvršavanja algoritma je O(1) i on zahteva O(n^{2}) procesora.