АСП1/К3 2017

Zadaci

1. zadatak

Postavka

Na slici je dat težinski neusmereni graf. Formirati minimalno obuhvatno stablo korišćenjem Kruskalovog algoritma. Prikazati postupak izbora grana i finalno stablo.

Rešenje

Kada uredimo grane po težini dobijamo redosled po kojem možemo da ih biramo za ubacivanje u graf.

1. B-D (2)
2. C-E (5)
3. A-C (8)
4. C-D (10)
5. A-B (12) - A i B su već povezani preko A-C, C-D i B-D
6. D-E (13) - D i E su već povezani preko C-D i C-E
7. B-M (15)
8. A-E (25) - svi čvorovi su nam već u stablu
9. M-E (30) - svi čvorovi su nam već u stablu

• 

  Graf iz postavke zadatka.

• 

  Minimalno obuhvatno stablo za graf iz postavke zadatka.

2. zadatak

Postavka

Napisati u pseudokodu iterativnu implementaciju funkcije za topološko sortiranje usmerenog netežinskog grafa. Ukoliko u nekom trenutku više čvorova može biti kandidat za istu poziciju u finalnom redosledu, bira se čvor sa najviše neposećenih suseda. Graf se predstavlja pomoću liste susednosti u čijem se zaglavlju za svaki čvor, pored pokazivača na odgovorajuću listu suseda, nalazi i broj suseda. Funkcija treba da vrati niz čvorova u topološkom poretku.

Rešenje

TOPSORT(G, n)
p = nil
for i = 1 to n do
    in[i] = 0
end_for
for i = 1 to n do
    p = first(e[i])
    while p ≠ nil do
        in[value(p)] = in[value(p)] + 1
        p = next(p)
    end_while
end_for
tail = head = nil
for i = 1 to n do
    if in[i] = 0 then
        if tail = nil then
            tail = head = GETNODE
            value(tail) = i
        else
            PRIORITY_QUEUE_INSERT(tail, head, E, i)
        end_if
    end_if
end_for
i = 1
while tail ≠ nil do
    ret[i] = value(tail)
    p = first(e[i])
    while p ≠ nil do
        in[value(p)] = in[value(p)] - 1
        if in[value(p)] = 0 then
            PRIORITY_QUEUE_INSERT(tail, head, E, value(p))
        end_if
        p = next(p)
    end_while
    i = i + 1
    p = tail
    tail = next(tail)
    FREENODE(p)
end_while
return ret
PRIORITY QUEUE INSERT(tail, head, E, value)
p = tail
found = false
t = nil
if num(e[value]) > num(e[value(p)]) then
    tail = GETNODE
    value(tail) = value
    next(tail) = p
else
    while next(p) ≠ nil do
        if num(e[value]) > num(e[value(next(p))]) then
            t = next(p)
            next(p) = GETNODE
            value(next(p)) = value
            next(next(p)) = t
            found = true
            break
        end_if
        p = next(p)
    end_while
    if not found then
        next(head) = GETNODE
        value(next(head)) = value
        head = next(head)
    end_if
end_if

3. zadatak

Postavka

Perica je vodoinstalater. Završio je posao za danas i vraća se kući, gde ga žena čeka za ručkom. Na putu do svoje kuće prolazi pored kuća svojih prijatelja i zna da će ga svaki od njih zaustaviti da popriča sa njim (malo mesto, svi se znaju, a i naš Perica je dobar vodoinstalater). Perica je gladan i nije danas mnogo raspoložen za priču, pa želi da stigne kući i pritom popriča sa što manjim brojem ljudi. Put do kuće sadrži određeni broj raskrsnica koje spajaju ulice sa određenim brojem kuća.

1. Objasniti na koji način se izloženi problem može modelovati putem grafa.
2. Napisati u pseudokodu funkciju koja navodi Pericu od posla do kuće tako da na putu popriča sa što je moguće manjim brojem ljudi.

Rešenje

Ovaj sistem možemo modelovati neusmerenim težinskim grafom u kojem su posao, kuća i raskrsnice čvorovi, ulice između njih su grane a težina tih grana je broj ljudskih bića sa kojima će Perica nažalost morati da se sukobi u njegovoj najneomiljenijoj disciplini: prijateljskom razgovoru.

GET PERICA HOME(G, work, home)
S = {home}
p = nil
curr = 0
for i = 1 to n do
    d[i] = w(home, i)
    if d[i] = ∞ then
        t[i] = 0
    else
        t[i] = home
    end_if
end_for
for k = 1 to n-1 do
    find min {d[i] : i ∈ (V - S)}
    p = e[i]
    while p ≠ nil do
        if d[i] + w(i, value(p)) < d[value(p)] then
            d[value(p)] = d[i] + w(i, value(p))
            t[value(p)] = i
        end_if
        p = next(p)
    end_while
    S = S + {i}
end_for
curr = t[work]
while curr ≠ home then
    GO(curr)
    curr = t[curr]
end_while
GO(home)

4. zadatak

Postavka

Graf iz postavke zadatka.

Za graf sa slike naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove. Kritični put označiti i na samom grafu.

Rešenje

Kritičan put: ACGSRT

Čvor	EST	LST	L
A	0	0	0
C	11	11	0
E	13	25	12
F	26	31	5
G	18	18	0
H	10	13	3
K	32	36	4
N	35	39	4
R	40	40	0
S	38	38	0
T	43	43	0

5. zadatak

Postavka

Neka se posmatra jedan fudbalski tim sa 25 članova koji konkurišu za 11 pozicija u timu. Svaki igrač ima definisan skup pozicija na kojima može da igra, a za svaku poziciju mu se dodeljuje odgovarajuća ocena. Dati predlog na koji način se dati problem može modelovati grafom i izvršiti selekcija prve postave, tako da se izabere postava od 11 igrača koji imaju najbolje ocene. Smatrati da je svaka pozicija u timu pokrivena najmanje jednim igračem.

Rešenje

Ovaj problem se može modelovati bipartitnim grafom gde čvorovi jednog dela označavaju fudbalere, čvorovi drugog pozicije na kojima oni mogu igrati, grane između fudbalera i pozicije označavaju da taj fudbaler može igrati na toj poziciji a težina te grane njegova ocena. Uparivanje se vrši brute-force metodom, tako što se isprobaju sva moguća uparivanja fudbalera i pozicija gde su sve pozicije zauzete i izabere ono gde je zbir težina grana najveći.

6. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Neka se posmatra netežinski usmereni graf G sa n čvorova. Za posmatrani graf su korišćenjem DFS algoritma određena početna i završna vremena svih čvorova i smeštena u nizovima F i L dužine n. Napisati u pseudokodu funkciju koja pronalazi najveću jako povezanu komponentu po broju čvorova. Smatrati da je graf predstavljen pomoću matrice susednosti.

Rešenje

MAX STRONG CC(G, n)

7. zadatak

Postavka

Neka je dato neko stanje protočnog grafa preko matrice trenutnih protoka F kao i odgovarajuće stanje rezidualnog grafa preko matrice R.

1. Napisati funkciju koja određuje matricu kapaciteta i izračunava broj grana polaznog protočnog grafa.
2. U odnosu na broj grana početnog protočnog grafa, odrediti koliko najmanje i koliko najviše grana može imati rezidulani graf.

Rešenje

Rezidualni graf najmanje može imati $n-1$ grana u slučaju da su svi protoci puni ili prazni i ima tačno onoliko grana koliko je potrebno da bi graf bio povezan, ili $n(n-1)$ grana u slučaju da nijedan protok nije pun ili prazan i svaki čvor je povezan sa svakim.

FLOW CAP(F, R)
num_total = 0
for x = 1 to n do
    for y = 1 to n do
        if (F[x, y] > 0) or ((F[x, y] = 0) and (F[y, x] = 0) and (R[x, y] > 0)) then
            num_total = num_total + 1
        end_if
        if F[x, y] = 0 then
            if R[x, y] ≠ 0 then
                C[x, y] = R[x, y]
            end_if
        else
            C[x, y] = F[x, y] + R[x, y]
        end_if
    end_for
end_for
return num_total

8. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Potrebno je utvrditi da li je dati povezani neusmereni graf cikličan na što efikasniji način.

1. Objasniti postupak i dati vremensku složenost.
2. Na osnovu predloženog postupka napisati pseudokod.

Rešenje

IS CYCLIC(G)