01 Druhy 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}}
$$
Navazuje na 01 Graf
# Druhy grafů
Úplný graf $\Large{K_n}$ (klika)
- Nechť počet vrcholů $n \ge 1$
- Úplný graf na $n$ vrcholech je $K_n$ graf $(V, \binom{V}{2})$ kde $|V| = n$
- Počet jeho automorfismů je $n!$
Úplný bipartitní graf $\Large{K_{n1,n2}}$
- Nechť počet vrcholů $n_1 \ge 1$ a $n_{2}\ge 1$
- Je tvořen 2 partitami o $n_1$ a $n_2$ vrcholech
- Graf $(A \cup B, {{a,b}} \enspace|\enspace a \in A, b \in B)$ tedy vrcholy jsou sjednocení vrcholů z grafů $A$ a $B$, hrany vedou z vrcholu $a$ do $b$
- Každý vrchol vlevo má hranu ke každému vpravo, tedy počet hran $|E| = n_{1}\cdot n_{2}$
# Cesta
- Značíme $P_m$
- Délka cesty $m \ge 0$
- Cesta je graf $({0,\dots,m}, {{i, i+1} \space | \space i \in {0,\dots, m-1} })$ = tedy graf s vrcholy a hranami $i$ takový, že hrana jde vždy z předchozího do dalšího vrcholu
Pozor! U cesty $P_m$ udává index $m$ počet hran, nikoli vrcholů!
# Kružnice
- Počet vrcholů je alespoň 3 = $n \ge 3$
- Vrcholy propojené v kruhu
# Doplněk grafu
Doplněk $\overline{G}$ grafu $G=(V,E)$ je graf $\overline{G}=(V,\binom{V}{2}\setminus E)$
Tedy úplný graf se všemi hranami kromě hran grafu $G$
Nechť $G=({0,1,2,3},\enspace {0,1}, {0,2}, {1,2}, {2,3})$
Pak $\overline{G}=({0,1,2,3},\enspace {0,3}, {1,3})$
