1. zadatak¶
Projekt je prikazan pomoću usmjerene mreže $D$ pri čemu su vremena trajanja aktivnosti izražena u mjesecima.
- Koliko minimalno mjeseci traje projekt?
- Odredite kritični put.
- Koje se aktivnosti u projektu mogu odugovlačiti?
Out[4]:
Minimalno vrijeme trajanja projekta¶
In [5]:
nx.dag_longest_path_length(D)
Out[5]:
27
Kritični put¶
In [6]:
nx.dag_longest_path(D)
Out[6]:
['a', 'c', 'm', 'b', 'e']
Out[7]:
| vrh | a | b | c | d | e | h | m | n |
| V(v) | 0 | 20 | 3 | 5 | 27 | 12 | 11 | 1 |
| K(v) | 0 | 20 | 3 | 16 | 27 | 23 | 11 | 13 |
Out[8]:
| aktivnost | ('c', 'm') | ('c', 'h') | ('c', 'b') | ('m', 'b') | ('h', 'e') | ('b', 'e') | ('d', 'h') | ('d', 'b') | ('n', 'b') | ('a', 'c') | ('a', 'd') | ('a', 'n') |
| F(u,v) | 0 | 11 | 13 | 0 | 11 | 0 | 13 | 11 | 12 | 0 | 11 | 12 |
Sva topološka sortiranja (1 - 20)¶
Out[9]:
[['a', 'n', 'd', 'c', 'h', 'm', 'b', 'e'], ['a', 'n', 'd', 'c', 'm', 'b', 'h', 'e'], ['a', 'n', 'd', 'c', 'm', 'h', 'b', 'e'], ['a', 'n', 'c', 'm', 'd', 'b', 'h', 'e'], ['a', 'n', 'c', 'm', 'd', 'h', 'b', 'e'], ['a', 'n', 'c', 'd', 'h', 'm', 'b', 'e'], ['a', 'n', 'c', 'd', 'm', 'b', 'h', 'e'], ['a', 'n', 'c', 'd', 'm', 'h', 'b', 'e'], ['a', 'd', 'c', 'h', 'm', 'n', 'b', 'e'], ['a', 'd', 'c', 'h', 'n', 'm', 'b', 'e'], ['a', 'd', 'c', 'm', 'n', 'b', 'h', 'e'], ['a', 'd', 'c', 'm', 'n', 'h', 'b', 'e'], ['a', 'd', 'c', 'm', 'h', 'n', 'b', 'e'], ['a', 'd', 'c', 'n', 'h', 'm', 'b', 'e'], ['a', 'd', 'c', 'n', 'm', 'b', 'h', 'e'], ['a', 'd', 'c', 'n', 'm', 'h', 'b', 'e'], ['a', 'd', 'n', 'c', 'h', 'm', 'b', 'e'], ['a', 'd', 'n', 'c', 'm', 'b', 'h', 'e'], ['a', 'd', 'n', 'c', 'm', 'h', 'b', 'e'], ['a', 'c', 'm', 'n', 'd', 'b', 'h', 'e']]
Sva topološka sortiranja (21 - 37)¶
Out[10]:
[['a', 'c', 'm', 'n', 'd', 'h', 'b', 'e'], ['a', 'c', 'm', 'd', 'h', 'n', 'b', 'e'], ['a', 'c', 'm', 'd', 'n', 'b', 'h', 'e'], ['a', 'c', 'm', 'd', 'n', 'h', 'b', 'e'], ['a', 'c', 'n', 'd', 'h', 'm', 'b', 'e'], ['a', 'c', 'n', 'd', 'm', 'b', 'h', 'e'], ['a', 'c', 'n', 'd', 'm', 'h', 'b', 'e'], ['a', 'c', 'n', 'm', 'd', 'b', 'h', 'e'], ['a', 'c', 'n', 'm', 'd', 'h', 'b', 'e'], ['a', 'c', 'd', 'h', 'm', 'n', 'b', 'e'], ['a', 'c', 'd', 'h', 'n', 'm', 'b', 'e'], ['a', 'c', 'd', 'm', 'n', 'b', 'h', 'e'], ['a', 'c', 'd', 'm', 'n', 'h', 'b', 'e'], ['a', 'c', 'd', 'm', 'h', 'n', 'b', 'e'], ['a', 'c', 'd', 'n', 'h', 'm', 'b', 'e'], ['a', 'c', 'd', 'n', 'm', 'b', 'h', 'e'], ['a', 'c', 'd', 'n', 'm', 'h', 'b', 'e']]
2. zadatak¶
Zadana je transportna mreža i protok $\mathcal{F}$.
- Odredite vrijednost protoka $\mathcal{F}$.
- Ispitajte je li $\mathcal{F}$ maksimalni protok.
- Pronađite maksimalni protok u zadanoj transportnoj mreži i minimalni rez od izvora do ponora.
Out[11]:
Out[12]:
- $\mathop{\mathrm{val}}{\mathcal{F}}=17$
- $\mathcal{F}$ nije maksimalni protok jer postoji $\mathcal{F}$-rastući put $szyxwt$.
Out[13]:
- $\mathop{\mathrm{val}}{\mathcal{F}}=19$
- minimalni rez: S={s,z}, T={x,w,y,t}
- $\mathop{\mathrm{cap}}{(S,T)}=19$
3. zadatak¶
Pomoću Bellman-Fordovog algoritma pronađite najkraće putove od vrha a do svih preostalih vrhova u zadanom težinskom digrafu.
Out[15]:
Bellman-Ford (ručni postupak)¶
Out[16]:
| vrh | korak | 0 | 1 | 2 | 3 | 4 | 5 |
| a | (-,0) | (-,0) | (-,0) | (-,0) | (-,0) | (-,0) |
| b | (-,oo) | (a,3) | (c,0) | (c,0) | (c,0) | (c,0) |
| c | (-,oo) | (a,-1) | (a,-1) | (a,-1) | (a,-1) | (a,-1) |
| d | (-,oo) | (-,oo) | (c,3) | (b,2) | (b,2) | (b,2) |
| e | (-,oo) | (-,oo) | (c,5) | (d,0) | (d,-1) | (d,-1) |
Out[17]:
