Riešenie: Na overenie acyklickosti digrafu môžeme použiť napríklad nasledujúci postup. Keďže prameň nemôže byť súčasťou žiadného cyklu, tak z grafu odstránime všetky pramene s hranami, ktoré z nich vychádzajú. Toto opakujeme aj v postupne vznikajúcich poddigrafoch. Ak ostane len jeden vrchol, respektíve diskrétny graf, pôvodný digraf bol acyklický. Ideme teda postupnými odoberaniami prameňov overiť acyklickosť. Ako vidíme, ostal nám jediný vrchol, digraf je teda acyklický. Na topologické očíslovanie vrcholov použijeme ATO (viď cvičenie 4).

Riešenie: Keďže digraf je topologicky očíslovaný, nemusíme vrcholy preznačovať. Kvôli prehľadnosti zobrazenia nahradíme v diagrafe vrcholy väčšími trojpoľovými kruhmi, do ktorých budeme zapisovať \(v_i\) - označenie vrchola, \(a_i\) - jeho minimálne časové ohodnotenie, \(b_i\) - jeho maximálne časové ohodnotenie. Najprv použijeme algoritmus pre určenie minimálnych časových ohodnotení vrcholov. Tu už vieme povedať, že projekt bude trvať \(T=a_8=12\). Potom použijeme aj algoritmus pre maximálne časové ohodnotenie vrcholov. Vrcholy, pre ktoré platí, že \(a_i=b_i\) sú kritické. Kritickou nazývame tú hranu \(v_i=v_j\), pre ktorú sú oba vrcholy \(v_i,v_j\) kritické a navyše platí \(b_j-b_i=T_{i,j}\). Kritické vrcholy a kritické hrany vyznačíme v diagrame. Existuje jedna kritická cesta: \(v_1 - v_3 - v_6 - v_8\).

Riešenie: Topologicky očíslujeme vrcholy digrafu (ak by to nešlo, nie je acyklický) a znázorníme ich trojpoľovými kruhmi. Podobne ako v predchádzajúcej úlohe použijeme algoritmus na určenie minimálneho a potom aj maximálneho časového ohodnotenia vrcholov. Farebne vyznačíme kritické vrcholy a kritické hrany. Dĺžka trvania daného projektu je \(T=32\) a existujú tu dve kritické cesty:

• \(v_1 - v_4 - v_5 - v_6 - v_7 - v_9 - v_{12} - v_{14}\)
• \(v_1 - v_2 - v_3 - v_6 - v_7 - v_9 - v_{12} - v_{14}.\)

Riešenie: Je zjavné, že dané očíslovanie nie je topologické. Pomocou ATO prečíslujeme vrcholy digrafu takto: \(u_1\to v_{9}\), \(u_2\to v_{8}\), \(u_3\to v_{4}\), \(u_4\to v_{7}\), \(u_5\to v_{6}\), \(u_6\to v_{10}\), \(u_7\to v_{5}\), \(u_8\to v_{12}\), \(u_9\to v_{14}\), \(u_{10}\to v_{11}\), \(u_{11}\to v_{13}\), \(u_{12}\to v_{2}\), \(u_{13}\to v_{1}\), \(u_{14}\to v_{3}\). Dostaneme nasledujúce označenia vrcholov:

činnosť	\(v_9v_{12}\)	\(v_8v_{9}\)	\(v_8v_{10}\)	\(v_8v_{11}\)	\(v_4v_{6}\)	\(v_7v_{8}\)	\(v_6v_{9}\)
čas	\(1\)	\(4\)	\(5\)	\(2\)	\(2\)	\(6\)	\(2\)
činnosť	\(v_6v_{7}\)	\(v_{10}v_{13}\)	\(v_5v_{9}\)	\(v_5v_{12}\)	\(v_{12}v_{14}\)	\(v_{12}v_{13}\)	\(v_{11}v_{13}\)
čas	\(6\)	\(3\)	\(5\)	\(3\)	\(6\)	\(4\)	\(7\)
činnosť	\(v_{13}v_{14}\)	\(v_2v_{4}\)	\(v_2v_{7}\)	\(v_2v_{5}\)	\(v_1v_{4}\)	\(v_1v_{5}\)	\(v_1v_{2}\)
čas	\(8\)	\(5\)	\(4\)	\(4\)	\(3\)	\(8\)	\(4\)
činnosť	\(v_1v_{3}\)	\(v_3v_{6}\)	\(v_3v_{5}\)
čas	\(7\)	\(2\)	\(1\)

Pokúsime sa čo najprehľadnejšie znázorniť diagram daného projektu digramom. Použijeme metódu CPM a farebne vyznačíme kritické hrany aj kritické vrcholy. Dĺžka trvania daného projektu je \(T=40\) a existujú tu dve kritické cesty:

• \(v_1 - v_2 - v_4 - v_6 - v_7 - v_8 - v_9 - v_{12} - v_{13} - v_{14}\)
• \(v_1 - v_2 - v_4 - v_6 - v_7 - v_8 - v_{11} - v_{13} - v_{14}.\)

Riešenie: Priemernú dobu trvania \(\bar{t}\) vypočítame podľa vzorca \[\bar{t}=\frac{a+4\cdot m+b}{6},\] kde \(a\) je optimistický odhad, \(m\) je normálny odhad a \(b\) je pesimistický odhad doby trvania danej činnosti. Výsledky pre každú činnosť sú uvedené v nasledujúcej tabuľke.

činnosť	\(t_1t_2\)	\(t_1t_3\)	\(t_1t_4\)	\(t_2t_4\)	\(t_2t_6\)
priemerná doba	\(4\)	\(8\)	\(17\)	\(0\)	\(11\)
činnosť	\(t_2t_7\)	\(t_3t_4\)	\(t_3t_5\)	\(t_4t_5\)	\(t_4t_6\)
priemerná doba	\(6\)	\(5\)	\(12\)	\(4\)	\(7\)
činnosť	\(t_5t_8\)	\(t_6t_7\)	\(t_6t_8\)	\(t_7t_9\)	\(t_8t_9\)
priemerná doba	\(3\)	\(2\)	\(8\)	\(10\)	\(6\)

Riešenie: Dobu, za ktorú bude projekt ukončený s pravdepodobnosťou 50%, určíme pomocou metódy CPM, pričom za časové ohodnotenia jednotlivých činností (teda jednotlivých hrán) berieme priemerné doby trvania jednotlivých činností. Tie máme vypočítane v predchádzajúcej úlohe. Na zaklade daných údajov znázorníme daný projekt acyklickým digrafom. Ako môžeme vidieť v predchádzajúcej úlohe, očíslovanie vrcholov v zadaní je topologické, takže ho zachováme. Pomocou metódy CPM vypočítame dobu trvania projektu. Projekt bude s 50% pravdepodobnosťou ukončený za 38 týždňov.

Riešenie: Na vyriešenie tohoto problému použijeme Ford-Fulkersonov algoritmus. Jednotlivé kroky v iteráciách budeme zapisovať do tabuliek a pre názornosť aj znázorňovať diagramami. Použijeme nasledujúce symboly:

• PV - pole preskúmaných vrcholov (všetky označené vrcholy, ktorých aj susedia sú označení)
• NOV - pole nepreskúmaných označených vrcholov (majú pridelenú značku)
• NV - pole neoznačených vrcholov (nemajú pridelenú značku)
• \(x_i\to[x_j,\delta]\) - tok \(\xi\) môžeme zväčšiť po hrane \((x_j,x_i)\) o hodnotu \(\delta\).

Na začiatok najčastejšie berieme nulový tok, tak nech \(\xi=0\).

• 1. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(a\)	\([s,10]\)	\(b,c,d,e,f,g,t\)	\(a,s\)
  \(e\)	\([s,15]\)	\(b,c,d,f,g,t\)	\(e,a\)	\(s\)
  \(b\)	\([a,4]\)	\(c,d,f,g,t\)	\(b,e,a\)	\(s\)
  \(g\)	\([a,8]\)	\(c,d,f,t\)	\(g,b,e\)	\(a,s\)
  \(c\)	\([b,4]\)	\(d,f,t\)	\(c,b,g,e\)	\(a,s\)
  \(f\)	\([b,3]\)	\(d,t\)	\(f,c,g,e\)	\(b,a,s\)
  \(t\)	\([c,4]\)	\(d\)	\(t,f,g,e\)	\(c,b,a,s\)
  \(d\)	\([g,8]\)			\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok vypočítaný v 1. iterácii je \(\delta_1=4\) a sieť po 1. iterácii je nasledovná:
  
• 2. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(a\)	\([s,6]\)	\(b,c,d,e,f,g,t\)	\(a,s\)
  \(e\)	\([s,15]\)	\(b,c,d,f,g,t\)	\(e,a\)	\(s\)
  \(g\)	\([a,6]\)	\(b,c,d,f,t\)	\(g,e\)	\(a,s\)
  \(b\)	\([e,9]\)	\(c,d,f,t\)	\(g,b\)	\(e,a,s\)
  \(c\)	\([b,4]\)	\(d,f,t\)	\(c,b,g\)	\(e,a,s\)
  \(f\)	\([b,3]\)	\(d,t\)	\(f,c,g\)	\(b,e,a,s\)
  \(t\)	\([c,4]\)	\(d\)	\(t,f,g\)	\(c,b,e,a,s\)
  \(d\)	\([g,6]\)			\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok vypočítaný v 2. iterácii je \(\delta_2=4\) a sieť po 2. iterácii je nasledovná:
  
• 3. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(a\)	\([s,6]\)	\(b,c,d,e,f,g,t\)	\(a,s\)
  \(e\)	\([s,11]\)	\(b,c,d,f,g,t\)	\(e,a\)	\(s\)
  \(g\)	\([a,6]\)	\(b,c,d,f,t\)	\(g,e\)	\(a,s\)
  \(b\)	\([e,5]\)	\(c,d,f,t\)	\(g,b\)	\(e,a,s\)
  \(f\)	\([b,3]\)	\(c,d,t\)	\(f,g\)	\(b,e,a,s\)
  \(t\)	\([g,6]\)	\(c,d\)	\(t,f,g\)	\(b,e,a,s\)
  \(d\)	\([g,6]\)	\(c\)	\(d,t,f\)	\(g,c,b,e,a,s\)
  \(c\)	\([d,6]\)			\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok vypočítaný v 3. iterácii je \(\delta_3=6\) a sieť po 3. iterácii je nasledovná:
  
• 4. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(e\)	\([s,11]\)	\(a,b,c,d,f,g,t\)	\(e\)	\(s\)
  \(b\)	\([e,5]\)	\(a,c,d,f,g,t\)	\(b,e\)	\(s\)
  \(g\)	\([e,10]\)	\(a,c,d,f,t\)	\(g,b\)	\(e,s\)
  \(f\)	\([b,3]\)	\(a,c,d,t\)	\(f,g\)	\(b,e,s\)
  \(a\)	\([g,2]\)	\(c,d,t\)	\(a,f,g\)	\(b,e,s\)
  \(d\)	\([g,9]\)	\(c,t\)	\(d,a,f,g\)	\(b,e,s\)
  \(t\)	\([g,3]\)	\(c\)	\(t,d,a,f\)	\(g,b,e,s\)
  \(c\)	\([d,9]\)			\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok vypočítaný v 4. iterácii je \(\delta_4=3\) a sieť po 4. iterácii je nasledovná:
  
• 5. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(e\)	\([s,11]\)	\(a,b,c,d,f,g,t\)	\(e\)	\(s\)
  \(b\)	\([e,5]\)	\(a,c,d,f,g,t\)	\(b,e\)	\(s\)
  \(g\)	\([e,7]\)	\(a,c,d,f,t\)	\(g,b\)	\(e,s\)
  \(f\)	\([b,3]\)	\(a,c,d,t\)	\(f,g\)	\(b,e,s\)
  \(a\)	\([g,2]\)	\(c,d,t\)	\(a,f,g\)	\(b,e,s\)
  \(d\)	\([g,7]\)	\(c,t\)	\(d,a,f\)	\(g,b,e,s\)
  \(c\)	\([g,3]\)	\(t\)	\(c,a,f\)	\(d,g,b,e,s\)
  \(t\)	\([c,2]\)			\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok vypočítaný v 5. iterácii je \(\delta_5=2\) a sieť po 5. iterácii je nasledovná:
  
• 6. iterácia

  Vrchol	Značka vrchola	NV	NOV	PV
  \(s\)	\([s,\infty]\)	\(s,a,b,c,d,e,f,g,t\)	\(s\)
  \(e\)	\([s,11]\)	\(a,b,c,d,f,g,t\)	\(e\)	\(s\)
  \(b\)	\([e,5]\)	\(a,c,d,f,g,t\)	\(b,e\)	\(s\)
  \(g\)	\([e,7]\)	\(a,c,d,f,t\)	\(g,b\)	\(e,s\)
  \(f\)	\([b,3]\)	\(a,c,d,t\)	\(f,g\)	\(b,e,s\)
  \(a\)	\([g,2]\)	\(c,d,t\)	\(a,f,g\)	\(b,e,s\)
  \(d\)	\([g,7]\)	\(c,t\)	\(d,a,f\)	\(g,b,e,s\)
  \(c\)	\([d,7]\)	\(t\)	\(c,a,f\)	\(d,g,b,e,s\)
  		\(t\)		\(s,a,b,c,d,e,f,g,t\)

  Čiastkový tok \(\delta_6\) neexistuje, algoritmus je skončený.

Tranzitnú kapacitu tejto plynárenskej siete určíme ako výsledný maximálny tok \(\xi=\delta_1+\delta_2+\delta_3+\delta_4+\delta_5=4+4+6+3+2=19\).