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

Определение 3.4.1.Графы G₁ =.(X₁,.A₁) и G₂ =.(X₂,.A₂) изоморфны (рис.15), если существует взаимно однозначное соответствие между множествами вершин X₁ и X₂, такое, что любые две вершины одного графа соединены тогда и только тогда, когда соответствующие вершины соединены в другом графе.

	рис.15
G1	G2

Изморфные графы рассматриваются как идентичные: их различия связаны со способом реализации, но не с внутренней структурой.

Определение 3.4.2.Инвариантом графа называется параметр, имеющий одно и то же значение для всех графов, изоморфных заданному графу. Среди самых очевидных инвариантов отметим следующие:

1. Число вершин |V|=n.

2. Число ребер |E|=m.

3. Число компонент связности.

4. Последовательность степеней, т.е.список степеней всех вершин в убывающем порядке значений.

Для решения задач изоморфизма обычно состоят в попытках показать, что два рассматриваемые графа не изоморфны. Для этого составляется список различных инвариантов в порядке, определяемом сложностью вычисления инварианта. Затем последовательно сравниваются значения параметров графов. Как только обнаруживаются два различных значения одного и того же параметра, приходят к заключению, что данные графы не изоморфны.

Множество инвариантов, которое позволило бы этой процедуре установить изоморфность графов за полиномиальное время, называется кодом графа. К сожалению, на сегодняшний день такое множество не найдено. По существу, алгоритм рассматриваемого типа сводится к сравнению кодов двух графов. Конечно, рассмотрение большого числа инвариантов увеличивает вероятность правильного заключения об изоморфизме при совпадении всех значений параметров, но в общем случае ничего не гарантирует.