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

Говорят, что два графа G₁(V₁,E₁) и G₂(V₂,E₂) изоморфны (обозначается G₁~ G₂), если существует биекция h: V₁V₂, сохраняющая смежность.

Графы рассматриваются с точностью до изоморфизма.

Пример

Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграм­мами одного и того же графа К_3,3.

Рис. 3.6. Диаграммы изоморфных графов

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) - инварианты графа G.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами