АСП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
- 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)
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
GET PERICA HOME(G, work, 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:
| Čvor | EST | LST | L |
|---|---|---|---|
| A | |||
| C | |||
| E | |||
| F | |||
| G | |||
| H | |||
| K | |||
| N | |||
| R | |||
| S | |||
| T |
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
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
FLOW CAP(F, R)
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)