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

Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.

Для изоморфизма двух n-вершинных графов теоретически безукоризненный способ проверки состоит в проверке всех n! взаимно однозначных соответствий между множествами вершин и установлении, совмещаются ли полностью ребра графа хотя бы при одном соответствии. Однако даже весьма грубая оценка показывает, что такое решение «в лоб» практически непригодно: уже при n=20 перебор всех n! вариантов потребовал бы десятки лет машинного времени.

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

Инвариантом графа G(X, U) называется параметр, имеющий одно и то же значение для всех графов, изоморфных графу G.

Вначале естественно поставить вопрос: какие характеристики графов инвариантны относительно изоморфизма?

Среди самых очевидных инвариантов отметим следующие:

1. Число вершин |X| = m.

2. Число ребер |U| = k.

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

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

5. Плотность f(G) – число вершин клики графа G.

6. Число внутренней устойчивости  (G).

7. Хроматическое число (G).

8. Число Хадвигера (G).

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

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

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

Пример. Для графов на рис. 9.1 определим значения инвариантов.

Рисунок 9.1. Графы G₁ и G₂

Инвариант	G1	G2	Совпадение
m	6	6	+
k	6	6	+
р(G)	1	1	+
Список x	3, 2, 2, 2, 2, 1	3, 2, 2, 2, 2, 1	+
f(G)	2	2	+
 (G)	3	3	+
(G)	2	3	-
(G)	3	3	+

Хроматические числа рассматриваемых графов разные. Это позволяет сделать вывод, что графы G₁ и G₂ не изоморфны.

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

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

Во-первых, если списки не совпадают, то отсюда сразу следует не изоморфизм графов G₁ и G₂.

Во-вторых, если списки совпали, то для проверки графов G₁ и G₂ на изоморфизм требуется перебор не всех n! соответствий между вершинами, а лишь тех, при которых сопоставляются вершины с одинаковой степенью. Так, в рассмотренном примере надо перебрать лишь 4! = 24 соответствия вместо 6! = 720.

Пример. Проверить на изоморфизм графы G₁ и G₂ (рис. 9.2)

		х1	х2	х3	х4	х5	х6	х7	ρ(x)
	х1	0	1	1	1				3
	х2	1	0	1		1		1	4
	х3	1	1	0	1	1	1	1	6
R(G1)=	х4	1		1	0	1	1	1	5
	х5		1	1	1	0	1		4
	х6			1	1	1	0	1	4
	х7		1	1	1		1	0	4

		y1	y2	y3	y4	y5	y6	y7	ρ(y)
	y1	0	1	1	1		1		4
	y2	1	0	1	1	1	1	1	6
	y3	1	1	0	1	1			4
R(G2)=	y4	1	1	1	0		1	1	5
	y5		1	1		0	1	1	4
	y6	1	1		1	1	0		4
	y7		1		1	1		0	3

Рисунок 9.2. Графы G₁ и G₂ и их матрицы соединений

Для графа G₁ Σρ(x)=30. Список Ρ(x) = {6, 5, 4, 4, 4, 4, 3}.

Для графа G₂ Σρ(y)=30. Список Ρ(y) = {6, 5, 4, 4, 4, 4, 3}.

Разобьем вершины обоих графов на классы по их степеням.

	ρ(x)= ρ(y)=6	ρ(x)= ρ(y)=5	ρ(x)= ρ(y)=4	ρ(x)= ρ(y)=3
X	x3	x4	x2, x5, x6, x7	x1
Y	y2	y4	y1, y3, y5, y6	y7

Из таблицы сразу видно соответствие вершин графов:

X	Y
x3	y2
x4	y4
x1	y7

Для определения соответствия вершин с ρ(x)= ρ(y)=4 попробуем связать вершины из классов с ρ(x)= ρ(y)=5 и ρ(x)= ρ(y)=3 с неустановленными вершинами.

X		Y
x 3	x2 x5 x6 x7	y 1 y3 y5 y6	y2
x 4			y4
x1			y7

Анализ связей вершин показывает соответствие вершин x₂ и y₅ (соединены с установленными вершинами х₃y₂ и х₁y₇. С учетом этого

X		Y
x 3	x5 x6 x7	y 1 y3 y6	y2
x 4			y4
x 1			y7
x2			y5

Анализ связей вершин показывает соответствие вершин x₆ и y₁ (единственные имеют одну связь с классом вершин ρ(x)= ρ(y)=5. С учетом этого

X		Y
x3	x5 x7	y3 y 6	y2
x 4			y4
x1			y7
x 2			y5
x6			y1

Анализ связей вершин показывает, что существует две пары соответствий оставшихся вершин: вершины x₅ и y₃ и вершины x₇ и y₆, или x₆ и y₃ и вершины x₇ и y_3. Это соответствует действительности, т.к. вершины x₅ и x₇ в графе G₁ и вершины y₃ и y₆ в графе G₂ смежны с одними и теми же вершинами.

Из сказанного можно сделать вывод, что графы G₁ и G₂ изоморфны.