1. (Tranzitivní uzávěr grafu)
    Dostanete graf $G=(V,E)$. Hrana $uv$ vyjadřuje, že $u$ a $v$ jsou v relaci $R$ (graf je v podstatě jen zápis relace $R$ obrázkem). Relace $R$ je určitě symetrická, protože máme neorientovaný graf. Relace $R$ ale nemusí být tranzitivní (pokud $a R b$ a $b R c$ tak potom i $a R c$). Chtěli bychom ji rozšířit na relaci, která už tranzitivní je.

    Tranzitivní uzávěr grafu je nejmenší nadgraf $G$ (doplnění hran), který už je tranzitivní. Jinými slovy, tranzitivní uzávěr grafu $G$ je graf $G_T=(V,E_T)$ s původními vrcholy a $vw$ je hrana tranzitivního uzávěru právě tehdy když v $G$ existuje cesta mezi $v$ a $w$.

    1. Navrhněte efektivní algoritmus, který najde tranzitivní uzávěr neorientovaného grafu $G$.
    2. Tranzitivní uzávěr můžeme definovat i pro orientované grafy (tj. pro relace, které nemusí být symetrické). Tranzitivní uzávěr orientovaného grafu $G$ je orientovaný graf $G_T=(V,E_T)$ s původními vrcholy a $vw$ je hrana tranzitivního uzávěru právě tehdy když v $G$ existuje orientovaná cesta z $v$ do $w$. Navrhněte efektivní algoritmus, který najde tranzitivní uzávěr orientovaného grafu $G$.