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