2.3. Некоторые виды графов

2

Определения

.3.1. Регулярные графы

Граф будет r- регулярным (или регулярным степени r), если каждая его вершина имеет степень r.

Следствие леммы рукопожатий: не существует r-регулярный граф на п вершинах, если r u n оба нечётны. Справедливо следующее обратное утверждение: r регулярный граф на п вершинах существует тогда и только тогда, когда r или п чётны(или они четны оба).

Пример

r =4

n =12

Рис.2.3.1. Регулярные графы

2.3.2. Полные графы

Определения

Полным графом будет граф, каждая вершина которого соединена с другой вершиной точно одним ребром. Полный граф с mвершинами обозначаетсяK_m. К_mявляется (m-1) – регулярным и имеет m(m-1) рёбер.

Пример

Рис.2.3.2. Примеры полных графов

2.3.3. Двудольные графы

Двудольный граф – это граф, у которого вершины разделены на два подмножества А и В таким образом, что каждая дуга графаGсоединяет одну вершину подмножества А и одну вершину подмножества В.

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

Пример

Определения

Полным двудольным графомназывается двудольный граф, у которого каждая вершина подмножества А соединена с каждой вершиной подмножества В только одним ребром. Полный двудольный граф сrиsвершинами имеет специальное обозначениеK_rs.

При r=sзавершенный двудольный граф называетсясбалансированным.

Пример

Рис.2.3.4. Примеры полных двудольных графов (К_2,2 –сбалансированный двудольный граф)

2.3.4. Граф звезда

Определения

Граф звездаявляется деревом на (n+1) вершине, из которых одна является смежнойnвершинам, а остальные вершины имеют степень 1. Граф звезда имеет специальное обозначениеS_n.

Пример

Рис.2.3.5. Примеры графов звезда

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. Изоморфизм графов и прямые методы