Замечание

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

1.3.2. Каноническая матрица смежности и изоморфность графов

Определение

Код матрицы смежности А задается следующим образом:

cd= A_ij 2^K,

где K=n²-(i-1)n-j.

В коде матрицы смежности А элементы матрицы выбираются строка за строкой в их естесственном порядке,т.е.

А₁₁А₁₂…А_1nA₂₁…A_2n…A_n1…A_nn .

Пример

Для матриц смежности рис.1.4.2 коды равны:

cd(A₁)=2⁶² + 2⁵⁷ + 2⁵⁶ + 2⁵⁵ + 2⁵³ + 2⁵² + 2⁴⁶ + 2⁴⁴ + 2⁴⁰ + 2³⁸ + 2³⁷ + 2³⁵ + 2²⁸ + 2²⁶ + 2²⁵ + 2¹⁹ + 2¹⁷ + 2¹⁵ + 2¹¹ + 2¹⁰ + 2⁷ + 2⁵ + 2² = 4 877 487 903 930 551 460

cd(A₂)= 5 021 603 092 014 697 890

М

Пример

ножество всех изоморфных друг другу графов образуют класс. Среди всех матриц смежности этого класса графов одна из матриц смежности будет иметь наименьший по значению код. Эта матрица называется канонической (обозначается canon(G)).

Для класса матриц рис.1.4.2 код канонической матрицы равен:

cd(canon(G)) = 507 522 663 119 374 560

Определение

Пусть G₁(V,E) и G₂(V,E) будут графами, а А₁ и А₂ – их матрицами смежности. Графы G₁(V,E) и G₂(V,E) будут изоморфны, если матрицы А₁ и А₂ сводятся к одной и той же канонической матрице.

Наиболее эффективные алгоритмы нахождения канонической матрицы смежности базируются на процедуре возврата для всех возможных перестановок имен множества вер-

шин графа.¹

2

Определения

.3.3. Инварианты

Пусть f- функция, относящая каждому графу G некоторый элемент f(G) из множества М произвольной природы.

Эта функция показывается инвариантом, если на изоморфных графах её значение совпадают, т.е. для любых G и G’ из изоморфизма графов G и G’ следует f(G)=f(G’).

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

Во многих случаях инварианты имеют всего два значения, 0 и 1 . Значение 1 показывает, что это свойство у графа имеется, а 0 – что это свойство отсутствует. К таким инвариантам относятся:

• связность,

• планарность,

• является ли граф деревом,

• является ли граф двудольным

и т.д.

Другую группу составляют инварианты, равные натуральным числам:

• число вершин и рёбер;

• степень вершин;

• последовательность степеней вершин;

• число компонент связности;

• хроматическое число;

• наличие пути заданной длины;

• наличие гамильтонова цикла;

• число связных компонент

и т.д.

К сожалению, нет универсального алгоритма определения изоморфизма для всех графов по одному инварианту.

Определения

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

Системы инвариантов существуют, но их нахождение является сложнейшей задачей.