АСП1/К3 2017
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.
- B-D (2)
- C-E (5)
- A-C (8)
- C-D (10)
A-B (12)- A i B su već povezani preko A-C, C-D i B-DD-E (13)- D i E su već povezani preko C-D i C-E- B-M (15)
A-E (25)- svi čvorovi su nam već u stabluM-E (30)- svi čvorovi su nam već u stablu
- ASP1 K3 2017 zadatak 1 graf.png
Graf iz postavke zadatka.
- ASP1 K3 2017 zadatak 1 MST.png
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.
- Objasniti na koji način se izloženi problem može modelovati putem grafa.
- 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
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.
- Napisati funkciju koja određuje matricu kapaciteta i izračunava broj grana polaznog protočnog grafa.
- 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 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 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.
- Objasniti postupak i dati vremensku složenost.
- Na osnovu predloženog postupka napisati pseudokod.
Rešenje
IS CYCLIC(G)