2.3 Izomorfismus

Definice 2.10 (Izomorfismus grafů)

Nechť \(G\) a \(H\) jsou dva grafy.

Funkce \(f : V (G) → 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)\).

Dva grafy \(G\) a \(H\) jsou izomorfní, pokud existuje izomorfismus grafů \(G\) a \(H\).
Tento fakt značíme \(G \simeq H\)

Definice 2.11 (Automorfismus grafu)

Automorfismus grafu \(G\) je izomorfismus se sebou samým,
tedy funkce \(f : V (G) \to V (G)\) taková, že

\(f\) je bijekce
a pro každou dvojici vrcholů \(u, v \in V(G)\) platí
\(\{u, v\} \in E(G)\) právě tehdy, když \(\{f (u), f (v)\} \in E(G)\).

Neformálně řečeno: Automorfismus je permutace vrcholů, zachovávající "býti hranou".
Automorfismy ukazují "symetrie" grafu.
Množství automorfismů tedy ukazuje na míru pravidelnosti grafu.

Pozorování 2.1 (O počtu grafů)

Na \(n\)-prvkové množině vrcholů \(V\) je právě \(2^{\binom{n}{2}}\) různých grafů

Navzájem neizomorfních grafů na \(V\) je méně.
Např. pro \(V = \{1, 2, 3\}\) dostáváme \(2^\binom{3}{2}\) = \(2^{3}\) = 8 všech grafů, z nichž ale jen 4 jsou neizomorfní.
Pozn.: Binomiální číslo \(\binom{n}{k}\) označuje počet \(k\)-prvkových podmnožin z \(n\)-prvkové množiny.