2

Определения

.3.5. Граф шина

Шина - граф G, имеющий n вершин и (n-1) ребер, при этом n-2 вершины имеют степень 2, а две вершины – степень 1.

Пример

Рис.2.3.6. Граф шина

2.3.6. Граф цикл

Определения

Г

Пример

раф с n вершинами степени 2 и n рёбрами (имеет специальное обозначение C_n) такой, что вершина i соединена с двумя вершинами i+1 и i-1.

Рис.2.3.7. Пример графов цикл (кольцо)

1.3.7. Граф колесо

Определения

Граф колесо порядка n (обозначается W_n) имеет одну вершину степени n-1, а остальные вершины имеют степени 3. (Вершина степени n-1 часто называется хабом (hub)).

Пример

Данные графы интересны тем, что число циклов в графе W_n равно n²-3n+3. Например, для W₄ число циклов равно 13.

Пример

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

Определения

Два графа могут быть одинаковыми во всем, кроме имен вершин (например, G₁=(V,E), G₂=(U,E), |V|=|U|). В этом случае говорят об изоморфизме графов.

Формально, графы G и H являются изоморфными, если существует соответствие один к одному вида

f: V(G)  V(H) такое, что

{ V_j,V_k }E(G)  f{V_j}f{V_k}E(H)

Функция f называется изоморфизмом.

Пример

1

2

1

3

5

3

4

4

2

5

6

6

Рис.2.4.1. Два изоморфных графа

Класс сложности

Неизвестен алгоритм нахождения изоморфизма графов общего вида в полиномиальное время, но не доказано, что проблема является NP-полной. Некоторые авторы выделяют отдельный класс сложности изоморфизма графов.

Алгоритмы полиномиального времени

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

Классификация алгоритмов

Алгоритмы распознавания изоморфизма графов:

• прямые переборные алгоритмы;

• алгоритмы направленного перебора;

• непереборные алгоритмы.

Перебор убыстряется с использованием:

• инвариантов;

• системы инвариантов.

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.

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

Пример