АСП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.

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

Датотека:ASP1 K3 2018 zadatak 2 graf.png

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 grafik 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 : (k, j) ∈ E} do
    paths = paths + FIND_PATHS_NUM(G, j, dst, k - 1)
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}
curr = 0
for i = 1 to n-1 do
    find min {w(u, v) : (u ∈ S) and (v ∈ (V - S))}
    curr = curr + w(u, v)
    if curr > 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, š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 ABCDFFGE.

• ASP1 K3 2018 zadatak 6 graf.png

  Graf iz postavke zadatka.

• ASP1 K3 2018 zadatak 6 rešenje.png

  Rešenje zadatka.

7. zadatak

Postavka

Датотека:ASP1 K3 2018 zadatak 7 graf.png

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

Rezidualni graf G_f je usmereni težinski graf čije grane označavaju na koji način se protok u grani koja spaja ista dva čvora u protočnom grafu G može promeniti. Ako grana između dva čvora u rezidualnom grafu ima isti smer kao grana između ta dva ista čvora u protočnom grafu, to označava da se protok kroz granu u protočnom grafu može maksimalno povećati za težnu grane u rezidualnom grafu. Analogno, ako grane imaju suprotne smerove to označava da se protok kroz granu u protočnom grafu može maksimalno smanjiti za težinu grane u rezidualnom grafu. Moguće je da postoje dve grane između dva čvora u rezidualnom grafu, i ako se protok kroz jednu granu u protočnom grafu ne može menjati na određen način onda odgovarajuća grana u rezidualnom grafu (koja bi u suprotnom bila težine 0) ne postoji.

Rezidualni graf se dobija iz protočnog tako što se svaka grana protočnog grafa zameni jednom granom istog smera težine (kapacitet - protok) i drugom granom suprotnog smera težine protok, pa se zatim izbace grane težine 0.

Rezidualni graf može stoga 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