АСП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
Predlažemo strukturu neusmerenog težinskog grafa u kojem čvorovi predstavljaju pozicije i igrače a grana između igrača pozicije označava da taj igrač može da igra tu poziciju (ocena je težina grane). Na početku odabira pozicije se čuvaju u opadajućem prioritetnom redu po broju suseda, i onda se ide po tom redu i svakoj poziciji dodeljuje igrač koji je najsposobniji za tu poziciju, a zatim se izbacuju čvor pozicije i igrača iz grafa i ažurira broj suseda u prioritetnom redu. Taj proces se ponavlja dok ima čvorova u prioritetnom redu.
6. zadatak
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 (x > y) and ((F[x, y] > 0) or (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
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)