02 Izomorfismus 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}}
$$
# Izomorfismus grafů
Nechť $G$ a $H$ jsou dva grafy
Funkce $f: V(G) \rightarrow V(H)$ je izomorfismus grafů $G$ a $H$, pokud:
- $f$ je bijekce
- a pro každou dvojici vrcholů $u,v$ z $V(G)$ platí ${u,v}\in E(G)$ právě tehdy, když ${f(u), f(v)} \in E(H)$
- ${u,v}\notin E(\overline{G})$ právě tehdy, když ${f(u), f(v)} \notin E(\overline{H})$
Tedy grafy jsou izomorfní, pokud mají hranami spojené stejné vrcholy (i když jinak pojmenované)
- Hrana přilehne na hranu
- Nehrana přilehne na nehranu
Izomorfismus značíme $G \simeq H$
