Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический

• Название: Простые графы (графы) Способы задания графа Основные способы задания графов графический
• Анкор: Глава 2.Ненаправленные графы, часть 1.doc
• Дата: 04.09.2018
• Размер: 1.28 Mb.
• Имя файла: Глава 2.Ненаправленные графы, часть 1.doc
• Тип: Глава; #24055
• страница: 7 из 14

2.3.1. Изоморфизм графов и прямые методы

п

Определение

еребора




П

Замечание

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



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

шин графа.¹