02 Souvislost 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}}
$$
# Souvislost grafu
- Graf je souvislý, jestliže v něm pro každé jeho 2 vrcholy $s,v$ existuje $s$-$v$-cesta
- Jinak je nesouvislý
Pozorování Graf je souvislý právě tehdy, když obsahuje právě 1 souvislou komponentu
- Nemůže existovat nesouvislý graf, jehož doplněk by byl takové nesouvislý (tj. doplněk musí být souvislý)
# Souvislé komponenty grafu
- Indukovaný
podgraf $H$ grafu $G$ je souvislou komponentou, pokud:
- je souvislý a zároveň
- neexistuje žádný souvislý podgraf $F, F \ne H$, grafu $G$ takový, že $H \subseteq F$
# Binární relace
- Značíme $\Large\leftrightsquigarrow$
- $u \leftrightsquigarrow v = \exists\space$ $u$-$v$-cesta v $G$
# Algoritmy pro vyšetřování souvislosti
- Lze využít
BFS
- Když doběhne, uzavře všechny vrcholy, do kterých existuje cesta ze startu $s$
- Lze najít souvislou komponentu ve které leží $s$
- Pokud uzavře všechny vrcholy, je celý graf souvislý
# Slabá souvislost orientovaného grafu
Souvisí s 01 Orientovaný graf
- 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)