Grafová teorie

DVOP PIT


Bc. Matěj Cajthaml — SSPŠ

©

Neorientovaný graf

Uspořadáná $n$-tice

  • $N = (a, b, c, d, e, ...)$
  • záleží na pořadí — každý prvek
    má jméno a pozici
  • obsahuje právě $n$ prvků
  • prvky se mohou opakovat
  • $(a, b) \neq (b, a)$ (nemusí být komutativní)

Množina

  • $M = \{a, b, c, d, e, ...\}$
  • nezáleží na pořadí — každý prvek
    má pouze jméno
  • prvky se nemohou opakovat
  • $\{a, b\} = \{b, a\}$ (musí být komutativní)

Neorientovaný graf

  • Neorientovaný graf je uspořadaná dvojice
    $G = (V, E)$, kde:
    • $V$ je neprázdná množina vrcholů
    • $E$ je množina hran
    • $E \subseteq \{\{u, v\} | u, v \in V\}$
      • $E$ obsahuje spojení vrcholů, které jsou v $V$

Ukázka grafu

$G_1 = (\{a, b, c\}, \{\{a, b\}, \{c, a\}\})$

                    graph LR
                        a((a)) --- b((b))
                        a --- c((c))

Nápady na alternativní zápis?

Proč v definici nepoužíváme v množině hran uspořádanou dvojici?

Může být v grafu s $V = \{a, b, c\}$ hrana $\{a, a\}$? Proč?

Kolik hran?

Práce

Kolik hran může mít maximálně graf s $3$ vrcholy?

Kolik hran může mít maximálně graf s $4$ vrcholy?

Kolik hran může mít maximálně graf s $n$ vrcholy?

Speciální grafy

Úplný graf

$K_n = (V, E)$, kde
$V = \{v_1, v_2, ..., v_n\}$ a
$E = \{\{v_i, v_j\} | v_i, v_j \in V\}$


$K_4$:

                    graph LR
                        1((1)) --- 2((2))
                        1 --- 3((3))
                        1 --- 4((4))
                        2 --- 4
                        2 --- 3
                        3 --- 4

Cesta

$P_n = (V, E)$, kde
$V = \{v_1, v_2, ..., v_n\}$ a
$E = \{\{v_i, v_{i+1}\} | v_i, v_{i+1} \in V\}$


$P_4$:

                    graph LR
                        1((1)) --- 2((2))
                        2 --- 3((3))
                        3 --- 4((4))

Kružnice

$C_n = (V, E)$, kde
$V = \{v_1, v_2, ..., v_n\}$ a
$E = \{\{v_i, v_{i+1}\} | v_i, v_{i+1} \in V\} \cup \{\{v_1, v_n\}\}$


$C_4$:

                    graph LR
                        1((1)) --- 2((2))
                        2 --- 3((3))
                        3 --- 4((4))
                        4 --- 1

Hvězda

$S_n = (V, E)$, kde
$V = \{v_1, v_2, ..., v_n\}$ a
$E = \{\{v_1, v_i\} | v_i \in V \land i > 1\}$


$S_6$:

                    graph TD
                        1((1)) --- 4((4))
                        1 --- 5((5))
                        1 --- 2((2))
                        1 --- 3((3))
                        1 --- 6((6))

Značení

Množiny

Nechť $G = (V, E)$ je graf. Pak:

$V(G)$ je množina vrcholů grafu $G$

$E(G)$ je množina hran grafu $G$

$|V(G)|$ je počet vrcholů grafu $G$

$|E(G)|$ je počet hran grafu $G$

Sousedé

Nechť $G = (V, E)$ je graf a $e = \{u, v\} \in E$. Pak:

$u$ je soused $v$

$v$ je soused $u$

Doplňek grafu

Nechť $G = (V, E)$ je graf. Pak:

$\overline{G} = (V, \overline{E})$, kde
$\overline{E} = \{\{u, v\} | u, v \in V \land \{u, v\} \notin E\}$

$\overline{G}$ je doplněk grafu $G$.

Tedy: $\overline{G}$ obsahuje všechny hrany, které $G$ neobsahuje

Doplňte

Práce

Jednotlivým grafům níže vytvořite doplněk grafu.

$G_1$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 3((3))
                                4((4))

$G_2$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 3((3))
                                3 --- 4((4))
                                4 --- 1

$G_3$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 1
                                2 --- 3((3))
                                3 --- 1
                                3 --- 2
                                4 --- 1
                                3 --- 4((4))

Okolí a stupeň

Okolí

Nechť $G = (V, E)$ je graf a $v \in V$. Pak:

$N(v) = \{u \in V | \{u, v\} \in E\}$

$N(v)$ je okolí vrcholu $v$ a reprezentuje množinu všech vrcholů, které jsou s $v$ spojeny hranou.

Obsahuje okolí vrcholu $v$ — $N(v)$ i vrchol $v$?

Stupeň

Nechť $G = (V, E)$ je graf a $v \in V$. Pak:

$d(v) = |N(v)|$

$d(v)$ je stupeň vrcholu $v$ a reprezentuje počet hran, které jsou s $v$ spojeny.

Sousednost

  • sousedy lze reprezentovat z $E$
  • pomocí tabulky sousednosti
    • $1$ = je soused
    • $0$ = není soused
    • diagonála je vždy $0$
    • lze spočítat stupeň

Tabulka sousednosti

Například:

1 2 3 4
1 0 1 0 1
2 1 0 0 0
3 0 0 0 0
4 1 0 0 0

Podgrafy

Podgraf

Nechť $G = (V_G, E_G)$ a $H = (V_H, E_H)$ je graf. Pak:

$H$ je podgraf grafu $G$ právě tehdy, když $V_H \subseteq V_G$ a $E_H \subseteq E_G$.

Podgraf

$G = (\{1, 2, 3, 4\}, \{\{1, 2\},\{2, 3\}, \{3, 4\}, \{4, 1\}\})$

$H = (\{1, 2, 3\}, \{\{1, 2\}, \{2, 3\}\})$

                    graph LR
                        1((1)) -.- 2((2))
                        2 -.- 3((3))
                        3 --- 4((4))
                        4 --- 1
                    
                        style 1 fill:#cd8f41,stroke:#333,stroke-width:4px
                        style 2 fill:#cd8f41,stroke:#333,stroke-width:4px
                        style 3 fill:#cd8f41,stroke:#333,stroke-width:4px

$H$ je podgraf $G$.

Mějme $G = (\{1, 2, 3\}, \{\{1, 2\}, \{3, 1\}\})$ a $H = (\{1, 2\}, \{\}\})$.
Je $H$ podgrafem $G$?

Souvislost

Cesta v grafu

Nechť $G = (V, E)$ je graf a $v_1, v_2, \dots, v_n \in V$. Pak:

$\{v_a, v_b, \dots, v_m\}$ je cesta v grafu $G$ právě tehdy, když $\{v_a, v_b\}, \{v_b, v_c\}, \dots, \{v_{m-1}, v_m\} \in E$.

Délka cesty

Nechť $G = (V, E)$ je graf a $v_1, v_2, \dots, v_n \in V$. Pak:

Délka cesty $\{v_a, v_b, \dots, v_m\}$ je $m - 1$.

Tedy: počet hran v cestě.

Cyklus

Nechť $G = (V, E)$ je graf a $v_1, v_2, \dots, v_n \in V$. Pak:

$\{v_a, v_b, \dots, v_m\}$ je cyklus v grafu $G$
právě tehdy, když
$\{v_a, v_b\}, \dots, \{v_{m-1}, v_m\}, \{v_m, v_a\} \in E$.

Máme-li cyklus v grafu $G$, je daný cyklus zároveň cestou v grafu $G$?

Souvislost

Nechť $G = (V, E)$ je graf. Pak:

$G$ je souvislý graf právě tehdy, když pro každé dva vrcholy $v, w \in V$ existuje cesta z $v$ do $w$.

Jinak je $G$ nesouvislý graf.

Je graf souvislý?

Práce

Pro každý graf $G$ zjistěte, zda je souvislý.

$G_1$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 3((3))
                                3 --- 4((4))
                                4 --- 1

$G_2$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 3((3))
                                3 --- 4((4))
                                4 --- 1
                                
                                5((5)) --- 6((6))
                                6 --- 7((7))
                                7 --- 8((8))
                                8 --- 5

$G_3$:

                            graph LR
                                1((1)) --- 2((2))
                                2 --- 3((3))
                                3 --- 4((4))
                                4 --- 1
                    
                                5((5))
                                6((6))
                                7((7))
                                7 --- 8((8))
                                8 --- 5

                                1 --- 5
                                3 --- 7
                                4 --- 8

Souvislá komponenta

Nechť $G = (V, E)$ je graf. Podgraf $H$ grafu $G$ je souvislá komponenta grafu $G$ právě tehdy:

  • $H$ je souvislý graf
  • $H$ je maximální souvislý podgraf grafu $G$
  • neexistuje souvislý podgraf grafu $G$, který by obsahoval $H$ a zároveň by byl větší než $H$

Souvislá komponenta

                    graph LR
                        1((1)) --- 2((2))
                        2 --- 3((3))
                        3 --- 4((4))
                        4 --- 1
                        2 --- 4
                        
                        5((5)) --- 6((6))
                        6 --- 7((7))
                        7 --- 8((8))
                        8 --- 6

Komponenty: $\{1, 2, 3, 4\}$, $\{5, 6, 7, 8\}$

Hledání komponent / určování souvislosti

Spousta algoritmů — my si ukážeme průchod do hloubky.

Průchod do hloubky

Průchod do hloubky

  • depth-first search (DFS)
  • princip:
    • startujeme v nějakém vrcholu
    • do všech sousedních vrcholů, se kterými sousedíme, můžeme přejít, vybereme první
    • z daného vrcholu můžeme vejít do jeho sousedů, a tak dále

Pseudokód

DFS(G, v):
    if v is visited
        return
    mark v as visited
    for every edge {v, w} in G
        DFS(G, w)

Všechny označené vrcholy tvoří jednu komponentu a můžeme navštívit ze startovního vrcholu.

Proč je tento algoritmus správný?

Jaká je časová a prostorová asymptotická složitost?

Implementace TS

Strom

Strom

Graf $G = (V, E)$ je strom právě tehdy, když:

  • $G$ je souvislý graf
  • $G$ neobsahuje cyklus

List

Vrchol $v$ ve stromě $G$ je list právě tehdy, když $d(v) = 1$.

Tedy: má stupeň 1 = je spojen pouze s jedním vrcholem.

Věta o existence listu

Strom s alespoň dvěma vrcholy má alespoň dva listy.

Jakto?

Odebrání listu

Operace odebrání listu $v$ ze stromu $G$:

  • značíme $G - v$
  • odebereme vrchol $v$ a všechny hrany, které do něj vedou
  • výsledný graf je strom

Jakto?

Přidání listu

Operace přidání listu $v$ do stromu $G$:

  • značíme $G + v$
  • přidáme vrchol $v$ a hranu s vrcholem $w$
  • $w \in V(G)$ a $v \notin V(G)$
  • výsledný graf je strom

Ekvivalentní definice stromu

Graf $G = (V, E)$ je graf. Poté jsou následující tvrzení ekvivalentní:

  • $G$ je strom
  • pro každé dva vrcholy $u, v \in V(G)$ existuje právě jedna cesta z $u$ do $v$
  • $G$ je souvislý graf a $|E(G)| = |V(G)| - 1$
  • $G$ je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf

Orientovaný graf

Orientovaný graf

Orientovaný graf je dvojice $G = (V, E)$, kde:

  • $V$ je neprázdná množina vrcholů
  • $E$ je množina orientovaných hran
  • $E \subseteq \{(u, v) | u, v \in V\}$

Reprezentace

Hrany kreslíme šipkami.

                    graph LR
                        A((A))
                        B((B))
                        C((C))
                        D((D))
                        A --> B
                        B --> C
                        C --> A
                        C --> D

Orientované pojmy

Pro orientované grafy definujeme:

  • orientovaná cesta
  • orientovaný cyklus

Tyto pojmy zkuste definovat sami.

Vstupní okolí

Nechť $G = (V, E)$ je orientovaný graf. Poté vstupní okolí vrcholu $v \in V$ je:

  • $N^+(v) = \{u | u \in V \land (u, v) \in E\}$
  • množina vrcholů, ze kterých vstupují hrany do $v$

Výstupní okolí

Nechť $G = (V, E)$ je orientovaný graf. Poté výstupní okolí vrcholu $v \in V$ je:

  • $N^-(v) = \{u | u \in V \land (v, u) \in E\}$
  • množina vrcholů, do kterých vstupují hrany z $v$

Stupeň

Nechť $G = (V, E)$ je orientovaný graf. Poté stupeň vrcholu $v \in V$ je:

  • $d(v) = |N^+(v)| + |N^-(v)|$

Vstupní stupeň

Nechť $G = (V, E)$ je orientovaný graf. Poté vstupní stupeň vrcholu $v \in V$ je:

  • $d^+(v) = |\{u | u \in V \land (u, v) \in E\}| = |N^+(v)|$
  • počet hran, které do vrcholu $v$ vstupují (končí v $v$)

Výstupní stupeň

Nechť $G = (V, E)$ je orientovaný graf. Poté výstupní stupeň vrcholu $v \in V$ je:

  • $d^-(v) = |\{u | u \in V \land (v, u) \in E\}| = |N^-(v)|$
  • počet hran, které z vrcholu $v$ vystupují (začínají v $v$)

Stupeň

Nechť $G = (V, E)$ je orientovaný graf. Poté stupeň vrcholu $v \in V$ je:

  • $d(v) = d^+(v) + d^-(v) = |N(v)| = |N^+(v)| + |N^-(v)|$
  • počet hran, které vrchol $v$ spojují s ostatními vrcholy

Zdroj, stoka, izolovaný vrchol

Nechť $G = (V, E)$ je orientovaný graf. Poté:

  • $v \in V$ je zdroj, pokud $d^+(v) = 0$
  • $v \in V$ je stoka, pokud $d^-(v) = 0$
  • $v \in V$ je izolovaný vrchol, pokud $d(v) = 0$

Ukázka

$v_1$ je zdroj, $v_5$ je stoka, $v_6$ je izolovaný vrchol

graph LR
    v1((v1))
    v2((v2))
    v3((v3))
    v4((v4))
    v5((v5))
    v6((v6))
    
    v1 --> v2
    v1 --> v3
    v2 --> v4
    v3 --> v4
    v4 --> v5

Další reprezentace

  • matice sousednosti
  • seznam následníků

Podgrafy a DFS

  • stejně jako u neorientovaných grafů
  • DFS — místo jakéhokoliv souseda vybíráme následníka

Slabá souvislost

Graf $G$ je slabě souvislý, právě tehdy, když:

  • je souvislý neorientovaný graf $G_{\text{neor}}$, který vznikne jako
  • $G_{\text{neor}}$ má stejné vrcholy jako $G$
  • $G_{\text{neor}}$ má hrany $\{u, v\}$, pokud $G$ má hranu $(u, v)$ nebo $(v, u)$

Neorientovaný z orientovaného

Práce

Z níže neorientovaného grafu vytvořte orientovaný graf dle předchozího schématu:

$G_1$:

graph LR
    v1((v1))
    v2((v2))
    v3((v3))
    
    v1 --> v2
    v2 --> v3
    v3 --> v1

$G_2$:

                            graph LR
                                v1((v1))
                                v2((v2))
                                v3((v3))
                                v4((v4))
                            
                                v1 --> v2
                                v3 --> v4
                                v2 --> v3

$G_3$:

                            graph LR
                                v1((v1))
                                v2((v2))
                                v3((v3))
                                v4((v4))
                                v5((v5))
                                v6((v6))
                                
                                v3 --> v4
                                v3 --> v5
                                v4 --> v5
                                v1 --> v3
                                v1 --> v2
                                v6 --> v4

Silná souvislost

Graf $G$ je silně souvislý, právě tehdy, když:

  • pro každé dva vrcholy $u, v \in V$ existuje orientovaná cesta z $u$ do $v$ a zároveň z $v$ do $u$

Je silně souvislý?

                    graph LR
                        0((0))
                        1((1))
                        2((2))
                        3((3))
                        4((4))
                        5((5))
                        
                        0 --> 1
                        1 --> 2
                        2 --> 5
                        2 --> 3
                        5 --> 2
                        3 --> 0
                        3 --> 4
                        4 --> 0

Jak můžeme algorithmicky zjistit, zda je graf silně souvislý?

Kostra

Kostra

Graf $K$ je kostra ke grafu $G$, právě tehdy, když:

  • $V(K) = V(G)$
    • kostra obsahuje všechny vrcholy grafu
  • $K$ je podgraf $G$
  • $K$ je strom

Kolik koster může mít graf?

DFS pro kostru

  • vybíráme náhodný vrchol
  • pokud je vrchol již navštívený, přeskočíme ho
  • vypisujeme/ukládáme hrany, které přidáváme do kostry

Pseudokód

spanning_tree(G):
    for every v in V(G):
        mark v as unvisited
        
    v := random_vertex(G)
    
    DFS_spanning_tree(G, v)
    
DFS_spanning_tree(G, v):
    mark v as visited
    
    for every edge {v, w} in E(G):
        if w is unvisited:
            add {v, w} to spanning tree
            DFS_spanning_tree(G, w)

Implementace v C#

Proč to funguje?

Jaká je časová a paměťová složitost?

Prohledávání do šířky

Prohledávání do šířky

  • breadth-first search (BFS)
  • použité pro nalezení nejkratší cesty
  • využívá frontu

Záplavové prohledávání

  • vybereme vrchol
  • vypíšeme/uložíme vrchol
  • vložíme své sousedy do fronty
  • vybereme další vrchol z fronty a opakujeme
  • tímto způsobem projdeme celý souvislý graf

Konstrukce cesty

  • počítáme vzdálenost od počátečního vrcholu
  • ke každému vrcholu ukládáme první vrchol, ze kterého jsme se do něj dostali

Pseudokód

BFS(G, v):
    for every v in V(G):
        mark v as unvisited
        D[v] := undefined
        P[v] := undefined
    
    Q := empty_queue()
    enqueue(v)
    mark v as visited
    D[v] := 0
    
    while Q is not empty:
        w := dequeue(Q)
        for every edge {w, u} in E(G):
            if u is unvisited:
                enqueue(u)
                mark u as visited
                D[u] := D[w] + 1
                P[u] := w

Implementace v TS

Proč to funguje?

Jaká je časová a paměťová složitost?

Modifikace BFS

  • najít cestu z vrcholu $u$ do vrcholu $v$
  • pro orientovaný graf
  • přidání podmínek

Datové struktury

Zakořeněný strom

Strom je zakořeněný, pokud má jeden jeho vrchol označený jako kořen.

Vrcholy jsou uspořádány do úrovní, kde kořen je na úrovni 0 a každý vrchol na úrovni $i$ má potomky na úrovni $i+1$.

Ukázkový zakořeněný strom

graph TD
    A((1)) --- B((2))
    A --- C((3))
    B --- D((4))
    B --- E((5))
    C --- F((6))
    C --- G((7))
    C --- H((8))
    C --- I((9))
    D --- J((10))
    D --- K((11))
    D --- L((12))
    
    style A fill:#cd8f41

Binární stromy

Strom je binární, pokud:

  • je zakořeněný
  • každý vrchol má nejvýše dva potomky
  • u potomků rozlišujeme levého a pravého potomka

Ukázkový binární strom

graph TD
    A(( )) --- B(( ))
    A --- C(( ))
    B --- D(( ))
    B --- E(( ))
    C --- G(( ))
    C --- F(( ))
    
    style A fill:#cd8f41
    style G fill:#00000000,stroke:#00000000
    linkStyle 4 stroke:#00000000,fill:#00000000

Binární minimová halda

  • struktura je tvaru binárního stromu
  • každý vrchol má hodnotu (klíč)
  • hodnota v každém vrcholu je menší než hodnoty v jeho potomcích
  • strom má všechny úrovně plné, až na poslední, která být nemusí
  • poslední úroveň je plní zleva doprava

Ukázková binární minimová halda

graph TD
    A((3)) --- B((5))
    A --- C((7))
    B --- D((8))
    B --- E((9))
    C --- F((11))
    C --- G(( ))
    
    style A fill:#cd8f41
    style G fill:#00000000,stroke:#00000000
    linkStyle 5 stroke:#00000000,fill:#00000000

Kolik úrovní má binární minimová halda s $n$ vrcholy?

Kolik listů má binární minimová halda s $n$ vrcholy?

Přidání prvku do haldy

  • vložíme prvek do poslední úrovně, př. založíme novou úroveň
  • pokud je nový prvek větší než jeho rodič, neprovedeme nic
  • pokud je nový prvek menší než jeho rodič, prohodíme je a zkontrolujeme jeho rodiče
  • $O(\log n)$

Pseudokód přidávání prvku do haldy

HeapInsert(H, x):
    H.size = H.size + 1
    insert x to the last level of H
    BubbleUp(H, x)
    
BubbleUp(H, x):
    if x is root of H:
        return
        
    y = parent of x
    if x.key < y.key:
        swap x and y
        BubbleUp(H, y)

Odstranění minima z haldy

  • odstraníme kořen
  • na jeho místo vložíme poslední prvek
  • pokud je nový prvek větší než nějaký jeho potomek, prohodíme je a zkontrolujeme jeho potomky, ...
  • $O(\log n)$

Pseudokód odstranění minima z haldy

HeapDeleteMin(H):
    x = root of H
    y = last element of H
    H.size = H.size - 1
    swap x and y
    BubbleDown(H, x)
    
BubbleDown(H, x):
    if x is leaf:
        return
        
    y = child of x with the smallest key
    if x.key > y.key:
        swap x and y
        BubbleDown(H, y)

Získání minima z haldy

  • minimální prvek je vždy v kořeni
  • $O(1)$

Maximová halda

  • stejné jako minimová halda, ale hodnoty v potomcích jsou větší než hodnoty v rodiči

Změna hodnoty

Práce

Sepište pseudokód pro změnu hodnoty prvku v haldě tak, aby byla splněna podmínka minimové haldy.

Ukládání haldy

  • velmi jednoduše pomocí pole
  • kořen je na pozici 0
  • potomci vrcholu na pozici $i$ jsou na pozicích $2i+1$ a $2i+2$
  • rodič vrcholu na pozici $i$ je na pozici $\lfloor\frac{i-1}{2}\rfloor$
  • při přidání prvku do haldy se vloží na konec pole

Binární vyhledávací strom

Binární vyhledávací strom

Strom $T$ je binární vyhledávací strom (BVS/BST), pokud:

  • je v jeho každém vrcholu $v$ uložena hodnota a
  • pro každý vrchol $v$ platí, že hodnoty v levém podstromu jsou menší než hodnota v $v$ a hodnoty v pravém podstromu jsou větší než hodnota v $v$

Ukázky BVS

$T_1$:

                        graph TD
                            7((7))
                            4((4))
                            2((2))
                            5((5))
                            9((9))
                            8((8))
                            
                            7 --- 4
                            7 --- 9
                            4 --- 2
                            4 --- 5
                            9 --- 8
                            9 --- E(( ))
                            
                            style E fill:#00000000,stroke:#00000000
                            linkStyle 5 stroke:#00000000,fill:#00000000

$T_2$:

                        graph TD
                            4((4))
                            2((2))
                            5((5))
                            E1(( ))
                            E11(( ))
                            7((7))
                            E2(( ))
                            E21(( ))
                            8((8))
                            E3(( ))
                            E31(( ))
                            9((9))
                            
                            4 --- 2
                            4 --- 5
                            
                            5 --- E1
                            E1 --- E11
                            5 --- 7
                            
                            7 --- E2
                            E2 --- E21
                            7 --- 8
                            
                            8 --- E3
                            E3 --- E31
                            8 --- 9
                            
                            style E1 fill:#00000000,stroke:#00000000
                            style E2 fill:#00000000,stroke:#00000000
                            style E3 fill:#00000000,stroke:#00000000
                            style E11 fill:#00000000,stroke:#00000000
                            style E21 fill:#00000000,stroke:#00000000
                            style E31 fill:#00000000,stroke:#00000000
                            
                            linkStyle 2 stroke:#00000000,fill:#00000000
                            linkStyle 3 stroke:#00000000,fill:#00000000
                            linkStyle 5 stroke:#00000000,fill:#00000000
                            linkStyle 6 stroke:#00000000,fill:#00000000
                            linkStyle 8 stroke:#00000000,fill:#00000000
                            linkStyle 9 stroke:#00000000,fill:#00000000

Operace

  • vypsání hodnot v BVS v pořadí vzestupném
  • minimum a maximum
  • předchozí a následující prvek
  • vyhledání prvku
  • vložení prvku
  • odebrání prvku

Vypsání hodnot

bst_show(T):
    if T is not empty:
        bst_show(T.left)
        print(T.value)
        bst_show(T.right)

Minimum/maximum

bst_min(T):
    if T is empty:
        return null
    if T.left is empty:
        return T.value
    return bst_min(T.left)

Předchozí/následující prvek

bst_prev(T, x):
    if T is empty:
        return null
    if T.value == x:
        if T.left is not empty:
            return bst_max(T.left)
        return null
    if T.value > x:
        return bst_prev(T.left, x)
    r = bst_prev(T.right, x)
    if r is null:
        return T.value
    return r

Vyhledání prvku

bst_find(T, x):
    if T is empty:
        return false
    if T.value == x:
        return true
    if T.value > x:
        return bst_find(T.left, x)
    return bst_find(T.right, x)

Vložení prvku

bst_insert(T, x):
    if T is empty:
        return bst_create(x)
    if T.value == x:
        return T
    if T.value > x:
        T.left = bst_insert(T.left, x)
    else:
        T.right = bst_insert(T.right, x)
    return T
    
bst_create(x):
    T = new Node
    T.value = x
    T.left = null
    T.right = null
    return T

Odebrání prvku

bst_remove(T, x):
    if T is empty:
        return null
    if T.value == x:
        if T.left is empty:
            return T.right
        if T.right is empty:
            return T.left
        T.value = bst_min(T.right)
        T.right = bst_remove(T.right, T.value)
        return T
    if T.value > x:
        T.left = bst_remove(T.left, x)
    else:
        T.right = bst_remove(T.right, x)

Kolik hladin může mít binární strom?

Dokonale vyvážený binární strom

Binární vyhlazovací strom $T$ je dokonale vyvážený, pokud pro každý uzel $u$ platí, že
$|h(u.left) - h(u.right)| \leq 1$.

$h(u)$ je počet hladin uzlu $u$.

Časová složitost operací

Práce

Jednotlivým operacím BVS určete jejich časovou složitost.

Ohodnocený graf

Ohodnocený graf

Grafu $G = (V, E)$ říkáme ohodnocený, pokud:

  • každé hraně $e \in E$ je přiřazena hodnota $w(e) \in \mathbb{R}$

Sled

Pro graf $G = (V, E)$ definujeme sled jako posloupnost vrcholů $(v_0, e_1, v_1, e_2, v_2, \dots, e_k, v_k)$, pro kterou platí:

  • $v_i \in V$ pro $i = 0, 1, \dots, k$
  • $e_i = (v_{i-1}, v_i) \in E$ pro $i = 1, 2, \dots, k$

Délka sledu $l(S)$ je součet délek jeho hran.

Jak se liší sled od cesty?

Vzdálenost v grafu

Pro libovolné dva vrcholy $u, v \in V$ definujeme vzdálenost $d(u, v)$ jako:

  • nejmenší součet hodnot hran na cestě z $u$ do $v$
  • neexistuje-li cesta z $u$ do $v$, je $d(u, v) = \infty$

Zjednodušování sledů

Pokud jsou délky hran kladné, pak pro každý $uv$-sled existuje $uv$-cesta stejné nebo menší délky.

Hledání nejkratší cesty

Problém je NP-těžký, což znamená, že neočekáváme algoritmus, který by jej řešil v polynomiálním čase.

Pro speciální ohodnocení grafu můžeme problém řešit lépe.

Dijkstrův algoritmus

Očekává pouze kladné ohodnocení hran.

Řeší obecný problém:

Pro zadaný orientovaný graf $G$ s kladnými délkami hran a zadaný počáteční vrchol $v_0$ nalezni vzdálenosti všech vrcholů grafu G od vrcholu $v_0$.

Pro jednotkové délky se algoritmus chová jako BFS.

Nápad 1

Každou hranu o kladné délce větší jak 1 nahradíme cestou z jednotkových hran.

graph LR
A((A))-- 4 -->B((B))
                
graph LR
A((A))-- 1 -->A1(( ))
A1-- 1 -->A2(( ))
A2-- 1 -->A3(( ))
A3-- 1 -->B((B))

Na novém grafu spustíme BFS. Tímto krokem budeme mít $O(L \cdot n)$ vrcholů a hran, kde $L$ je největší délka cest.

Nápad 2

  • v každém vrcholu je budík
  • místo BFS nastavíme sousedům budíky na časy, kdy do nich vlna dorazila
  • podle nejdříve probuzeného vrcholu:
    • prozkoumáme jeho sousedy
    • nastavíme jim budíky, pokud vlna dorazila dříve
  • znovu čekáme na nejdříve probuzený vrchol a opakujeme

Dijkstra

  • všechny vrcholy mají hodnotu budíku $h(v)$
  • všechny vrcholy ze začátku mají hodnotu $h(v) = \infty$
  • máme tři stavy vrcholu $v$:
    • nenalezený
    • otevřený (budík je nastavený)
    • uzavřený (budík zazvonil)
  • pro cestu si pamatujeme předchůdce

Pseudokód

Dijkstra(G, v0):
    for every v in V(G):
        h(v) := infinity
        P[v] := undefined
        state[v] := notFound
        
    h(v0) := 0
    state[v0] := open
    
    while there is an open vertex:
        v := open vertex with the smallest h(v)
        
        for every edge {v, w} in E(G): // záleží na typu grafu
            if h(w) > h(v) + w(v, w):
                h(w) := h(v) + w(v, w)
                P[w] := v
                state[w] := open

        state[v] := closed
    return P

Správnost

  • proč tento algoritmus funguje?
  • jakou má časovou složitost?

Fellmanův-Fordův algoritmus

  • očekává, že ohodnocení hran může být i záporné
  • ALE graf neobsahuje záporný cyklus

To be continued...

Děkuji za pozornost!

  • matej.cajthaml@ssps.cz
  • https://ssps.cajthaml.eu/