Grafy a stromy: struktura, na které stojí hledání i neuronové sítě

Nechť V je konečná neprázdná množina; její prvky nazýváme vrcholy.

1. Neorientovaný graf je dvojice G = (V, E), kde E ⊆ {{u, v} : u, v ∈ V, u ≠ v}; prvky E jsou hrany — dvouprvkové podmnožiny V. Vrcholy u, v jsou sousední, právě když {u, v} ∈ E.
2. Orientovaný graf je dvojice G = (V, E), kde E ⊆ V × V; hrana je uspořádaná dvojice (u, v) — šipka z u do v. Orientovaný graf je tedy relace na V (viz díl Množiny a relace).
3. Ohodnocený graf je trojice G = (V, E, w), kde (V, E) je graf podle 1. nebo 2. a w : E → ℝ je funkce, která každé hraně e ∈ E přiřadí váhu w(e) (délku, cenu, čas).

Kde není řečeno jinak, je v tomto díle graf neorientovaný.

Nechť G = (V, E) je neorientovaný graf a v ∈ V. Stupeň vrcholu v je počet hran, které ho obsahují (které z něj vycházejí):

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

Věta (o podávání rukou). Nechť G = (V, E) je neorientovaný graf. Pak

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

Speciálně je součet stupňů v každém neorientovaném grafu sudé číslo.

Věta. Nechť G = (V, E) je neorientovaný graf a L = {v ∈ V : deg(v) je liché} množina jeho vrcholů lichého stupně. Pak |L| je sudé číslo.

Důkaz. Rozdělme součet stupňů na vrcholy sudého a lichého stupně: ∑_{v ∈ V} deg(v) = ∑_{v ∈ V ∖ L} deg(v) + ∑_{v ∈ L} deg(v). Levá strana je podle věty o podávání rukou 2|E|, sudá; první součet napravo je součet sudých čísel, tedy sudý. Druhý tedy musí být sudý také — a součet |L| lichých čísel je sudý, právě když |L| je sudé. ∎

Proto nejde nakreslit graf s pěti vrcholy, z nichž každý má stupeň 3: součet 15 by byl lichý.

Nechť G = (V, E, w) je ohodnocený neorientovaný graf s nenulovými vahami (w(e) ≠ 0 pro všechna e ∈ E) a n = |V| vrcholy, které očíslujeme: V = {v₁, …, v_n}. Matice sousednosti grafu G je čtvercová matice A ∈ ℝ^n×n s prvky (pro i, j = 1, …, n)

A_ij = w({v_i, v_j}), je-li {v_i, v_j} ∈ E;   jinak A_ij = 0.

Nenulové váhy jsou potřeba, aby se hrana dala odlišit od chybějící hrany. U neohodnoceného grafu se místo váhy píše 1. Protože {v_i, v_j} = {v_j, v_i}, má neorientovaný graf A_ij = A_ji, tedy A = A^T.

Pro v ∈ V označme N(v) množinu jeho sousedů:

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

Seznam sousedů je zobrazení, které každému vrcholu v ∈ V přiřadí množinu N(v), u ohodnoceného grafu i s vahami: {(u, w({u, v})) : u ∈ N(v)}. Platí |N(v)| = deg(v).

Graf měst: matice má 7 · 7 = 49 buněk, z toho jen 24 nenulových (každá silnice dvakrát, nad i pod úhlopříčkou). Seznamy sousedů mají dohromady ∑ deg(v) = 2 · 12 = 24 položek (barvy podle věty o podávání rukou výše). Řádek B matice je (4, 0, 5, 3, 7, 0, 0) — čtyři nenulová čísla, protože deg(B) = 4.

Silniční síť s milionem křižovatek, z každé v průměru 3 silnice: |E| = 10⁶ · 3/2 = 1,5 · 10⁶. Matice má (10⁶)² = 10¹² buněk, seznamy jen 2 · 1,5 · 10⁶ = 3 · 10⁶ položek — přes třistatisíckrát méně.

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

1. Cesta z u do v je posloupnost vrcholů (v₀, v₁, …, v_k), k ≥ 0, taková, že v₀ = u,   v_k = v,   v_i ≠ v_j pro i ≠ j,   {v_i−1, v_i} ∈ E pro i = 1, …, k. Její délka je k (počet hran); v ohodnoceném grafu (V, E, w) je to součet vah ∑_i=1^k w({v_i−1, v_i}).
2. Cyklus je posloupnost vrcholů (v₀, v₁, …, v_k) s k ≥ 3, ve které jsou v₀, …, v_k−1 navzájem různé, v_k = v₀ a {v_i−1, v_i} ∈ E pro i = 1, …, k — cesta, která se po aspoň třech hranách vrátí do výchozího vrcholu.
3. G je souvislý, právě když ∀u, v ∈ V existuje cesta z u do v.
4. Definujme relaci ∼ na V: u ∼ v, právě když existuje cesta z u do v. Je to ekvivalence (reflexivní díky cestě délky 0, symetrická obrácením cesty, tranzitivní, protože ze spojení dvou cest lze vybrat cestu). Její třídy ekvivalence jsou komponenty souvislosti G; tvoří tedy rozklad V (viz díl Množiny a relace).

Graf je tedy souvislý, právě když má jedinou komponentu souvislosti.

Nechť G = (V, E, w) je ohodnocený neorientovaný graf s nezápornými vahami, w : E → [0, ∞), a u, v ∈ V. Pro cestu π označme w(π) = ∑_{e ∈ π} w(e) její délku (součet vah jejích hran). Vzdálenost vrcholů u a v je

d(u, v) = min {w(π) : π je cesta z u do v},   existuje-li aspoň jedna taková cesta; jinak d(u, v) = ∞.

Minimum existuje, protože cest v konečném grafu je konečně mnoho. Pro neohodnocený graf bereme w(e) = 1 pro všechna e ∈ E; vzdálenost je pak nejmenší počet hran cesty z u do v.

Věta. Nechť G = (V, E, w) je ohodnocený graf s nezápornými vahami, w : E → [0, ∞), start ∈ V výchozí vrchol a d[·] odhady Dijkstrova algoritmu spuštěného ze startu (popis výše). Pak pro každý vrchol u v okamžiku, kdy ho algoritmus uzavře, platí

d[u] = d(start, u).

Proč: každá jiná cesta do u musí někde poprvé opustit množinu uzavřených vrcholů, a to přes vrchol x, jehož odhad je ≥ d[u] (jinak bychom vybrali x, ne u). Zbytek cesty z x do u má nezápornou délku, takže celá cesta není kratší než d[u]. ∎

Se zápornou hranou tahle úvaha padá — „zbytek cesty“ by mohl délku zkrátit. Pro záporné váhy je proto potřeba jiný algoritmus (Bellman–Ford).

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

1. G je les, právě když neobsahuje žádný cyklus (každá jeho komponenta souvislosti je pak strom).
2. G je strom, právě když je souvislý a neobsahuje žádný cyklus.

Věta. Nechť G = (V, E) je neorientovaný graf s n = |V| ≥ 1 vrcholy. Pak jsou následující tvrzení ekvivalentní:

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

Kořenový strom je dvojice (T, r), kde T = (V, E) je strom a r ∈ V vyznačený vrchol, kořen. Pro v ∈ V:

1. hloubka h(v) je délka (počet hran) jediné cesty z r do v; speciálně h(r) = 0;
2. děti vrcholu v jsou jeho sousedé směrem od kořene, tj. vrcholy množiny {u ∈ N(v) : h(u) = h(v) + 1}; v je jejich rodič;
3. v je list, právě když nemá žádné dítě.

Věta. Nechť T = (V, E) je strom s n = |V| ≥ 1 vrcholy. Pak |E| = n − 1.

Lemma: nechť T je strom s aspoň dvěma vrcholy. Pak T má list, tj. vrchol stupně 1. Důkaz lemmatu: vezmeme nejdelší cestu ve stromu; její koncový vrchol nemůže mít dalšího souseda mimo cestu (cesta by šla prodloužit), ani na cestě (vznikl by cyklus) — má tedy stupeň 1.

Důkaz věty indukcí podle n. Základ: strom s 1 vrcholem má 0 hran. Krok: ve stromu s n + 1 vrcholy odeberme list i s jeho jedinou hranou. Zbytek je pořád souvislý a bez cyklů, tedy strom s n vrcholy, a podle indukčního předpokladu má n − 1 hran. Původní strom jich měl o jednu víc, n. ∎

Nechť G = (V, E, w) je souvislý ohodnocený neorientovaný graf.

1. Kostra grafu G je graf T = (V, F) s F ⊆ E, který je strom — obsahuje všechny vrcholy G a jen některé jeho hrany.
2. Váha kostry je w(T) = ∑_{e ∈ F} w(e).
3. Kostra T je minimální, právě když w(T) ≤ w(T′) pro každou kostru T′ grafu G.

Kruskalův algoritmus.

• Vstup: souvislý ohodnocený neorientovaný graf G = (V, E, w) s m = |E| hranami.
• Výstup: množina hran F ⊆ E taková, že (V, F) je minimální kostra G.

1. Seřaď hrany vzestupně podle váhy: e₁, …, e_m s w(e₁) ≤ … ≤ w(e_m).
2. Polož F := ∅.
3. Pro i = 1, …, m: neobsahuje-li graf (V, F ∪ {e_i}) cyklus, polož F := F ∪ {e_i}; jinak hranu e_i vynech.
4. Vrať F.

Zastavení: algoritmus skončí po projití všech m hran (smí skončit dřív, jakmile |F| = |V| − 1). Jde o hladový algoritmus — v každém kroku bere nejlehčí přípustnou hranu a rozhodnutí už nemění — a přesto vždy najde minimální kostru (věta níže).

Hrany seřazené podle délky (přijaté tučně): 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).

Prvních šest hran se přijme: A–C a D–E spojí dvojice, B–D přidá B k D–E, E–G přidá G a A–B propojí skupinu {A, C} se skupinou {B, D, E, G}. D–F připojí poslední vrchol F. Teď už jsou všechny vrcholy v jedné komponentě, takže každá další hrana by spojila dva vrcholy téže komponenty — uzavřela by cyklus a algoritmus ji odmítne.

Délka kostry: 2 + 2 + 3 + 3 + 4 + 4 = 18.

Nechť G = (V, E, w) je souvislý ohodnocený neorientovaný graf. Řez je rozdělení vrcholů na dvě neprázdné části S a V ∖ S, kde ∅ ≠ S ⊊ V. Hrana {u, v} ∈ E vede přes řez, právě když |{u, v} ∩ S| = 1 (jeden konec v S, druhý mimo).

Věta. Nechť (S, V ∖ S) je řez grafu G a e je hrana, která vede přes řez a má nejmenší váhu ze všech hran vedoucích přes tento řez. Pak existuje minimální kostra G, která hranu e obsahuje.

Důkaz: vezměme libovolnou minimální kostru T; obsahuje-li e, jsme hotovi. Jinak uvažujme T bez e. Přidáním e vznikne cyklus a ten musí řez překročit ještě jednou, nějakou hranou f. Odebráním f dostaneme zase kostru, s vahou w(T) + w(e) − w(f) ≤ w(T), protože w(e) ≤ w(f). Je tedy také minimální a e obsahuje. ∎

Kruskal přijme hranu jen tehdy, když spojuje dvě různé komponenty — a je to nejlehčí hrana přes řez „jedna z těch komponent proti zbytku“, protože všechny lehčí už zpracoval.

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

1. Orientovaný cyklus je posloupnost vrcholů (v₀, v₁, …, v_k), k ≥ 1, taková, že (v_i−1, v_i) ∈ E pro i = 1, …, k a v_k = v₀ — po šipkách se dá vrátit do výchozího vrcholu.
2. G je orientovaný acyklický graf (DAG), právě když neobsahuje žádný orientovaný cyklus.
3. Topologické uspořádání grafu G je bijekce π : V → {1, …, n} (pořadí vrcholů) taková, že ∀(u, v) ∈ E : π(u) < π(v), tj. každá hrana vede zleva doprava — u je v pořadí před v.

Věta. Nechť G = (V, E) je orientovaný graf. Pak G má topologické uspořádání, právě když je acyklický.

Vstupy x = 2, w = 0,5, b = −1, správná odpověď y = 1, ztráta L = (ŷ − y)², σ(z) = 1/1 + e^−z.

Dopředu (v topologickém pořadí): w · x = 1; z = 1 + (−1) = 0; ŷ = σ(0) = 0,5; L = (0,5 − 1)² = 0,25.

Pozpátku (v obráceném pořadí; barvy podle rozboru řetízkového pravidla níže): ∂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).

Obě derivace jsou záporné: zvětšením w i b se ztráta zmenší — síť se posune k odpovědi 1.