п

Определение

еребора

П

Замечание

усть G₁ и G₂будут графами, а А₁и А₂– их матрицами смежности. Графы G₁ и G₂будут изоморфными, если их матрицы смежности равны.

Задача определения равенства матриц смежности сложна, т.к. вид матрицы смежности графа зависит от процедуры именования вершин графа.

Пример

1 2 3 4 5 6 7 8

Рис.2.4.2. Два изоморфных графа и их матрицы смежности

Метод перебора

Прямым методом определения равенства матриц А₁и А₂является перестановка строк и столбцов матриц и их сравнение между собой. Для этого потребуется в общем случаеn! операций, гдеn=|V| (для примера рис.1.4.2 потребуется 8!=40 320 операций).

Определение

Пусть имеется два графа G₁и G₂, а Т₁и Т₂– таблицами инцидентности этих графов. Графы G₁и G₂будут изоморфны, если Т₁совпадает с Т₂.

Алгоритм перебора

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

Обозначим через v_1ii-ую вершину графаG₁.

1. Если |V₁| = |V₂|, тоn= |V₁|,

   1. иначе графы неизоморфны.

2. Начальное условие: i= 1.

3. Сравнивая таблицы инцидентности построчно, определить совпадают ли по длине запись для v_1iи записи таблицы инцидентности графаG₂. Если совпадают, то изъять эти записи их обеих таблиц инцидентности, иначе графы неизоморфны.

4. Повторить шаг 3 для v_1i,i=2,3,…,n.

После успешного выполнения алгоритма обе таблицы инцидентности будут пустыми.

Пример

Замечание

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

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) будут изоморфны, если матрицы А₁и А₂сводятся к одной и той же канонической матрице.

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

шин графа.¹