03 Orientovaný acyklický 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ý acyklický graf
# Zdroj
- Takový vrchol orientovaného grafu, do kterého nevede žádná hrana
- Každý DAG (Directed Acyclic Graph) má alespoň 1 zdroj
# Stok
- Takový vrchol orientovaného grafu, ze kterého nevede žádná hrana
- Každý DAG (Directed Acyclic Graph) má alespoň 1 stok
# Algoritmus TopSort
- Algoritmus konstrukce [topologického uspořádání vrcholů](notes/bi-ag1/03-kostra-grafu.md#Topologické uspořádání vrcholů)
- Postupně odtrhává zdroje
- Zkontroluj, že $G$ má jediný zdroj $v$
- Zařaď $v$ do TU, $G = G - v$
- Opakuj