01 Orientovaný graf
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Orientovaný graf
- Uspořádaná dvojice $(V,E)$, kde:
- $V$ - neprázdná konečná množina vrcholů
- $E$ - množina orientovaných hran (šipky)
- Orientovaná hrana $(u,v)$ je uspořádaná dvojice
- $u$ - předchůdce
- $v$ - následník
- $(u,u)$ - smyčka
# Modrá/červená hrana
- Nejvýš 1 modrá hrana:
- Udělám 2 kopie grafu jako orientovaný graf
- Červené hrany budou obousměrné v obou kopiích
- Modré hrany budou vést mezi kopiemi (orientované z jedné kopie do druhé)
# Zbytkové třídy
- Číslo vynásobím základem, přičtu novou cifru (0 nebo 1), modulím základem, zbytek je opět hrana k další třídě
# Symetrizace
- Každou orientovanou šipku nahradím neorientovanou hranou
- “Zapomenu orientaci”
# Slabá souvislost orientovaného grafu
Souvisí s 02 Souvislost grafu
- Je slabě souvislý, pokud je souvislá jeho symetrizace $\mathrm{sym}(G)$
# Silná souvislost
- Je silně souvislý, pokud pro každé vrcholy existuje orientovaná cesta tam i nazpátek (nemusí být přímo jen délky 1)