Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete

Nech V je konečná neprázdna množina; jej prvky nazývame vrcholy.

1. Neorientovaný graf je dvojica G = (V, E), kde E ⊆ {{u, v} : u, v ∈ V, u ≠ v}; prvky E sú hrany — dvojprvkové podmnožiny V. Vrcholy u, v sú susedné práve vtedy, keď {u, v} ∈ E.
2. Orientovaný graf je dvojica G = (V, E), kde E ⊆ V × V; hrana je usporiadaná dvojica (u, v) — šípka z u do v. Orientovaný graf je teda relácia na V (pozri diel Množiny a relácie).
3. Ohodnotený graf je trojica G = (V, E, w), kde (V, E) je graf podľa 1. alebo 2. a w : E → ℝ je funkcia, ktorá každej hrane e ∈ E priradí váhu w(e) (dĺžku, cenu, čas).

Ak nie je povedané inak, je graf v tomto diele neorientovaný.

Nech G = (V, E) je neorientovaný graf a v ∈ V. Stupeň vrcholu v je počet hrán, ktoré ho obsahujú (ktoré z neho vychádzajú):

deg(v) = |{e ∈ E : v ∈ e}|.

Veta (o podávaní rúk). Nech G = (V, E) je neorientovaný graf. Potom

∑_{v ∈ V} deg(v) = 2 |E|.

Špeciálne je súčet stupňov v každom neorientovanom grafe párne číslo.

Veta. Nech G = (V, E) je neorientovaný graf a L = {v ∈ V : deg(v) je nepárne} množina jeho vrcholov nepárneho stupňa. Potom |L| je párne číslo.

Dôkaz. Rozdeľme súčet stupňov na vrcholy párneho a nepárneho stupňa: ∑_{v ∈ V} deg(v) = ∑_{v ∈ V ∖ L} deg(v) + ∑_{v ∈ L} deg(v). Ľavá strana je podľa vety o podávaní rúk 2|E|, párna; prvý súčet napravo je súčet párnych čísel, teda párny. Druhý teda musí byť tiež párny — a súčet |L| nepárnych čísel je párny práve vtedy, keď |L| je párne. ∎

Preto nejde nakresliť graf s piatimi vrcholmi, z ktorých každý má stupeň 3: súčet 15 by bol nepárny.

Nech G = (V, E, w) je ohodnotený neorientovaný graf s nenulovými váhami (w(e) ≠ 0 pre všetky e ∈ E) a n = |V| vrcholmi, ktoré očíslujeme: V = {v₁, …, v_n}. Matica susednosti grafu G je štvorcová matica A ∈ ℝ^n×n s prvkami (pre i, j = 1, …, n)

A_ij = w({v_i, v_j}), ak {v_i, v_j} ∈ E;   inak A_ij = 0.

Nenulové váhy sú potrebné, aby sa hrana dala odlíšiť od chýbajúcej hrany. Pri neohodnotenom grafe sa namiesto váhy píše 1. Keďže {v_i, v_j} = {v_j, v_i}, má neorientovaný graf A_ij = A_ji, teda A = A^T.

Pre v ∈ V označme N(v) množinu jeho susedov:

N(v) = {u ∈ V : {u, v} ∈ E}.

Zoznam susedov je zobrazenie, ktoré každému vrcholu v ∈ V priradí množinu N(v), pri ohodnotenom grafe aj s váhami: {(u, w({u, v})) : u ∈ N(v)}. Platí |N(v)| = deg(v).

Graf miest: matica má 7 · 7 = 49 buniek, z toho len 24 nenulových (každá cesta dvakrát, nad aj pod uhlopriečkou). Zoznamy susedov majú spolu ∑ deg(v) = 2 · 12 = 24 položiek (farby podľa vety o podávaní rúk vyššie). Riadok B matice je (4, 0, 5, 3, 7, 0, 0) — štyri nenulové čísla, pretože deg(B) = 4.

Cestná sieť s miliónom križovatiek, z každej v priemere 3 cesty: |E| = 10⁶ · 3/2 = 1,5 · 10⁶. Matica má (10⁶)² = 10¹² buniek, zoznamy len 2 · 1,5 · 10⁶ = 3 · 10⁶ položiek — vyše tristotisíckrát menej.

Nech G = (V, E) je neorientovaný graf a u, v ∈ V.

1. Cesta z u do v je postupnosť vrcholov (v₀, v₁, …, v_k), k ≥ 0, taká, že v₀ = u,   v_k = v,   v_i ≠ v_j pre i ≠ j,   {v_i−1, v_i} ∈ E pre i = 1, …, k. Jej dĺžka je k (počet hrán); v ohodnotenom grafe (V, E, w) je to súčet váh ∑_i=1^k w({v_i−1, v_i}).
2. Cyklus je postupnosť vrcholov (v₀, v₁, …, v_k) s k ≥ 3, v ktorej sú v₀, …, v_k−1 navzájom rôzne, v_k = v₀ a {v_i−1, v_i} ∈ E pre i = 1, …, k — cesta, ktorá sa po aspoň troch hranách vráti do východiskového vrcholu.
3. G je súvislý práve vtedy, keď ∀u, v ∈ V existuje cesta z u do v.
4. Definujme reláciu ∼ na V: u ∼ v práve vtedy, keď existuje cesta z u do v. Je to ekvivalencia (reflexívna vďaka ceste dĺžky 0, symetrická obrátením cesty, tranzitívna, pretože zo spojenia dvoch ciest sa dá vybrať cesta). Jej triedy ekvivalencie sú komponenty súvislosti G; tvoria teda rozklad V (pozri diel Množiny a relácie).

Graf je teda súvislý práve vtedy, keď má jediný komponent súvislosti.

Nech G = (V, E, w) je ohodnotený neorientovaný graf s nezápornými váhami, w : E → [0, ∞), a u, v ∈ V. Pre cestu π označme w(π) = ∑_{e ∈ π} w(e) jej dĺžku (súčet váh jej hrán). Vzdialenosť vrcholov u a v je

d(u, v) = min {w(π) : π je cesta z u do v},   ak existuje aspoň jedna taká cesta; inak d(u, v) = ∞.

Minimum existuje, pretože ciest v konečnom grafe je konečne veľa. Pre neohodnotený graf berieme w(e) = 1 pre všetky e ∈ E; vzdialenosť je potom najmenší počet hrán cesty z u do v.

Veta. Nech G = (V, E, w) je ohodnotený graf s nezápornými váhami, w : E → [0, ∞), štart ∈ V východiskový vrchol a d[·] odhady Dijkstrovho algoritmu spusteného zo štartu (opis vyššie). Potom pre každý vrchol u v okamihu, keď ho algoritmus uzavrie, platí

d[u] = d(štart, u).

Prečo: každá iná cesta do u musí niekde prvýkrát opustiť množinu uzavretých vrcholov, a to cez vrchol x, ktorého odhad je ≥ d[u] (inak by sme vybrali x, nie u). Zvyšok cesty z x do u má nezápornú dĺžku, takže celá cesta nie je kratšia než d[u]. ∎

So zápornou hranou táto úvaha padá — „zvyšok cesty“ by mohol dĺžku skrátiť. Pre záporné váhy je preto potrebný iný algoritmus (Bellman–Ford).

Nech G = (V, E) je neorientovaný graf.

1. G je les práve vtedy, keď neobsahuje žiadny cyklus (každý jeho komponent súvislosti je potom strom).
2. G je strom práve vtedy, keď je súvislý a neobsahuje žiadny cyklus.

Veta. Nech G = (V, E) je neorientovaný graf s n = |V| ≥ 1 vrcholmi. Potom sú nasledujúce tvrdenia ekvivalentné:

1. G je strom;
2. G je súvislý a |E| = n − 1;
3. G neobsahuje cyklus a |E| = n − 1;
4. ∀u, v ∈ V existuje práve jedna cesta z u do v.

Koreňový strom je dvojica (T, r), kde T = (V, E) je strom a r ∈ V vyznačený vrchol, koreň. Pre v ∈ V:

1. hĺbka h(v) je dĺžka (počet hrán) jedinej cesty z r do v; špeciálne h(r) = 0;
2. deti vrcholu v sú jeho susedia smerom od koreňa, t. j. vrcholy množiny {u ∈ N(v) : h(u) = h(v) + 1}; v je ich rodič;
3. v je list práve vtedy, keď nemá žiadne dieťa.

Veta. Nech T = (V, E) je strom s n = |V| ≥ 1 vrcholmi. Potom |E| = n − 1.

Lema: nech T je strom s aspoň dvoma vrcholmi. Potom T má list, t. j. vrchol stupňa 1. Dôkaz lemy: vezmeme najdlhšiu cestu v strome; jej koncový vrchol nemôže mať ďalšieho suseda mimo cesty (cesta by sa dala predĺžiť), ani na ceste (vznikol by cyklus) — má teda stupeň 1.

Dôkaz vety indukciou podľa n. Základ: strom s 1 vrcholom má 0 hrán. Krok: v strome s n + 1 vrcholmi odoberme list aj s jeho jedinou hranou. Zvyšok je stále súvislý a bez cyklov, teda strom s n vrcholmi, a podľa indukčného predpokladu má n − 1 hrán. Pôvodný strom ich mal o jednu viac, n. ∎

Nech G = (V, E, w) je súvislý ohodnotený neorientovaný graf.

1. Kostra grafu G je graf T = (V, F) s F ⊆ E, ktorý je strom — obsahuje všetky vrcholy G a len niektoré jeho hrany.
2. Váha kostry je w(T) = ∑_{e ∈ F} w(e).
3. Kostra T je minimálna práve vtedy, keď w(T) ≤ w(T′) pre každú kostru T′ grafu G.

Kruskalov algoritmus.

• Vstup: súvislý ohodnotený neorientovaný graf G = (V, E, w) s m = |E| hranami.
• Výstup: množina hrán F ⊆ E taká, že (V, F) je minimálna kostra G.

1. Zoraď hrany vzostupne podľa váhy: e₁, …, e_m s w(e₁) ≤ … ≤ w(e_m).
2. Polož F := ∅.
3. Pre i = 1, …, m: ak graf (V, F ∪ {e_i}) neobsahuje cyklus, polož F := F ∪ {e_i}; inak hranu e_i vynechaj.
4. Vráť F.

Zastavenie: algoritmus skončí po prejdení všetkých m hrán (smie skončiť skôr, len čo |F| = |V| − 1). Ide o pažravý algoritmus — v každom kroku berie najľahšiu prípustnú hranu a rozhodnutie už nemení — a predsa vždy nájde minimálnu kostru (veta nižšie).

Hrany zoradené podľa dĺžky (prijaté tučne): A–C (2), D–E (2), B–D (3), E–G (3), A–B (4), D–F (4), B–C (5), F–G (5), C–D (6), E–F (6), B–E (7), C–F (8).

Prvých šesť hrán sa prijme: A–C a D–E spoja dvojice, B–D pridá B k D–E, E–G pridá G a A–B prepojí skupinu {A, C} so skupinou {B, D, E, G}. D–F pripojí posledný vrchol F. Teraz sú už všetky vrcholy v jednom komponente, takže každá ďalšia hrana by spojila dva vrcholy toho istého komponentu — uzavrela by cyklus a algoritmus ju odmietne.

Dĺžka kostry: 2 + 2 + 3 + 3 + 4 + 4 = 18.

Nech G = (V, E, w) je súvislý ohodnotený neorientovaný graf. Rez je rozdelenie vrcholov na dve neprázdne časti S a V ∖ S, kde ∅ ≠ S ⊊ V. Hrana {u, v} ∈ E vedie cez rez práve vtedy, keď |{u, v} ∩ S| = 1 (jeden koniec v S, druhý mimo).

Veta. Nech (S, V ∖ S) je rez grafu G a e je hrana, ktorá vedie cez rez a má najmenšiu váhu zo všetkých hrán vedúcich cez tento rez. Potom existuje minimálna kostra G, ktorá hranu e obsahuje.

Dôkaz: vezmime ľubovoľnú minimálnu kostru T; ak obsahuje e, sme hotoví. Inak uvažujme T bez e. Pridaním e vznikne cyklus a ten musí rez prekročiť ešte raz, nejakou hranou f. Odobraním f dostaneme opäť kostru, s váhou w(T) + w(e) − w(f) ≤ w(T), pretože w(e) ≤ w(f). Je teda tiež minimálna a e obsahuje. ∎

Kruskal prijme hranu len vtedy, keď spája dva rôzne komponenty — a je to najľahšia hrana cez rez „jeden z tých komponentov proti zvyšku“, pretože všetky ľahšie už spracoval.

Nech G = (V, E) je orientovaný graf, E ⊆ V × V, s n = |V| vrcholmi.

1. Orientovaný cyklus je postupnosť vrcholov (v₀, v₁, …, v_k), k ≥ 1, taká, že (v_i−1, v_i) ∈ E pre i = 1, …, k a v_k = v₀ — po šípkach sa dá vrátiť do východiskového vrcholu.
2. G je orientovaný acyklický graf (DAG) práve vtedy, keď neobsahuje žiadny orientovaný cyklus.
3. Topologické usporiadanie grafu G je bijekcia π : V → {1, …, n} (poradie vrcholov) taká, že ∀(u, v) ∈ E : π(u) < π(v), t. j. každá hrana vedie zľava doprava — u je v poradí pred v.

Veta. Nech G = (V, E) je orientovaný graf. Potom G má topologické usporiadanie práve vtedy, keď je acyklický.

Vstupy x = 2, w = 0,5, b = −1, správna odpoveď y = 1, strata L = (ŷ − y)², σ(z) = 1/1 + e^−z.

Dopredu (v topologickom poradí): w · x = 1; z = 1 + (−1) = 0; ŷ = σ(0) = 0,5; L = (0,5 − 1)² = 0,25.

Dozadu (v obrátenom poradí; farby podľa rozboru reťazového pravidla nižšie): ∂L/∂ŷ = 2(ŷ − y) = −1; ∂ŷ/∂z = σ(z)(1 − σ(z)) = 0,25; ∂L/∂z = −1 · 0,25 = −0,25; ∂L/∂b = ∂L/∂z · 1 = −0,25; ∂L/∂w = ∂L/∂z · ∂z/∂w = −0,25 · 2 = −0,5 (∂z/∂w = x = 2).

Obe derivácie sú záporné: zväčšením w aj b sa strata zmenší — sieť sa posunie k odpovedi 1.