1. (Převody mezi reprezentacemi)
    Pro každé dvě reprezentace grafu navrhněte nejefektivnější způsob převodu z první reprezentace do druhé. Určete časovou složitost převodu.

  2. (Obrácení hran v orientovaném grafu)
    Dostanete orientovaný graf reprezentovaný maticí sousednosti $A$. Obrátit všechny šipky na druhou stranu je jednoduché, stačí vzít matici transponovanou $A^{\mbox{T}}$. Matice transponovaná k matici $A=(a_{i,j})$ je matice $A^{\mbox{T}}=(a_{j,i})$ (prohodíme řádky za sloupce a naopak). Ale co když dostaneme graf reprezentovaný seznamem sousedů? Jak rychle obrátíte hrany v této reprezentaci?

  3. (Mocnina orientovaného grafu)
    Mocnina orientovaného grafu $G=(V,E)$ je graf $G^2=(V, E^2)$, kde $uv\in E^2$ právě tehdy když z $u$ vede orientovaná cesta délky $2$ do $v$ (neboli existuje vrchol $w\in V$ takový, že $uw\in E$ a $wv\in E$). Navrhněte efektivní algoritmus, který dostane graf $G$ reprezentovaný buď maticí sousednosti nebo seznamem sousedů, a vytvoří graf $G^2$ reprezentovaný stejným způsobem. Jaká je časová složitost vašeho algoritmu?

  4. (Hledání stoku)
    Dostanete orientovaný graf reprezentovaný maticí sousednosti. Většina algoritmů pracujících s maticí sousednosti má časovou složitost alespoň $\Omega(n^2)$. Ale jsou i výjimky.

    1. Zkuste co nejrychleji najít univerzální stok grafu. Univerzální stok je takový vrchol, do kterého vede $n-1$ hran ze všech ostatních vrcholů, ale ze kterého nevedou žádné hrany ven. Zvládnete to v čase $\OO(n)$?
    2. Zkuste co nejrychleji najít stok grafu. Stok je takový vrchol, ze kterého nevedou žádné hrany ven. Jaká bude časová složitost vašeho algoritmu?
  5. (Matice incidence)
    Česky bychom mohli říci matice náležení. Tato matice zachycuje, kdy platí $v\in e$ pro $v\in V$ a $e\in E$. Matice incidence $I$ má velikost $n\times m$ a je definována jako $I=(i_{v,e})_{v\in V, e\in E}$, kde $$i_{v,e} = \left\{\begin{array}{l r} 0 & \Longleftrightarrow v \not\in e \\ 1 & \Longleftrightarrow v \in e \end{array}\right.$$

    Pro graf $G$ z kapitoly „Reprezentace grafu“ dostáváme následující matici. $$I(G) =
    \hspace{3mm}\begin{array}{ccccccr}
    e_{AB} &e_{AC} & e_{AD} & e_{BD} & e_{CD} & e_{DE} & {} \\[2mm]
    \left(
    \begin{array}{c}1 \\1 \\0 \\0 \\0 \end{array}
    \right.
    &
    \begin{array}{c}1 \\0 \\1 \\0 \\0 \end{array}
    &
    \begin{array}{c}1 \\0 \\0 \\1 \\0 \end{array}
    &
    \begin{array}{c}0 \\1 \\0 \\1 \\0 \end{array}
    &
    \begin{array}{c}0 \\0 \\1 \\1 \\0 \end{array}
    &
    \left.
    \begin{array}{c}0 \\0 \\0 \\1 \\1 \end{array}
    \right)
    &
    \begin{array}{c}A \\B \\C \\D \\E \end{array}
    \end{array}
    $$

    V každém sloupci jsou právě dvě jedničky, protože každá hrana má právě dva konce. Pokud bychom chtěli takto reprezentovat orientovaný graf, tak musíme jedničku u výchozího vrcholu šipky změnit na mínus jedničku.

    Matice incidence orientovaného grafu $G=V,E)$ je matice tvaru $n\times m$ $B=(b_{v,e})$, kde $$
    b_{v,e} = \left\{
    \begin{array}{l l} -1 & \mbox{pokud hrana $e$ vychází z vrcholu $v$} \\
    1 & \mbox{pokud hrana $e$ přichází do vrcholu $v$} \\
    0 & \mbox{jinak.} \\
    \end{array}\right.
    $$

    Zjistěte, jaký význam mají položky matice $B\cdot B^{\mbox{T}}$, kde $B^{\mbox{T}}$ značí matici transponovanou k matici $B$.

Podsekce: