Изоморфизм графов

Изоморфизм графов (Graph isomorphism) --- биекция [math]\displaystyle{ \varphi: \; V(G) \rightarrow V(H) }[/math] множества вершин графа [math]\displaystyle{ G }[/math] на множество вершин графа [math]\displaystyle{ H }[/math], сохраняющая отношение смежности; другими словами, для любых вершин [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] графа [math]\displaystyle{ G }[/math] их образы [math]\displaystyle{ \varphi(u) }[/math] и [math]\displaystyle{ \varphi(v) }[/math] смежны в [math]\displaystyle{ H }[/math] тогда и только тогда, когда [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] смежны в [math]\displaystyle{ G }[/math].

Отношение изоморфизма графов является отношением эквивалентности, т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов является [math]\displaystyle{ \mathcal NP }[/math]-Полной.

Литература

[Лекции],

[Зыков/69]