Гамма-алгоритм (в общем виде) 1 страница

 

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

2. (Общий шаг). Пока множество сегментов непустое:

a. Для каждого сегмента найти множество . Если существует сегмент , для которого , то граф не планарный, конец.

b. Выбираем один из сегментов с минимальным числом, вмещающих его граней.

c. Выбираем одну из подходящих граней для выбранного сегмента.

d. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).

3. (Завершение). Построена плоская укладка исходного графа , конец.

 

9.4 Контрольные вопросы и задания

 

1. Перечислите операции, которые можно производить над графами.

2. Охарактеризуйте операции удаления ребер и вершин.

3. Какой граф называется дополнением графа ?

4. Как определить композицию графов и . Приведите пример.

5. Дайте характеристику операции соединения (сильного произведения) графов.

6. Какие графы называются гомеоморфными графами.

7. Какие графы называются изоморфными графами.

8. Дайте определения плоского графа, планарного графа.

9. Для решения каких задач можно использовать теорему Понтрягина – Куратовского?

10. Для решения каких задач можно использовать теорему Жордана?

11. Для плоской укладки графа и попутной проверки, планарный ли он, можно использовать гамма-алгоритм?

12. Приведите гамма-алгоритм в общем виде.

 

Лекция 20. Связность графов. Эйлеровы и гамильтоновы графы

 

20.1 Связность графов, компонента связности. n-связный граф

Определение. Две вершины и в графе связны, если существует соединяющая их (простая) цепь. Если же в графе нет ни одной цепи, соединяющей вершины и , то вершины и являются несвязными.

Пример. Вершины 1 и 5 (рис. 20.1) связны, так как их соединяет цепь 1,7,6,5 (а также 1,7,2,5; 1,7,6,2,5 и 1,7,2,6,5), а вершины 2 и 3 связными не являются, так как ни одна цепь их не соединяет.

Рисунок 20.1

 

Определение. Граф называется связным, если любая пара его вершин связана. Если же в графе имеется хотя бы одна пара вершин, не соединенных цепью, то граф называется несвязным.

Пример. Согласно этим определениям граф, изображенный на рис. 20.1, является несвязным, а граф, приведенный на рис. 20.2, – связным.

Рисунок 20.2

 

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

Определение. Классы эквивалентности, из которых состоит несвязный граф, называются его компонентами. Между разными компонентами связности ребер нет.

Любой связный граф состоит из одной компоненты связности – всего графа.

Определение. Число компонент, из которых состоит граф, называется степенью связности. Число компонентов связности графа обозначается .

Пример. Граф, изображенный на рисунке 20.2, имеет степень связности, равную 2. Степень связности графа, приведенного на рис. 20.3, равна 5.

Рисунок 20.3

 

Определение. Граф называется n-связным, если между любыми его двумя вершинами найдется цепей, попарно не имеющих общих неконцевых вершин.

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

Определение. Пусть – граф порядка . Числом реберной связности графа называется наименьшее число ребер, удаление которых приводит к несвязному графу.

Определение. Вершина графа называется точкой сочленения (или разделяющей вершиной), если граф имеет больше компонент, чем . В частности, если связен и – точка сочленения, то несвязен. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент. Концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине.

 

20.2 Свойства связных графов

 

1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.

2. Связный граф, имеющий вершин, содержит по крайней мере ребро.

3. В связном графе любые две простые цепи максимальной длины имеют по крайней мере одну общую вершину.

4. Пусть у графа есть вершин. Пусть – минимальная из степеней вершин этого графа. Тогда .

 

20.3 Компоненты сильной связности ориентированного графа

 

Определение. Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимальные по включению сильно связные подграфы.

Для нахождения компонент сольной связности в орграфе cоставляем матрицу смежности A (D) размерности (n − количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины v_i и входящая в v_j, то элемент матрицы смежности, стоящий на пересечении i -той строки и j -того столбца равен 1, иначе – 0).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T (D) ориентированного графа, затем находим матрицу сильной связности S (D) ориентированного графа (она должна быть симметрической).

 

20.4 Алгоритм выделения компонент сильной связности

1. Присваиваем p =1 (p − количество компонент связности), .

2. Включаем в множество вершин V_p компоненты сильной связности D_p вершины, соответствующие единицам первой строки матрицы S_p. В качестве матрицы A (D_p) возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V_p.

3. Вычеркиваем из S_p строки и столбцы, соответствующие вершинам из V_p. Если не остается ни одной строки (и столбца), то p - количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как S_p+1, присваиваем p=p +1 и переходим к п. 2.

Пример.

Выделим компоненты связности ориентированного графа, изображенного на рис. 20.4. В данной задаче количество вершин n= 5.

Рисунок 20.4

 

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

.

Найдем матрицу достижимости для данного ориентированного графа:

, ,

,

Следовательно,

.

Таким образом, матрица сильной связности будет следующей:

.

Присваиваем p =1 и составляем множество вершин первой компоненты сильной связности D ₁: это те вершины, которым соответствуют единицы в первой строке матрицы S (D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S ₁(D) строку и столбец, соответствующие вершине v ₁, чтобы получить матрицу S ₂(D):

.

Присваиваем p =2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S ₂(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A (D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V ₂:

.

Вычеркиваем из матрицы S ₂(D) строки и столбцы, соответствующие вершинам из V ₂,чтобы получить матрицу S ₃(D), которая состоит из одного элемента: и присваиваем p =3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены три компоненты сильной связности ориентированного графа D (рис. 20.5):

D 1:

D 2: Рисунок 20.5

D 3:

20.5 Метрические характеристики связных графов

Определение. Расстояние между вершинами и графа – это длина кратчайшей цепи между и . Если от вершины до вершины не ведет ни одна цепь, то .

В связном графе определенное таким способом расстояние удовлетворяет всем аксиомам метрики, а именно:

1. , причем только при .

2. .

3. .

Определение. Диаметром графа называется максимальное расстояние в графе .

Пример. В графе на рис. 20.6 различные вершины соединены минимальными цепями со следующими длинами:

;

откуда следует, что диаметр графа .

Рисунок 20.6

Определение. Грань (ячейка) плоского графа (в котором ребра пересекаются только в вершинах) – это такая непустая замкнутая подобласть плоскости, что всякие две точки области можно соединить простой (Жордановой) кривой, внутренние (не концевые) точки которой лежат внутри области, не пересекаясь с ребрами графа. Другими словами, если плоскость разрезать по ребрам плоского графа, она распадется на связные части, которые называют гранями.

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

Если в плоском графе нет циклов, то у него имеется только одна грань. Если же циклы есть, то граница каждой грани содержит цикл, но не обязательно является циклом.

Пример. На рис. 20.7 показан плоский граф с пятью занумерованными гранями. Граница грани с номером 3 состоит из двух циклов, а граница грани с номером 2 кроме цикла длины 5 включает еще дерево из трех ребер.

Рисунок 20.7

 

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

Пример. На рис. 20.8 показаны две плоские укладки одного графа. В левой укладке (рис. 20.8 а)) есть две грани, границы которых являются простыми циклами длины 5. В правой укладке (рис. 20.8 б)) таких граней нет, но есть грани, ограниченные циклами длины 4 и 6.

а) б)

Рисунок 20.8

 

Теорема (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего вершин, ребер и компонент связности, равно .

Определение. Эксцентриситет вершины в связном графе – это расстояние от до наиболее удаленной от нее вершины.

Пример. Эксцентриситет вершины 8 графа на рис. 20.9 равен .

Рисунок 20.9

 

Определение. Наименьший из эксцентриситетов называется радиусом графа .

Пример. Найдем все эксцентриситеты графа на рис. 20.10: .

Рисунок 20.10

 

Наименьший эксцентриситет равен 2, следовательно, радиус графа . Наибольший эксцентриситет равен диаметру графа.

Определение. Вершина называется центральной вершиной графа , если на ней достигается минимум эксцентриситетов, то есть .

Вершина называется периферийной, если .

Определение. Простая цепь, расстояние между концами которой равно , называется диаметральной цепью.

Пример. На рис. 20.11 все вершины, кроме вершины 2, являются периферийными, (1,2,3) – диаметральная цепь.

Рисунок 20.11

 

Определение. Центром графа называется множество всех его центральных вершин; центр может состоять из единственной вершины, может – из двух и более вершин.

Пример. В графе на рис. 20.10 два центра – вершины 3 и 5.

Центр графа может совпадать с множеством всех вершин. Например, центр простой цепи при четном числе вершин состоит ровно из двух вершин, а при нечетном – из одной; для цикла же все вершины являются центральными.

Задача нахождения центральных вершин графа постоянно возникает в практической деятельности людей. Пусть, например, граф представляет сеть дорог, т.е. вершины его соответствуют отдельным населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, магазины.

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

Реальные задачи (их называют минимаксными задачами размещения) отличаются от идеальной тем, что приходится ещё учитывать другие обстоятельства – фактические расстояния между отдельными пунктами, стоимость, время проезда и прочее. Для того чтобы учесть это, используют взвешенные графы.

 

20.6 Эйлеровы графы

Определение. Эйлеров цикл (эйлерова линия, замкнутая эйлерова цепь, эйлерова цепь) – это цикл, содержащий все ребра графа.

Определение. Граф, содержащий эйлеров цикл, называется эйлеровым графом (рис 20.12).

Рисунок 20.12

 

Определение. Если граф содержит разомкнутую цепь, содержащую все ребра этого графа, то такой граф называется полуэйлеровым (рис. 20.13).

Рисунок 20.13

 

Теорема 20. 1. Если в связном графе все вершины четны, то этот граф содержит эйлеров цикл.

Верно и обратное утверждение: если граф содержит эйлеров цикл, то все его вершины четны.

Теорема 20. 2. Если в связном графе две вершины нечетны, а все остальные – четны, то этот граф содержит эйлерову разомкнутую цепь.

Определение. Всякую линию, которую можно провести, проходя по заданным участкам точно по одному разу, называют уникурсальной.

Применительно к эйлеровым графам провести уникурсальную линию – это значит пройти по всем ребрам графа по одному разу, не отрывая карандаш от бумаги. Заметим, что разомкнутая уникурсальная линия всегда начинается с нечетной вершины и заканчивается в другой нечетной вершине. Если же начать обход полуэйлерового графа с четной вершины, то уникурсальную линию, ни замкнутую, ни разомкнутую, построить не удастся.

Эйлеровы графы иногда называют уникурсальными.

 

Теорема 20. 3. Если в связном графе содержится нечетных вершин, то в нем имеется разомкнутых эйлеровых цепей, в совокупности содержащих все ребра графа точно по одному разу.

Используя понятие уникурсальной линии, эту теорему можно сформулировать следующим образом: если в связном графе содержится нечетных вершин, то в нем имеется разомкнутых уникурсальных линий. Чтобы изобразить такой граф, карандаш придется оторвать от бумаги не менее раз.

Пример. Граф на рис. 20.14 содержит четыре нечетные вершины, следовательно, . При его изображении карандаш от бумаги придется оторвать один раз. Если начать с вершины 1, то получим две уникурсальные линии: 1,3,4,2,1,2,4 и 2,3.

Рисунок 20.14

 

Теорема 20.4. В любом связном графе можно построить замкнутый маршрут, проходящий через каждое ребро точно два раза.