03 Kostra grafu
$$
\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}}
$$
# Kostra grafu
- Spanning tree
- Vybrat nějakou sadu hran takovou, že bude indukovat souvislý graf
- Bude strom
- Nechť $G$ je
souvislý graf, podgraf $K$ nazveme kostrou, pokud $V(K) = V$ a $K$ je strom
- Nesouvislé grafy nemají kostru, kostru má každá souvislá komponenta
- Souvislý graf s kružnicemi má více koster
- Podgraf, který obsahuje všechny vrcholy a zároveň je strom
# Hledání kostry
- Modifikace BFS - po zaplavení vrcholu vytvoříme zpětný pointer, odkud se zaplavilo
- Nechť $G$ je souvislý graf
- Hrany do předchůdců tvoří nějakou kostru grafu $G$
# Topologické uspořádání vrcholů
- Pořadí vrcholů, aby všechny orientované hrany vedly pouze od nižších k vyšším indexům
- Takové seřazení vrcholů $V = {v_{1}, \dots, v_{n}}$, že pro každou orientovanou hranu platí $(v_{i}, v_{j})\in E$ platí $i < j$
- Může jich být více
- Graf s cykly nemá řešení
Pozorování:
- Graf má právě 1 topologické uspořádání, právě tehdy, když existuje orientovaná cesta délky $n$ v $G$