АСП1/К3 2018

Zadaci

1. zadatak

Postavka

Diskutovati implementaciju algoritma za topološko sortiranje grafa u inverznom poretku, ukoliko se za memorijsku reprezentaciju grafa usvoje liste susednosti. Da li je za ovu operaciju pogodnije koristiti inverzne liste susednosti? Obrazložiti odgovor uz precizno navođenje razlika u implementaciji.

Rešenje

Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana.

U ovom slučaju je najpovoljnije koristiti inverzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost $O(n+e)$ jer se postupak ponavlja za svih $n$ čvorova u grafu, a ukupno se prolazi kroz $e$ grana.

Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo našli kojim čvorovima je on sve sledbenik.

2. zadatak

Postavka

Data je matrica puteva dužine tačno 1 (jedan) nekog netežinskog usmerenog grafa. Odrediti matricu puteva dužine d≤3. Postupak prikazati po koracima, uz obrazloženje.

-	A	B	C	D	E
A	0	1	1	0	0
B	0	0	0	0	0
C	1	1	0	0	0
D	1	0	0	0	0
E	0	0	0	1	0

Rešenje

Graf koji se dobija iz matrice susednosti.

Naša tabela već sadrži informacije o svim putevima dužine 1, a to su:

• AB
• AC
• CA
• CB
• DA
• ED

Na osnovu toga možemo nacrtati graf s desne strane. Nakon toga sa kraja svakog od prethodnih puteva nastavljamo kroz još jednu granu kako bismo dobili sve moguće puteve dužine 2.

• AB → ne može dalje
• AC → ACA, ACB
• CA → CAC, CAB
• CB → ne može dalje
• DA → DAB, DAC
• ED → EDA

I taj proces ponovimo još jednom kako bismo dobili puteve dužine 3.

• ACA → ACAB, ACAC
• ACB → ne može dalje
• CAC → CACB, CACA
• CAB → ne može dalje
• DAB → ne može dalje
• DAC → DACA, DACB
• EDA → EDAB, EDAC

Na osnovu dobijenih puteva ažuriramo matricu povezanosti tako što za svaki put uzmemo čvor sa početka puta i čvor sa kraja puta, postavimo polje za granu između ta dva čvora na 1 i za sve ostale čvorove postavimo na 0. Tako se dobija konačna tablica ispod.

-	A	B	C	D	E
A	1	1	1	0	0
B	0	0	0	0	0
C	1	1	1	0	0
D	1	1	1	0	0
E	1	1	1	1	0

3. zadatak

Postavka

Dat je usmereni težinski acikličan graf. Implementirati funkciju FIND_PATHS_NUM koja treba da pronađe ukupan broj putanja od izvornog čvora (src) do destinacionog čvora (dst) koje su kraće od vrednosti prosleđenog parametra k.

Rešenje

Pošto se ne kaže da mora iterativno rešenje, ovde nam je najlakše rekurzivno rešenje.

FIND PATHS NUM(G, src, dst, k)
if k < 1 then
    return 0
end_if
if src = dst then
    return 1
end_if
paths = 0
for {j : (src, j) ∈ E} do
    paths = paths + FIND_PATHS_NUM(G, j, dst, k - w(src, j))
end_for
return paths

4. zadatak

Postavka

Posmatra se neka opština predstavljena neusmerenim težinskim grafom. Čvorovi grafa predstavljaju naselja, dok grane povezuju čvorove između kojih je moguće postaviti kabl, pri čemu težina predstavlja rastojanje između gradova. Telekomunikacioni operater treba da poveže naselja opštine, odnosno da postavi kablove između njih. Kablovi koje operater ima na raspolaganju su dužine k i mogu se skratiti po potrebi, ali se ne mogu nastavljati. Napisati funkciju u pseudokodu koja za prosleđeni graf sa datim brojem čvorova n i parametrom k vraća da li je moguće povezati sva naselja u okviru opštine telekomunikacionom mrežom.

Rešenje

TELECOM(G, n, k)
S = {1}
for i = 1 to n-1 do
    find min {w(u, v) : (u ∈ S) and (v ∈ (V - S))}
    if w(u, v) > k then
        return false
    end_if
    S = S + {v}
end_for
return true

5. zadatak

Postavka

Neka je dat neusmeren netežinski graf G predstavljen matricom susednosti. Napisati u pseudokodu iterativnu funkciju za određivanje povezanih komponenti u zadatom grafu i komentarisati njenu složenost. Funkcija treba da vrati informaciju o povezanim komponentama u vidu niza pokazivača, gde svaki pokazivač pokazuje na jedan od čvorova iz odgovarajuće povezane komponente.

Rešenje

Osnovna detekcija povezanih komponenti funkcioniše tako što jedna petlja prolazi kroz svaki čvor i ako nije posećen računa ga kao odvojenu komponentu i radi DFS nad njim kako bi se ostali čvorovi u komponenti označili kao posećeni. Sa listom susednosti spoljašnja petlja prolazi tačno n puta kroz niz a od svakog čvora prilikom DFS-a se moraju posetiti sve grane, pa to čini ukupnu složenost od $\mathcal{O(e + n)}$. Pošto, nažalost, koristimo matricu susednosti umesto liste susednosti, pri obilaženju svakog čvora DFS-om moraćemo da prođemo kroz ceo red matrice kako bismo odredili koje su u njoj grane, i to ćemo morati da učinimo za svaki čvor (jer ćemo svaki čvor morati da posetimo), što bez obzira na spoljašnju petlju čini složenost od $\mathcal{O(n^2)}$.

CONN COMP MAT(G)
curr_comp = 0
for i = 1 to n do
    comp[i] = 0
end_for
stack = t = nil
for i = 1 to n do
    if comp[i] = 0 then
        curr_comp = curr_comp + 1
        comp[i] = curr_comp
        stack = GETNODE
        value(stack) = i
        while stack ≠ nil do
            for j = 1 to n do
                if (e[value(stack), j] = 1) and (comp[j] = 0) then
                    comp[j] = curr_comp
                    t = next(stack)
                    next(stack) = GETNODE
                    value(next(stack)) = j
                    next(next(stack)) = t
                end_if
            end_for
            t = stack
            stack = next(stack)
            FREENODE(t)
        end_while
    end_if
end_for
ALLOCATE(res[curr_comp])
for i = 1 to curr_comp do
    res[i] = nil
end_for
for i = 1 to n do
    if res[comp[i]] = nil then
        res[comp[i]] = v[i]
    end_if
end_for
return res

6. zadatak

Postavka

Neka se posmatra usmeren graf sa slike. Pod pretpostavkom da se za obilazak grafa koristi BFS algoritam i početni čvor A, definisati i obeležiti grane stabla obilaska, grane unapred, povratne grane i poprečne grane. Smatrati da se susedi obilaze u alfabetskom poretku njihovih oznaka.

Rešenje

Redosled obilaska je ABCDFGEFH. Stablo obilaska izgleda ovako:

    A
 /  |  \
B   C   D
|   |  / \
F   G F2  E
|
H

• 

  Graf iz postavke zadatka.

• 

  Rešenje zadatka.

7. zadatak

Postavka

Pojednostavljen graf iz postavke zadatka.

Za graf sa slike, odrediti najkraća rastojanja od čvora C do svih ostalih čvorova. Kada algoritam završava svoj rad u ovom slučaju?

Rešenje

Algoritam završava svoj rad kada više ne postoji čvor grafa i ∉ S kome d[i] ≠ ∞.

S	T	D
		A	B	D	E	F	G	H
C	-	∞	∞	3	∞	∞	4	∞
C, D	D	∞	∞	3	7	9	4	∞
C, D, G	G	∞	∞	3	7	6	4	∞
C, D, G, F	F	∞	∞	3	7	6	4	9
C, D, G, F, E	E	∞	∞	3	7	6	4	9
C, D, G, F, E, H	H	∞	∞	3	7	6	4	9

8. zadatak

Postavka

Maksimizacija protoka grafa G(V, E)

1. Na formalan (netekstualni) i precizan način definisati rezidualni graf G_f za protočni graf G. Koliko maksimalno grana može da ima rezidualni graf?
2. Napisati funkciju koja na osnovu protočnog grafa G formira rezidualni graf G_f. Graf G je zadat listom susednosti, gde čvor liste sadrži trenutni protok grane f i njen kapacitet c.

Rešenje

$G_f = (V, E_f)$

$E_f = \{(i, j) : i, j \in V, c(i, j) - f(i, j) > 0 \}$

Rezidualni graf može maksimalno da ima duplo više grana od protočnog grafa, u slučaju da se nakon zamene grana ne dobiju grane težine 0. Protočni graf ima maksimalan broj grana $\frac{n(n-1)}{2}$ jer između svaka dva čvora može da postoji grana, pa zato rezidualni graf može da ima maksimalno $n(n-1)$ grana.

GTOGF(G)
ALLOCATE(E', n)
for i = 1 to n do
    e'[i] = nil
end_for
p = nil
for i = 1 to n do
    p = e[i]
    while p ≠ nil do
        BRANCH_INSERT(E', i, value(p), c(p) - f(p))
        BRANCH_INSERT(E', value(p), i, f(p))
        p = next(p)
    end_while
end_for
return' (V, E)
BRANCH INSERT(E', from, to, w)
if w = 0 then
    return
end_if
t = e'[from]
e'[from] = GETNODE
value(e'[from]) = to
next(e'[from]) = t
w(e'[from]) = w