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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Литература

  • Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.