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 | \]