Riešenie: Najprv si označíme vrcholy a hrany daného grafu. Maticu incidencie označujeme \(A\). Počet jej riadkov zodpovedá počtu vrcholov grafu, počet stĺpcov zase počtu hrán v grafe. Na príslušné miesto \(a_{i,j}\) píšeme 1, ak \(i\)-tý vrchol inciduje s \(j\)-tou hranou. Ak nie, tak píšeme 0. Teda naša matica incidencie má 6 riadkov a 9 stĺpcov a vyzerá takto: \[A=\left ( \begin{array}{c} 1\\ 1\\ 0\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 0\\ 0\\ 1 \end{array} \begin{array}{c} 0\\ 0\\ 1\\ 1\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 1\\ 1 \end{array} \right ) \] Maticu susednosti označujeme \(B\). Je to štvorcová matica, v ktorej počet riadkov aj stĺpcov zodpovedá počtu vrcholov v grafe. Na mieste \(b_{i,j}\) píšeme 1, ak \(i\)-tý a \(j\)-tý vrchol incidujú. Ak nie, píšeme 0. V našom prípade to bude štvorcová matica rádu 6: \[B=\left ( \begin{array}{c} 0\\ 1\\ 0\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 1\\ 0\\ 1\\ 1\\ 1\\ 1 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 1\\ 1\\ 0\\ 1\\ 0\\ 1 \end{array} \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 1\\ 0 \end{array}\right ) \]

Riešenie: Matica susednosti má 7 riadkov aj stĺpcov, takže graf bude mať 7 vrcholov. Znázorníme najprv vrcholy a potom podľa príslušných miest v matici, kde \(b_{i,j}=1\), znázorníme hranu medzi \(i\)-tým a \(j\)-tým vrcholom.

Riešenie: Matica susednosti digrafu má 5 riadkov aj stĺpcov, takže digraf bude mať 5 vrcholov. Znázorníme najprv vrcholy a potom podľa príslušných miest v matici, kde \(b_{i,j}=1\), znázorníme hranu šípkou z \(i\)-tého vrcholu do \(j\)-tého vrcholu.

Riešenie: Matica incidencie \(A\) digrafu pozostáva z prvkov množiny {-1, 0, 1}. Počet jej riadkov zodpovedá počtu vrcholov digrafu, počet stĺpcov zase počtu hrán v digrafe. Na príslušné miesto \(a_{i,k}\) píšeme hodnoty nasledovne: \[a_{i,k}=\left\{ \begin{array}{l} 1\text{, ak } h_k = (v_i,v_j) \text{ pre nejaký vrchol}\ v_j\in V \\ -1\text{, ak } h_k = (v_j,v_i) \text{ pre nejaký vrchol}\ v_j\in V \\ 0\text{ v ostatných prípadoch. } \end{array}\right. \] Najprv teda označíme hrany v digrafe. Potom podľa predchádzajúceho pravidla zapíšeme maticu incidencie. Keďže digraf má 6 vrcholov a 11 hrán, matica incidencie bude mať rozmer \(6\times 11\) a vyzerá takto: \[A=\left ( \begin{array}{r} -1\\ 1\\ 0\\ 0\\ 0\\ 0 \end{array} \begin{array}{r} 1\\ 0\\ -1\\ 0\\ 0\\ 0 \end{array} \begin{array}{r} 1\\ 0\\ 0\\ -1\\ 0\\ 0 \end{array} \begin{array}{r} -1\\ 0\\ 0\\ 1\\ 0\\ 0 \end{array} \begin{array}{r} -1\\ 0\\ 0\\ 0\\ 0\\ 1 \end{array} \begin{array}{r} 0\\ -1\\ 1\\ 0\\ 0\\ 0 \end{array} \begin{array}{r} 0\\ 1\\ 0\\ 0\\ -1\\ 0 \end{array} \begin{array}{r} 0\\ -1\\ 0\\ 0\\ 0\\ 1 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ -1\\ 0\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ -1\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0\\ -1\\ 1 \end{array}\right ) \] Matica susednosti \(B\) digrafu pozostáva z núl a jednotiek. Počet jej riadkov aj stĺpcov zodpovedá počtu vrcholov v digrafe. Na príslušné miesto \(b_{i,j}\) píšeme hodnoty nasledovne: \[b_{i,j}=\left\{ \begin{array}{l} 1\text{, ak } (v_i,v_j)\in H \\ 0\text{ v ostatných prípadoch. } \end{array}\right. \] \[B=\left ( \begin{array}{r} 0\\ 1\\ 0\\ 1\\ 0\\ 1 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 0\\ 0\\ 1 \end{array} \begin{array}{r} 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{array} \begin{array}{r} 1\\ 0\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 1\\ 0\\ 0\\ 0\\ 1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right ) \]

Riešenie: Najprv zostrojíme maticu \(B^{(1)}= B+E\), kde \(E\) je jednotková matica takého rozmeru, ako \(B\). \[B^{(1)}=\left ( \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 0\\ 1 \end{array} \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 0\\ 1 \end{array}\right ) \] Postupne vypočítame \(B^{(2)},B^{(3)},B^{(4)}\) podľa pravidla \(B^{(k)}=B^{(k-1)}\cdot B^{(1)}\). Matice násobime klasickým násobením matíc s jedinou výnimkou, že pri sčítaní prvkov je \(1+1=1\), teda ako pri operácii "OR". Ak bude matica \(B^{(n-1)}\), čo je v našom prípade \(B^{(4)}\) tvorená samými jednotkami, graf je súvislý. Ak nie, nie je súvislý. Výpočtom dostaneme \[B^{(4)}=\left ( \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 0\\ 1 \end{array} \begin{array}{r} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 0\\ 1 \end{array}\right ) \] a teda graf nie je súvislý.

Riešenie: Najprv zostrojíme maticu \(B^{(1)}= B+E\). Potom postupne vypočítame matice \(B^{(2)},\dots,B^{(6)}\). \[B^{(1)}=\left ( \begin{array}{r} 1\\ 1\\ 0\\ 0\\ 0 \\0 \\0 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 0\\ 0 \\0 \\0 \end{array} \begin{array}{r} 0\\ 1\\ 1\\ 1\\ 0 \\0 \\0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 1\\ 1 \\1 \\0 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 1\\ 1 \\0 \\0 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 1\\ 0 \\1 \\1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0\\ 0 \\1 \\1 \end{array}\right ) ; B^{(2)}=\left ( \begin{array}{r} 1\\ 1\\ 1\\ 0\\ 0 \\0 \\0 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 0 \\0 \\0 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1 \\1 \\0 \end{array} \begin{array}{r} 0\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 1\\ 1 \\1 \\0 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 1\\ 0 \\1 \\1 \end{array}\right ) ; B^{(3)}=\left ( \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 0 \\0 \\0 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1 \\1 \\0 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 0\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 0\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array} \begin{array}{r} 0\\ 0\\ 1\\ 1\\1 \\1 \\1 \end{array}\right ) ; B^{(4)}=B^{(5)}=B^{(6)}=\left ( \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\ 1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\ 1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\ 1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1\\1 \\1 \end{array} \begin{array}{r} 1\\ 1\\ 1\\ 1\\ 1 \\1 \\1 \end{array}\right ) \]

1. Keďže matica \(B^{(n-1)}\), teda \(B^{(6)}\) je tvorená samými jednotkami, graf je súvislý.
2. Prvý krát sa riadok tvorený samými jednotkami nachádza v matici \(B^{(3)}\), takže polomer grafu je \(r=3\). Prvý krát je samými jednotkami tvorená matica \(B^{(4)}\), takže priemer grafu je \(P=4\). V matici \(B^{(3)}\) ako prvé jednotkové riadky vznikli riadky prislúchajúce vrcholom \(v_3, v_4\). Stred grafu je teda množina \(\{v_3, v_4\}\).
3. Dvojice vrcholov, ktorých vzdialenosť je práve 3 sú tie, ktorým v matici \(B^{(2)}\) prislúchajú nuly a v matici \(B^{(3)}\) jednotky. Sú to dvojice \(\{v_1,v_4\}, \{v_2, v_5\},\{v_2,v_6\},\{v_3,v_7\}, \{v_4,v_7\}\).
4. Dvojice vrcholov, ktorých vzdialenosť je viac ako 3 sú tie, ktorým v matici \(B^{(3)}\) prislúchajú nuly. Sú to dvojice \(\{v_1,v_5\}, \{v_1, v_6\},\{v_1,v_7\},\{v_2,v_7\}\).

Riešenie: Najprv potrebujeme zostrojiť maticu susednosti \(B\) a diagonálnu maticu \(D\), ktorej prvkami sú nuly a na hlavnej diagonále sú stupne príslušných vrcholov. \[B=\left ( \begin{array}{c} 0\\ 1\\ 1\\ 1\\ 1 \end{array} \begin{array}{c} 1\\ 0\\ 1\\ 1\\ 1 \end{array} \begin{array}{c} 1\\ 1\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 1\\ 1\\ 0\\ 0\\ 1 \end{array} \begin{array}{c} 1\\ 1\\ 0\\ 1\\ 0 \end{array}\right ) ; D=\left ( \begin{array}{c} 4\\ 0\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 4\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 2\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 3\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 3 \end{array}\right ) \] Vypočítame \(D-B\) a odstránime ľubovoľný \(i\)-tý riadok a taký istý \(i\)-tý stĺpec, čím dostaneme maticu \(D_i-B_i\). (Výhodné je odstrániť riadok a stĺpec tak, aby v matici ostalo čo najviac núl.) Determinant takto určenej matice \(D_i-B_i\) nám určuje počet kostier daného grafu. \[D-B=\left ( \begin{array}{r} 4\\ -1\\ -1\\ -1\\ -1 \end{array} \begin{array}{r} -1\\ 4\\ -1\\ -1\\ -1 \end{array} \begin{array}{r} -1\\ -1\\ 2\\ 0\\ 0 \end{array} \begin{array}{r} -1\\ -1\\ 0\\ 3\\ -1 \end{array} \begin{array}{r} -1\\ -1\\ 0\\ -1\\ 3 \end{array}\right ) ; D_i-B_i=\left ( \begin{array}{r} 4\\ -1\\ -1\\ -1 \end{array} \begin{array}{r} -1\\ 2\\ 0\\ 0 \end{array} \begin{array}{r} -1\\ 0\\ 3\\ -1 \end{array} \begin{array}{r} -1\\ 0\\ -1\\ 3 \end{array}\right ) ; |D_i-B_i|=\left | \begin{array}{r} 4\\ -1\\ -1\\ -1 \end{array} \begin{array}{r} -1\\ 2\\ 0\\ 0 \end{array} \begin{array}{r} -1\\ 0\\ 3\\ -1 \end{array} \begin{array}{r} -1\\ 0\\ -1\\ 3 \end{array}\right |=40 \] Daný graf má 40 rôznych kostier.

Riešenie:

1. Počet všetkých kostier digrafu určíme tak, že odstránime z digrafu orientácie všetkých hrán, čím dostaneme neorientovaný graf. A všetkých kostier daného digrafu určíme ako počet kostier grafu vzniknutého z digrafu odstránením orientácie. Keďže odstránením orientácie v našom digrafe dostaneme graf z predchádzajúcej úlohy, tak počet kostier daného digrafu je taký istý, ako počet kostier grafu z predchádzajúcej úlohy, teda 40.
2. Na určenie počtu koreňových kostier digrafu potrebujeme maticu susednosti \(B\) digrafu a diagonálnu maticu \(D^-\), ktorá má na hlavnej diagonále vnútorné stupne príslušných vrcholov, teda počet hrán vchádzajúcich do vrchola. \[B=\left ( \begin{array}{c} 0\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 1 \end{array} \begin{array}{c} 1\\ 1\\ 0\\ 1\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 0\\ 1 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right ) ; D^-=\left ( \begin{array}{c} 2\\ 0\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 1\\ 0\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 3\\ 0\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 2\\ 0 \end{array} \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right ) \] Zostrojíme maticu \(K=D^--B\). V nej vynecháme riadok a stĺpec prislúchajúci vrcholu, pre ktorý počet koreňových kostier počítame, v našom prípade \(v_2\). Z takto získanej matice vypočítame determinant a ten určuje počet kostier, ktorých je vrchol \(v_2\) koreňom. \[K=D^--B=\left ( \begin{array}{r} 2\\ -1\\ 0\\ -1\\ 0 \end{array} \begin{array}{r} 0\\ 1\\ 0\\ 0\\ -1 \end{array} \begin{array}{r} -1\\ -1\\ 3\\ -1\\ 0 \end{array} \begin{array}{r} 0\\ -1\\ 0\\ 2\\ -1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right ) ; K_2=\left ( \begin{array}{r} 2\\ 0\\ -1\\ 0 \end{array} \begin{array}{r} -1\\ 3\\ -1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 2\\ -1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0 \end{array}\right ) ; |K_2|=\left | \begin{array}{r} 2\\ 0\\ -1\\ 0 \end{array} \begin{array}{r} -1\\ 3\\ -1\\ 0 \end{array} \begin{array}{r} 0\\ 0\\ 2\\ -1 \end{array} \begin{array}{r} 0\\ 0\\ 0\\ 0 \end{array}\right |=0 \]
3. Počet všetkých koreňových kostier daného digrafu určíme tak, že pre každý vrchol \(v_i\) vypočítame počet kostier ako \(K_i\) podobne ako v predchádzajúcom odseku. Teda \(|K_1|=0\), \(|K_2|=0\), \(|K_3|=0\), \(|K_4|=0\) a \(|K_5|=12\). Počet všetkých koreňových kostier digrafu \(\vec{D}\) je 12.

Riešenie: Prvým krokom Kruskalovho algoritmu je zostrojiť diskrétny faktor grafu \(G_0\). Zoradíme hrany grafu do neklesajúcej postupnosti podľa ohodnotení hrán:
2,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,6,7,8,8,9,10.
Ako prvú pridáme k faktoru \(G_0\) hranu s najnižším ohodnotením, vznikne podgraf \(G_1\). Postupne berieme po jednej hrane s najnižším ohodnotením a pridávame k aktuálnemu podgrafu \(G_i\), no vždy testujeme, či nevznikne kružnica. Ak áno, hranu vynecháme a testujeme nasledujúcu. Nasledujúci obrázok ilustruje prvé tri kroky algoritmu. Keďže graf má \(12\) vrcholov, algoritmus bude končiť pridaním \(11\) hrán. Dostali sme minimálnu kostru (jednu z možných minimálnych kostier), ktorej súčet ohodnotení je \(35\). Podľa toho, pre ktoré z hrán sa rozhodneme, ak máme viac možností, môžeme dostať rozdielne kostry. No všetky musia byť minimálne, čo znamená, že súčet ich ohodnotení musí byť vždy \(35\).

Riešenie: V grafe označíme vrcholy. Prvým krokom je vrchol s najnižším označením, teda \(v_1\) a vznikne podgraf \(G_0\). Ako prvú pridáme k podgrafu \(G_0\) hranu s najnižším ohodnotením vychádzajúcu z \(v_1\), teda hranu \({v_1 v_4}\), Čím vznikne podgraf \(G_1\). Ďalej zoberieme hranu vychádzajúcu z už pridaných vrcholov ( \(v_1, v_4\) ), ktorá má najnižšie ohodnotenie, teda \({v_1 v_5}\) a vznikne \(G_1\). Postupne berieme po jednej hrane s najnižším ohodnotením vychádzajúcej z už pridaných vrcholov a pridávame k aktuálnemu podgrafu \(G_i\). Pri každom pridaní vždy testujeme, či nevznikne kružnica. Ak áno, hranu vynecháme a testujeme nasledujúcu. Nasledujúci obrázok ilustruje prvé tri kroky algoritmu. Keďže graf má \(12\) vrcholov, algoritmus bude končiť pridaním \(11\) hrán. Dostali sme minimálnu kostru, ktorej súčet ohodnotení je \(29\).

Riešenie: Digraf nazývame silne súvislým, ak medzi každými dvomi vrcholmi (v hocijakom poradí) existuje orientovaný sled. Teda z každého vrcholu sa vieme orientovanými hranami dostať so iného vrcholu v zmysle orientácie.
Tento graf nie je silne súvislý. Vrchol \(d\) je prameňom, všetky hrany z neho len vychádzajú. To znamená, že žiadne spojenie z nejakého vrcholu do vrcholu \(d\) neexistuje. Podobne je to s vrcholom \(e\). Vrchol \(e\) je ústím, všetky hrany do neho len vchádzajú. To znamená, že žiadne spojenie z nvrcholu \(d\) do nejakého iného vrcholu neexistuje.

Riešenie: Je veľa spôsobov, ako takúto orientáciu zvoliť. Spôsob, ktorý použijeme tu, pozostáva z toho, že najprv vyberieme v danom grafe Hamiltonovskú kružnicu (keďže graf je Hamoltonovský), na nej zvolíme orientáciu tak, aby sme dostali Hamiltonovský cyklus, čo nám zaručí, že sa z každého vrcholu dostaneme orientovaným sledom do ostatných. Orientáciu na ostatných hranách potom môžeme zvoliť hocijako.

Riešenie: Vieme, že acyklický digraf nemôže obsahovať prameň. Tento poznatok použijeme na postupné iterácie. Najprv teda v digrafe odstránime všetky pramene a hrany z nich vychádzajúce. V poddigrafe, ktorý sme po prvej iterácii dostali budeme pokračovať rovnako a potom znova a ... Skončíme vtedy, keď budeme jednoznačne vedieť, že digraf neobsahuje cyklus. Ako môžeme vidieť, daný digraf je acyklický.

Riešenie: Použijeme podobný spôsob, ako v predchádzajúcom prípade. Teda v digrafe odstránime všetky pramene a hrany z nich vychádzajúce a túto iteráciu v každom ďalšom vzniknutom poddigrafe budeme opakovať dovtedy, kým jednoznačne nebudeme vedieť rozhodnúť o cyklickosti. Dostali sme sa do situácie, kedy už nie je žiaden prameň, teda žiadna ďalšia iterácia nie je možná. Tento digraf tvorí cyklus dĺžky 5 a teda pôvodný digraf je cyklický.

Riešenie: Vrcholy si predbežne nejako značíme, aby sa príklad ľahšie zapisoval. Zapíšeme pod seba všetky vrcholy a vedľa nich počet hrán do nich vchádzajúcich. \[ \begin{array}{c} u_1\\ u_2\\ u_3\\ u_4\\ u_5\\ u_6 \\ u_7 \\ u_8 \\ u_9 \\ u_{10} \\ u_{11} \\ u_{12} \end{array} \left | \begin{array}{c} 1\\ 3\\ 2\\ 2\\ 0\\ 2 \\ 2\\ 2\\ 2\\ 1\\ 1\\ 2 \end{array} \right | \] Vrchol, ktorý má priradenú nulu, je zjavne prameňom, keďže do neho nevchádza žiadna hrana. Tento vrchol bude označený prvý, napr. \(v_1\). Všetkým vrcholom, do ktorých ide hrana z vrcholu \(v_1\), odpočítame od priradenej hodnoty jednotku. Zo zvyšných vrcholov zase vyberieme vrchol, ktorý má priradenú nulu, označíme ho \(v_2\) a pokračujeme ako pri prvom vrchole. Toto robíme dovtedy, kým neoznačíme všetky vrcholy. Ak sa stane, že v niektorom kroku budú k dispozícii dva pramene, volíme ten, ktorý má nižšie označenie. \[ \begin{array}{c} u_1\\ u_2\\ u_3\\ u_4\\ u_5\\ u_6 \\ u_7 \\ u_8 \\ u_9 \\ u_{10} \\ u_{11} \\ u_{12} \end{array} \left | \begin{array}{c} 1\\ 3\\ 2\\ 2\\ 0\\ 2 \\ 2\\ 2\\ 2\\ 1\\ 1\\ 2 \end{array} \right | \begin{array}{c} 0\\ 3\\ 2\\ 2\\ v_1\\ 1 \\ 2\\ 2\\ 2\\ 0\\ 1\\ 2 \end{array} \left | \begin{array}{c} v_2\\ 2\\ 2\\ 2\\ - \\ 0 \\ 2\\ 2\\ 2\\ 0\\ 1\\ 2 \end{array} \right | \begin{array}{c} - \\ 2\\ 2\\ 2\\ - \\ v_3 \\ 1\\ 2\\ 2\\ 0\\ 1\\ 2 \end{array} \left | \begin{array}{c} - \\ 1\\ 2\\ 2\\ - \\ - \\ 1\\ 2\\ 2\\ v_4\\ 0\\ 1 \end{array} \right | \begin{array}{c} - \\ 1\\ 2\\ 2\\ - \\ - \\ 0\\ 1\\ 2\\ - \\ v_5 \\ 0 \end{array} \left | \begin{array}{c} - \\ 0\\ 2\\ 2\\ - \\ - \\ v_6\\ 0\\ 2\\ - \\ - \\ 0 \end{array} \right | \begin{array}{c} - \\ v_7\\ 1\\ 2\\ - \\ - \\ - \\ 0\\ 2\\ - \\ - \\ 0 \end{array} \left | \begin{array}{c} - \\ - \\ 0\\ 2\\ - \\ - \\ - \\ v_8\\ 1\\ - \\ - \\ 0 \end{array} \right | \begin{array}{c} - \\ - \\ v_9\\ 1\\ - \\ - \\ - \\ - \\ 1\\ - \\ - \\ 0 \end{array} \left | \begin{array}{c} - \\ - \\ - \\ 1\\ - \\ - \\ - \\ - \\ 0\\ - \\ - \\ v_{10} \end{array} \right | \begin{array}{c} - \\ - \\ - \\ 0\\ - \\ - \\ - \\ - \\ v_{11}\\ - \\ - \\ - \end{array} \left | \begin{array}{c} - \\ - \\ - \\ v_{12}\\ - \\ - \\ - \\ - \\ - \\ - \\ - \\ - \end{array} \right | \] Podľa výsledkov algoritmu preznačíme vrcholy daného grafu a môžeme sa aj vizuálne presvedčiť, že číslovanie je topologické, teda každá hrana smeruje z vrchola s nižším označením do vrchola s vyšším označením.

Riešenie:

1. Dĺžkou cesty v hranovo ohodnotenom grafe (spojenia v hranovo ohodnotenom digrafe) rozumieme súčet ohodnotení všetkých hrán danej cesty (spojenia). Pod vzdialenosťou dvoch vrcholov v grafe (digrafe) rozumieme minimum zo všetkých dĺžok ciest (spojení) medzi danými dvomi vrcholmi. Ak sa teda pozrieme na daný graf, z vrcholu \(v_1\) do vrcholu \(v_4\) sa môžeme dostať viacerými cestami, no najmenší súčet dosiahnú dve cesty:
   \(v_1 - v_2 - v_3 - v_8 - v_4\) a
   \(v_1 - v_2 - v_7 - v_8 - v_4\)
   a to \(8\). Takže vzdialenosť vrcholov \(v_1\) a \(v_4\) je \(8\).
2. Najkratšiu vzdialenosť do nesusedného vrchola má vrchol \(v_5\) do vrchola \(v_8\). Je to cesta \(v_5 - v_7 - v_8\) a vzdialenosť je \(3\).

Riešenie: Použijeme Dijkstrov algoritmus, ktorý bol popísaný na prednáške. Zapíšeme pod seba vrcholy grafu, vedľa nich dáme znaky nekonečna, okrem vrcholu \(g\), v ktorom pred prvou iteráciou sme a teda vzdialenosť \(g - g\) je \(0\). Po ďalších iteráciách budú pribúdať hodnoty ďalších vzdialeností. \[ \begin{array}{c} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \end{array} \left | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ 0 \\ \infty \\ \infty \end{array} \right | \] Jednotlivé iterácie pozostávejú z nasledujúceho postupu. Za východiskový vyberieme vrchol, ktorý má po predchádzajúcom kroku priradenú najmenšiu hodnotu. Pre každú hranu vychádzajúcu z daného vrcholu sčítame hodnotu aktuálne prislúchajúcu danému vrcholu a ohodnotenie hrany. Ak je výsledok menší ako hodnota pri vrchole, do ktorého táto hrana ide, hodnotu nahradíme výsledkom súčtu. V opačnom prípade hodnotu ponecháme. Východiskový vrchol už ďalej neberieme do úvahy. Takto pokračujeme, kým neprejdeme všetky vrcholy. Posledné im pridelené hodnoty sú hľadanými vzdialenosťami z \(g\) do príslušných vrcholov. \[ \begin{array}{c} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \end{array} \left | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ 0 \\ \infty \\ \infty \end{array} \right | \begin{array}{c} \infty \\ \infty \\ \infty \\ 5 \\ 5 \\ 7 \\ - \\ \infty \\ \infty \end{array} \left | \begin{array}{c} 7 \\ \infty \\ 10 \\ - \\ 5 \\ 7 \\ - \\ 11 \\ \infty \end{array} \right | \begin{array}{c} 7 \\ 10 \\ 10 \\ - \\ - \\ 7 \\ - \\ 9 \\ 9 \end{array} \left | \begin{array}{c} - \\ 10 \\ 10 \\ - \\ - \\ 7 \\ - \\ 9 \\ 9 \end{array} \right | \begin{array}{c} - \\ 10 \\ 10 \\ - \\ - \\ - \\ - \\ 9 \\ 9 \end{array} \left | \begin{array}{c} - \\ 10 \\ 10 \\ - \\ - \\ - \\ - \\ - \\ 9 \end{array} \right | \begin{array}{c} - \\ 10 \\ 10 \\ - \\ - \\ - \\ - \\ - \\ - \end{array} \left | \begin{array}{c} - \\ - \\ 10 \\ - \\ - \\ - \\ - \\ - \\ - \end{array} \right | \]

Riešenie: Podobne ako pri grafoch, vieme zistiť vzdialenosť dvoch vrcholov v digrafe, musíme len rešpektovať orientáciu hrán, teda uvažujeme spojenia. Keďže graf je len \(6\)-vrcholový, pokúsime sa vzdialenosti určiť bez použitia nejakého algoritmu: \(d_w(v_1,v_2)=\infty\), \(d_w(v_1,v_3)=13\), \(d_w(v_1,v_4)=\infty\), \(d_w(v_1,v_5)=11\), \(d_w(v_1,v_6)=4\) \(d_w(v_4,v_1)=5\), \(d_w(v_4,v_2)=\infty\), \(d_w(v_4,v_3)=18\), \(d_w(v_4,v_5)=16\), \(d_w(v_4,v_6)=9\). Môžeme si všimnúť, že v digrafoch vzdialenosť dvoch vrcholov nie je komutatívna. Napríklad \(d_w(v_1,v_4)=\infty\), \(d_w(v_4,v_1)=5\), teda \(d_w(v_1,v_4)\neq d_w(v_4,v_1)\).

Riešenie: Podobne, ako už vo vyššie popísanej úlohe, zapíšeme pod seba vrcholy digrafu, vedľa nich dáme znaky nekonečna, okrem vrcholu \(h\), v ktorom pred prvou iteráciou sme. \[ \begin{array}{c} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \end{array} \left | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ 0 \\ \infty \end{array} \right | \] Jednotlivé iterácie pozostávajú z takého istého postupu, ako pri grafoch. Len berieme ohľad na orientáciu hrán. A tiež, ako pri grafoch, posledné hodnoty pridelené vrcholom sú hľadanými vzdialenosťami z \(h\) do príslušných vrcholov. \[ \begin{array}{c} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \end{array} \left | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ 0 \\ \infty \end{array} \right | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ \infty \\ 8 \\ \infty \\ - \\ 4 \end{array} \left | \begin{array}{c} \infty \\ \infty \\ \infty \\ \infty \\ 8 \\ 8 \\ \infty \\ - \\ - \end{array} \right | \begin{array}{c} \infty \\ 13 \\ \infty \\ \infty \\ - \\ 8 \\ \infty \\ - \\ - \end{array} \left | \begin{array}{c} \infty \\ 13 \\ 14 \\ \infty \\ - \\ 8 \\ \infty \\ - \\ - \end{array} \right | \begin{array}{c} \infty \\ - \\ 14 \\ \infty \\ - \\ - \\ 15 \\ - \\ - \end{array} \left | \begin{array}{c} \infty \\ - \\ - \\ \infty \\ - \\ - \\ 15 \\ - \\ - \end{array} \right | \begin{array}{c} \infty \\ - \\ - \\ 20 \\ - \\ - \\ - \\ - \\ - \end{array} \left | \begin{array}{c} 22 \\ - \\ - \\ - \\ - \\ - \\ - \\ - \\ - \end{array} \right | \]

Riešenie: Z definície eulerovského grafu vieme, že graf sa nazýva eulerovský, ak všetky jeho stupne sú párneho stupňa. Skontrolujeme teda stupne oboch grafov. Ako je to znázornené na predchádzajúcom obrázku, v grafe \(G_1\) máme aj vrcholy stupňa \(3\), teda nepárne. To znamená, že graf \(G_1\) nie je eulerovský. Naopak, graf \(G_2\) má vrcholy len stupňov \(2\) a \(4\), teda je eulerovský.

Riešenie: Graf \(G_1\) je eulerovský, pretože všetky jeho vrcholy majú párny stupeň. Keďže je eulerovský, dá sa pokryť jedným uzavretým ťahom. Samotné pokrytie (nakreslenie diagramu jedným ťahom) uzavretým ťahom nechávame na čitateľa.
Graf \(G_2\) nie je eulerovský, keďže obsahuje dva vrcholy nepárneho stupňa. Nedá sa ani pokryť uzavretým ťahom, pretože eulerovskosť je nutnou podmienkou pokrytia grafu jedným uzavretým ťahom. No tento graf, keďže má práve dva vrcholy nepárneho stupňa, dá sa pokryť otvoreným ťahom. Musíme však začať v jednom z týchto vrcholov a skončiť v druhom. To nech čitateľ tiež vyskúša sám.

Riešenie: Vyriešiť problém okružnej cesty (známy tiež pod názvom problém poštára) znamená zistiť, ako prejsť všetkými hranami a vrátiť sa do východzieho bodu tak, aby ohodnotenie výsledného sledu bolo čo najmenšie.
V eulerovskom grafe to nie je žiaden problém, stačí pokryť graf uzavretým ťahom. Keďže daný graf je eulerovský, ohodnotenie výsledného sledu bude súčet ohodnotení všetkých hrán, a to \(56\).

Riešenie: Tento graf nie je eulerovský, takže sa nedá pokryť uzavretým ťahom. Vrcholy \(C\) a \(E\) majú nepárny stupeň. Ak teda chceme začať okružnú cestu v nejakom vrchole, prejsť všetky hrany a vrátiť sa späť, tak musíme niektoré hrany prejsť dvakrát. Konktétne cestu z vrcholu \(C\) do vrcholu \(E\). Pomocou napríklad Dijkstrovho algoritmu (viď cvičenie 4), nájdeme najkratšiu cestu z \(C\) do \(E\). Je to cesta \(C-F-H-E\) a jej dĺžka je \(10\). K súčtu ohodnotení všetkých hrán daného grafu: \(89\) pripočítame toto číslo a dostaneme \(99\), čo je dĺžka hľadanej minimálnej okružnej cesty.

Riešenie: Graf nie je eulerovský, má \(4\) vrcholy nepárneho stupňa :\(C, D, E, F\). Ak teda chceme začať okružnú cestu v tomto grafe, tak musíme niektoré hrany prejsť dvakrát. Otázkou je, ako máme poprepájať nepárne vrcholy tak, aby súčet ohodnotení vybraných ciest bol najmenší.
Všetkých dvojíc ciest je \(3\), sú to: \(CD,EF\), \(CE,DF\) a \(CF,DE\). Pomocou napríklad Dijkstrovho algoritmu (viď cvičenie 4), nájdeme najkratšie cesty z pre každú dvojicu vrcholov nepárneho stupňa:

\(CD\)	\(CE\)	\(CF\)	\(DE\)	\(DF\)	\(EF\)
\(3\)	\(4\)	\(6\)	\(4\)	\(7\)	\(4\)

Naše tri možnosti dvojíc ciest budú mať nasledujúce hodnoty:

\(CD, EF\)	\(CE, DF\)	\(CF, DE\)
\(7\)	\(11\)	\(10\)

Pridanie hrán na minimálnych cestách medzi dvojicami vrcholov \(CD, EF\) je najvýhodnejšie. Súčet všetkých ohodnotení hrán v grafe je \(40\) a minimálna okružná cesta má hodnotu \(40+7=47\).

Riešenie: Ani tento graf nie je eulerovský, má až \(6\) vrcholov nepárneho stupňa :\(B, C, F, G, L, P\). Podobne ako v dvoch predchádzajúcich príkladoch pre nájdenie minimálnej okružnej cesty musíme niektoré hrany prejsť dvakrát. Dvakrát budeme musieť prejsť hrany troch dvojíc týchto vrcholov, pre ktoré je súčet ohodnotení hrán minimálnych ciest minimálny.
Zostrojíme teda všetkých \(15\) možných trojíc zostavených z dvojíc vrcholov nepárneho stupňa a priradíme im minimálne dĺžky určené napríklad Dijkstrovým algoritmom.

\(BC, FG, LP\)	\(BC, FL, GP\)	\(BC, FP, GL\)	\(BF, CG, LP\)	\(BF, CL, GP\)
\(5, 9, 9\)	\(5, 11, 4\)	\(5, 11, 13\)	\(15, 16, 9\)	\(15, 6, 4\)
\(BF, CP, GL\)	\(BG, CF, LP\)	\(BG, CL, FP\)	\(BG, CP, FL\)	\(BL, CF, GP\)
\(15, 12, 13\)	\(11, 11, 9\)	\(11, 6, 11\)	\(11, 12, 11\)	\(11, 11, 4\)
\(BL, CG, FP\)	\(BL, CP, FG\)	\(BP, CF, GL\)	\(BP, CG, FL\)	\(BP, CL, FG\)
\(11, 16, 11\)	\(11, 12, 9\)	\(7, 11, 13\)	\(7, 16, 11\)	\(7, 6, 9\)

Najmenší súčet dáva trojica \(BC, FL, GP\) a to \(20\). Súčet všetkých ohodnotení hrán v grafe je \(122\) a minimálna okružná cesta má hodnotu \(122+20=142\).

Riešenie: Graf \(G_1\) obsahuje kompletný graf \(K_4\) ako podgraf. Pre vrcholové farbenie kompletných grafov platí, že na regulárne zafarbenie grafu \(K_n\) je nutných \(n\) farieb. Na zafarbenie grafu \(G_1\) ich teda potrebujeme aspoň \(4\). Ako vidieť na nasledujúcom obrázku, \(4\) farby stačia na zafarbenie \(G_1\) a teda chromatické číslo \(\chi (G_1) = 4\). Graf \(G_2\) obsahuje len kružnice párnej dĺžky, pokúsime sa ho zafarbiť dvomi farbami. Ako je znázornené v nasledujúcom diagrame, \(2\) farby postačujú a \(\chi (G_2) = 2\). V grafe \(G_3\) sú kružnice nepárnej dĺžky, je teda jasné, že na zafarbenie potrebujeme aspoň \(3\) farby. Pokúsime sa to tromi farbami zafarbiť. Tak ako je to v nasledujúcom diagrame znázornené, \(3\) farby stačia a \(\chi (G_3) = 3\).

Riešenie: Chromatický index grafu \(\bar{\chi} (G)\) je minimálny počet farieb potrebných na regulárne hranové zafarbenie grafu \(G\). Pre chromatický index platí nasledujúca nerovnosť: \(\Delta(G)\leq \bar{\chi}(G)\leq \Delta(G)+1\), kde \(\Delta(G)\) je maximálny stupeň vrchola v grafe. Odtiaľ je zrejme, že chromatický index grafu \(G_1\) je \(4\) alebo \(5\), chromatický index grafu \(G_2\) je \(5\) alebo \(6\) a chromatický index grafu \(G_3\) je \(3\) alebo \(4\). Skúsime tieto grafy hranovo regulárne zafarbiť menším z možných čísel, ak sa to dá. Ako vidieť na predchádzajúcom diagrame, v grafoch \(G_1, G_2\) je potrebný počet farieb rovný najvyššiemu stupňu, no v grafe \(G_3\) potrebujeme jednu farbu navyše. A teda:
\(\bar{\chi} (G_1)=4\),
\(\bar{\chi} (G_2)=5\),
\(\bar{\chi} (G_3)=4\).

Riešenie: Most v grafe je definovaný "hrana daného grafu, ktorá nepatrí žiadnej kružnici". Z toho vyplýva, že most je takou hranou, ktorej odstránením dostaneme podgraf obsahujúci viac komponentov, ako pôvodný graf. Daný graf je súvislý, teda odstránením mosta, by sme mali dostať nesúvislý podgraf. Tomu vyhovujú dve hrany, ktoré sú mostami: \(\{a,b\}\) a \(\{f,j\}\).

Riešenie: Artikuláciou v grafe rozumieme "vrchol daného grafu, ktoreho odstránením dostaneme podgraf obsahujúci viac komponentov, ako pôvodný graf". Daný graf je súvislý, teda odstránením artikulácie, by sme mali dostať nesúvislý podgraf. Artikuláciami v uvedenom grafe sú vrcholy: \(a,b,c,f\).

Riešenie: Riešením môžu byť rôzne grafy, každý si môže zvoliť rôzny. Tu uvedieme len nejaké príklady:

1. Nasledujúci graf obsahuje jednu artikuláciu, žiaden most.
   
2. Vrcholy incidujúce s mostom sú zároveň artikuláciami, výnimkou je visiaci vrchol. Preto jediným možným súvislým grafom obsahujúcim most a nie artikulácie je cesta na dvoch vrcholoch.
3. Tento graf obsahuje dva mosty a dve artikulácie.
   

Riešenie: Pravidelný súvislý graf 3. stupňa znamená, že všetky vrcholy budú mať stupeň 3 a má ich byť 16. Bez mosta to môže byť napríklad uvedený graf \(G_1\), s jedným mostom napríklad graf \(G_2\). Odporúčame však čitateľovi zostrojiť si nejaký vlastný graf s danými vlastnosťami.

Riešenie: V grafe \(G_1\) neplatí žiadna z nám známych postačujúcich podmienok pre hamiltonovskosť. To však neznamená, že graf nemôže byť hamiltonovský. Pokúsime sa tomto grafe regulárne zafarbiť všetky vrcholy čo najmenším počtom farieb. Daný graf sa nám podarilo zafarbiť dvoma farbami. Počet vrcholov označených 1 je 6, počet vrcholov označených 2 je 5. Keďže susedné vrcholy majú vždy iné číslo, ak by existovala hamiltonovská kružnica, museli by sa v nej dvojky a jednotky striedať. No pretože jednotiek a dvoják nie je rovnaký počet, takáto kružnica nemôže existovať a graf nie je hamiltonovský. Jednou z možných postačujúcich podmienok na hamiltonovskosť grafov je, aby všetky vrcholy v grafe s n vrcholmi mali stupeň aspoň \(n/2\). Graf \(G_2\) túto podmienku spĺňa. Má 8 vrcholov a každý vrchol má stupeň 4. Teda graf je hamiltonovský a existuje v ňom napríklad takáto hamiltonovská (obsahujúca všetky vrcholy) kružnica: Platí tiež veta, že ak v súvislom grafe vieme odstrániť \(m\) vrcholov tak, že vznikne aspoň \(m+1\) komponentov, tak graf nie je hamiltonovský. V grafe \(G_3\) vieme odstrániť dva vrcholy tak, že nám vzniknú tri komponenty, preto tento graf nie je hamiltonovský.

Riešenie: Zostrojíme rozhodovací strom z vrcholu \(F\) (keďže je výhodné začať z vrcholu s najnižším stupňom). Postupovať budeme tak, že z vrcholu naznačíme hrany do všetkých susedných vrcholov, ak už v ceste nie sú uvedené. Potom z každého ďalšieho naznačíme každého jeho suseda,... Ako je vidieť v strome, existujú tu len dve hamiltonovské kružnice:

• \(k_1\): \(FABCDEF\)
• \(k_2\): \(FADCBEF\)

Dĺžku kružnice \(k_1\) vypočítame ako súčet ohodnotení jej hrán, teda \(18+6+2+10+12+2=50\). Podobne dĺžka kružnice \(k_2\) je \(18+4+10+2+8+2=44\). Cestou pre obchodného cestujúceho je teda kružnica \(k_2\) (keďže je kratšia) a jej dĺžka je \(44\).

Riešenie: Vieme, že graf je súvislý a planárny, teda pre počet hrán \(|H|\), počet vrcholov \(|V|\) a počet oblastí \(r\) platí vzťah: \(|V|-|H|+2=r\). Ďalej vieme, že odstránením 5 hrán dostaneme kostru, teda je to minimálny počet hrán, ktoré musíme odstrániť, aby sme zrušili všetky kružnice v grafe, čo znamená, že 5 je vlastne cyklomatické číslo grafu \(\mu =5\). Z vlastností planárnych grafov tiež vieme, že platí \(r=\mu +1\), teda \(r = 5 + 1 = 6\). Dosadením dostaneme: \(|H|-11+2=6\) a teda počet hrán daného grafu \(|H|=15\).

Riešenie: Overiť, resp. dokázať planárnosť grafu znamená nájsť nejaký jeho diagram bez pretínajúcich sa hrán. Ako možno vidieť na nasledujúcom obrázku, tento graf je planárny, pretože jeho diagram sa dá prekresliť tak, aby sa hrany nepretínali.

Riešenie: Keď sa pozrieme na diagram grafu, vidíme, že obsahuje len jeden priesečník hrán, no odstrániť ho nejde. Tento graf nie je planárny a dokážeme to použitím Kuratowského vety, ktorá hovorí o tom, že graf je planárny práve vtedy, ak neobsahuje podgraf homeomorfný s \(K_5\) ani s \(K_{3,3}\). Vieme z grafu vybrať podgraf, ktorý je homeomorfný s \(K_5\). Nahradením hrán \({a,e}\) a \({a,b}\) hranou \({e,b}\) a postupne nahradením hrán \({b,c}; {c,d}; {d,h}\) hranou \({b,h}\) dostaneme graf izomorfný s \(K_5\), teda z grafu sa dá vybrať podgraf homeomorfný s \(K_5\), čo znamená, že graf nie je planárny.

Riešenie: Podobne ako v predchádzajúcom príklade sa pokúsime z grafu vybrať podgraf homeomorfný s \(K_{3,3}\) alebo \(K_5\). Podgraf \(G´\) na nasledujúcom obrázku je podgrafom pôvodného grafu. Odstránením vrcholov stupňa \(2\) a ich nahradením hranami dostaneme graf \(K_{3,3}\). To je dôkazom toho, že daný graf nie je planárny.

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: Ľahko môžeme overiť, že digraf je acyklický a očíslovanie vrcholov je topologické. Pre všetky hrany vypočítame priemernú dobu trvania danej činnosti. Použitím CPM nájdeme kritickú cestu v digrafe. \(T=53,2\) a to je čas, za ktorý sa projekt skončí s pravdepodobnosťou 50%. Kritická cesta je \(v_1 - v_2 - v_3 - v_6 - v_7 - v_{10}\). Pre všetky kritické hrany \(v_i - v_j\)vypočítame \(\sigma^2_{i,j}\) podľa vzorca \[\sigma^2=\frac{(b-a)^2}{36},\] takže: \(\sigma^2_{1,2}=\frac{49}{36}\), \(\sigma^2_{2,3}=\frac{25}{36}\), \(\sigma^2_{3,6}=\frac{16}{36}\), \(\sigma^2_{6,7}=\frac{64}{36}\), \(\sigma^2_{7,10}=\frac{64}{36}\), potom \(\sigma=\sqrt{\frac{218}{36}}\doteq2,46\).

• Poznáme tieto veličiny: \(T=53,2\); \(X=60\); \(\sigma=2,46\). Dosadením do vzorca \[u=\frac{X-T}{\sigma}\] vypočítame hodnotu distribučnej funkcie \(u\) a k nej prislúchajúcu pravedpodobnosť: \[u\doteq2,76\ \Rightarrow \ \phi(u)=0,99711\sim 99,711\%.\] Za 60 týždňov bude daný projekt ukončený s pravdepodobnosťou 99,711%.
• Keďže chceme určiť čas, za ktorý sa projekt uskutoční s pravdepodobnosťou 90%, tak \(\phi(u)=0,9\). K tejto hodnote vyhľadáme prislúchajúcu hodnotu distribučnej funkcie, takže \(u=1,28\). Z vyššie uvedeného vzorca vyjadríme \(X\) \[X=\sigma u +T\] a vypočítame \(X=56,34\). Daný projekt bude s pravdepodobnosťou 90% ukončený za 56,34 týždňa.

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\).

Riešenie:

1. Predpokladajme, že \(A=(a_{ij}), \, B=(b_{ij})\) sú \(n\times n\) matice. Potom pre ich súčinovú maticu \(C=(c_{ij})\) platí: \[c_{ij}=\sum\limits_{k=1}^n a_{ik}\times b_{kj}.\]
2. Počet operácií \(+\) pre výpočet jedného elementu \(c_{ij}\) je \(n-1\).
3. Počet operácií \(\times \) pre výpočet jedného elementu \(c_{ij}\) je \(n\).
4. Celkový počet operácií pre výpočet jedného elementu \(c_{ij}\) je \(n-1+n=2n-1\).
5. Celkový počet operácií pre výpočet všetkých elementov matice \(C\) je \(n^2(2n-1)\).

Riešenie:

1. Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Potom pre jej \(p-\)tú mocninu \(A^p=(a^{(p)}_{ij})\) platí: \[a^{(p)}_{ij}=\sum\limits_{k=1}^n a^{(p-1)}_{ik}\,a_{kj}.\] Vytvoríme postupnosť \(A,\,A^2,\,\ldots \,,\,A^{p}\).
2. Podľa predchádzajúceho príkladu počet operácií potrebných na výpočet súčinu dvoch štvorcových \(n\times n\) matíc je \(n^2(2n-1)\).
3. Počet násobení matíc je \(p-1\).
4. Celkový počet operácií pre výpočet matice \(A^p\) je \((p-1)n^2(2n-1)\).

Riešenie:

1. Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Podľa predchádzaj[úceho príkladu je počet operácií potrebných na vytvorenie postupnosti za sebou idúcich mocnín zadanej matice \(A,\,A^2,\,\ldots \,,\,A^{n}\) daný hodnotou \((n-1)n^2(2n-1)\).
2. Počet operácií \(\oplus\) pre výpočet jedného prvku metrickej matice \(\gamma_{ij}\) je daný hodnotou \(n-1\).
3. Celkový počet operácií \(\oplus\) potrebných na výpočet všetkých prvkov metrickej matice je \(n^2(n-1)\).
4. Celkový počet operácií na výpočet metrickej matice \(\Gamma(A)\) je \((n-1)n^2(2n-1)+n^2(n-1)\).

Riešenie:

1. Počet uzavretých ciest, ktoré obchádzajú všetky mestá práve raz je \(\frac{(n-1)!}{2}\).
2. Počet operácií \(+\)potrebných na výpočet váhy jednej cesty je \(n-1\).
3. Počet operácií potrebných na výpočet váh všetkých ciest je \(\frac{(n-1)(n-1)!}{2}\).
4. Počet operácií porovnania dvoch prvkov potrebných na výber najmenšieho prvku je \(\frac{(n-1)!}{2}-1\).
5. Celkový počet operácií potrebných na nájdenie uzavretej cesty s minimálnou váhou, ktorá obchádza všetky mestá práve raz, je \(\frac{(n-1)(n-1)!}{2}+(\frac{(n-1)!}{2}-1)\).

Jedná sa o neefektívny algoritmus, pretože je počet operácií potrebných na vyriešenie TSP-problému popísaným spôsobom vyjadrený pomocou faktoriálu. Medzi neefektívne algoritmy radíme aj tie, ktoré vyžadujú exponenciálny počet operácií.

Riešenie:

1. Predpokladajme, že \(A=(a_{ij}), \, B=(b_{ij})\) sú \(n\times n\) matice. Potom pre ich súčinovú maticu \(C=(c_{ij})\) platí: \[c_{ij}=\sum\limits_{k=1}^n a_{ik}\times b_{kj}.\]
2. Počet operácií \(+\) pre výpočet jedného elementu \(c_{ij}\) je \(n-1\). Výpočtová zložitosť je \(O(n)\).
3. Počet operácií \(\times \) pre výpočet jedného elementu \(c_{ij}\) je \(n\). Výpočtová zložitosť je \(O(n)\).
4. Celkový počet operácií pre výpočet jedného elementu \(c_{ij}\) je \(n-1+n=2n-1\). Výpočtová zložitosť je \(O(n)\).
5. Celkový počet operácií pre výpočet všetkých elementov matice \(C\) je \(n^2(2n-1)\). Celková výpočtová zložitosť popísaného algoritmu je preto \(O(n^3)\).

Riešenie:

1. Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Potom pre jej \(p-\)tú mocninu \(A^p=(a^{(p)}_{ij})\) platí: \[a^{(p)}_{ij}=\sum\limits_{k=1}^n a^{(p-1)}_{ik}\,a_{kj}.\] Vytvoríme postupnosť \(A,\,A^2,\,\ldots \,,\,A^{p}\).
2. Podľa predchádzajúceho príkladu počet operácií potrebných na výpočet súčinu dvoch štvorcových \(n\times n\) matíc je \(n^2(2n-1)\). Výpočtová zložitosť je \(O(n^3)\).
3. Počet násobení matíc je \(p-1\). Celkový počet operácií pre výpočet matice \(A^p\) je teda \((p-1)n^2(2n-1)\). Celková výpočtová zložitosť popísaného algoritmu je \(O(pn^3)\).

Riešenie:

1. Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Podľa predchádzajúceho príkladu je počet operácií potrebných na vytvorenie postupnosti za sebou idúcich mocnín zadanej matice \(A,\,A^2,\,\ldots \,,\,A^{n}\) daný hodnotou \((n-1)n^2(2n-1)\). Výpočtová zložitosť tohto kroku je \(O(n^4)\).
2. Počet operácií \(\oplus\) pre výpočet jedného prvku metrickej matice \(\gamma_{ij}\) je daný hodnotou \(n-1\). Výpočtová zložitosť je \(O(n)\).
3. Celkový počet operácií \(\oplus\) potrebných na výpočet všetkých prvkov metrickej matice je \(n^2(n-1)\). Výpočtová zložitosť kroku je \(O(n^3)\).
4. Celkový počet operácií na výpočet metrickej matice \(\Gamma(A)\) je \((n-1)n^2(2n-1)+n^2(n-1)\). Celková výpočtová zložitosť popísaného algoritmu je \(O(n^4)\).

Riešenie:

1. Vypočítame limitu \[\lim\limits_{n\rightarrow \infty}\frac{\left(\ln n\right)^k}{n^\varepsilon}= \left(\lim\limits_{n\rightarrow \infty}\frac{\ln n}{n^{\frac{\varepsilon}{k}}}\right)^k= \left(\lim\limits_{n\rightarrow \infty}\frac{\frac{1}{n}}{\frac{\varepsilon}{k}n^{\frac{\varepsilon}{k}-1}}\right)^k= \left(\frac{k}{\varepsilon}\lim\limits_{n\rightarrow \infty}\frac{1}{n^{\frac{\varepsilon}{k}}}\right)^k=0\]
2. Stačí položiť \(c=1\) a tvrdenie platí pre všetky \(k\in N\) a pre všetky \(\varepsilon>0.\)

Riešenie:

1. Predpokladajme, že graf \(G=(V,E)\) je reprezentovaný maticou susednosti \(A=(a_{ij})\), kde \(a_{ij}=1\), ak \((v_i,v_j)\in E\) a \(a_{ij}=0\), inak.
2. Potom veľkosťou vstupu môže byť množina \(|E|=n^2\), ale často sa z dôvodu riedkych matíc pri charakterizácii grafových algoritmov používa dvojica \(|V|=n, |E|=n^2\).
3. Celkový počet operácií potrebných na výpočet objektu grafového problému je možné vyjadriť ako násobok hodnôt \( O(|V|)\) alebo \(O(|E|)\).

Riešenie: Môžu nastať nasledujúce prípady:

1. Predpokladajme, že \(n\) je nepárne číslo a \(n\) nie je prvočíslo. Potom \(f(n)=n^3\) a \(g(n)=n^2\). Pre \(c=1\) platí \(g(n)=O(f(n)).\) Naviac, neexistuje \(c> 0\), ktoré nie je funkciou \(n\) a také, že \(n^3=O(n^2)\).
2. Predpokladajme, že \(n\) je nepárne číslo a \(n\) je prvočíslo. Potom \(f(n)=n^2\) a \(g(n)=n^2\). Pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)
3. Predpokladajme, že \(n\) je párne číslo a \(n\) je prvočíslo. Jediné číslo splňajúce podmienku prepokladu je \(n=2\). V tomto prípade pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)
4. Predpokladajme, že \(n\) je párne číslo a \(n\) nie je prvočíslo. Potom \(f(n)=n^3\) a \(g(n)=n^3\). Pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)

Riešenie: Floydov-Warshallov algoritmus

1. Vstup: \(n\times n\) matica \((c_{ij})\) s nezápornými vstupmi
2. Výstup: \(n\times n\) matica \((d_{ij})\), kde \(d_{ij}\) je najkratšia vzdialenosť z vrchola \(i\) do vrchola \(j\).
3. begin
4. for all \(i\neq j\) do \(d_{ij}:=c_{ij}\);
5. for\(i=1,2,\dots,n\) do \(d_{ii}:=\infty\);
6. for\(j=1,2,\dots,n\) do
7. for \(i=1,2,\dots,n,\ i\neq j\) do
8. for \(k=1,2,\dots,n,\ k\neq j\) do
9. \(d_{ik}:=\min\{d_{ik},d_{ij}+d_{jk}\}\)
10. end .

Floydov-Warshallov algoritmus pre problém najkratšej cesty má zložitosť \(O(|V|^3)\), teda na dosiahnutie výsledku v najhoršom prípade spotrebuje \(O(|V|^3)\) operácií. Analýza algoritmu je ľahká, pretože kľúčovým pozorovaním je fakt, že algoritmus obsahuje tri zahniezdené slučky (cykly), pričom každá z nich je vykonávaná v čase \(O(|V|)\).