Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Связность графов, компонента связности. n-связный граф
Определение. Две вершины и в графе связны, если существует соединяющая их (простая) цепь. Если же в графе нет ни одной цепи, соединяющей вершины и , то вершины и являются несвязными.
Пример. Вершины 1 и 5 (рисунок 6.39) связны, так как их соединяет цепь 1,7,6,5 (а также 1,7,2,5; 1,7,6,2,5 и 1,7,2,6,5), а вершины 2 и 3 связными не являются, так как ни одна цепь их не соединяет.
Рисунок 6.39
Определение. Граф называется связным, если любая пара его вершин связана. Если же в графе имеется хотя бы одна пара вершин, не соединенных цепью, то граф называется несвязным.
Пример. Согласно этим определениям граф, изображенный на рисунке 32, является несвязным, а граф, приведенный на рисунке 6.40, – связным.
Рисунок 6.40
Отношение связности вершин и является рефлексивным (всякая вершина, имеющая петлю, связна сама с собой), симметричным (если вершины и связны, то связны и вершины и ), транзитивным (если вершины и связны и связны вершины и , то связны и вершины и ), следовательно, множество связных вершин образует класс эквивалентности.
Определение. Классы эквивалентности, из которых состоит несвязный граф, называются его компонентами. Между разными компонентами связности ребер нет.
Любой связный граф состоит из одной компоненты связности – всего графа.
Определение. Число компонент, из которых состоит граф, называется степенью связности. Число компонентов связности графа обозначается .
Пример. Граф, изображенный на рисунке 6.40, имеет степень связности, равную 2. Степень связности графа, приведенного на рисунке 6.41, равна 5.
Рисунок 6.41
Определение. Граф называется n-связным, если между любыми его двумя вершинами найдется цепей, попарно не имеющих общих неконцевых вершин.
Определение. Числом вершинной связности (или просто числом связности) графа называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.
Определение. Пусть – граф порядка . Числом реберной связности графа называется наименьшее число ребер, удаление которых приводит к несвязному графу.
Определение. Вершина графа называется точкой сочленения (или разделяющей вершиной), если граф имеет больше компонент, чем . В частности, если связен и – точка сочленения, то несвязен. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент. Концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине. (см. рис 6.7).
Свойства связных графов
1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.
2. Связный граф, имеющий вершин, содержит по крайней мере ребро.
3. В связном графе любые две простые цепи максимальной длины имеют по крайней мере одну общую вершину.
4. Пусть у графа есть вершин. Пусть – минимальная из степеней вершин этого графа. Тогда .
Компоненты сильной связности ориентированного графа
Определение. Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимальные по включению сильно связные подграфы.
Для нахождения компонент сольной связности в орграфе cоставляем матрицу смежности A(D) размерности (n − количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi и входящая в vj, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0).
Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической).
Алгоритм выделения компонент сильной связности
1. Присваиваем p=1 (p − количество компонент связности), .
2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.
3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p+1 и переходим к п. 2.
Пример.
Выделим компоненты связности ориентированного графа, изображенного на рис. 6.42. В данной задаче количество вершин n=5.
Рис. 6.42
Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом
.
Найдем матрицу достижимости для данного ориентированного графа:
, ,
,
Следовательно,
.
Таким образом, матрица сильной связности будет следующей:
.
Присваиваем p=1 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .
Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине v1, чтобы получить матрицу S2(D):
.
Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:
.
Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:
и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .
Таким образом, выделены три компоненты сильной связности ориентированного графа D:
|
D1: |
D2: |
D3: |
Метрические характеристики связных графов. Расстояние между вершинами графа. Диаметр, грань, граница, центр графа. Эксцентриситет вершины графа
Определение. Расстояние между вершинами и графа – это длина кратчайшей цепи между и . Если от вершины до вершины не ведет ни одна цепь, то .
В связном графе определенное таким способом расстояние удовлетворяет всем аксиомам метрики, а именно:
1. , причем только при .
2. .
3. .
Определение. Диаметром графа называется максимальное расстояние в графе .
Пример. В графе на рисунке 6.42 различные вершины соединены минимальными цепями со следующими длинами:
;
откуда следует, что диаметр графа .
Рисунок 6.42
Определение. Грань (ячейка) плоского графа (в котором ребра пересекаются только в вершинах) – это такая непустая замкнутая подобласть плоскости, что всякие две точки области можно соединить простой (Жордановой) кривой, внутренние (не концевые) точки которой лежат внутри области, не пересекаясь с ребрами графа. Другими словами, если плоскость разрезать по ребрам плоского графа, она распадется на связные части, которые называют гранями.
Определение. Границей грани считается множество ребер и вершин графа, принадлежащих грани. Всякий конечный плоский граф имеет в точности одну неограниченную грань, которая называется внешней гранью. Все остальные (ограниченные) грани называются внутренними.
Если в плоском графе нет циклов, то у него имеется только одна грань. Если же циклы есть, то граница каждой грани содержит цикл, но не обязательно является циклом.
Пример. На рисунке 6.43 показан плоский граф с пятью занумерованными гранями. Граница грани с номером 3 состоит из двух циклов, а граница грани с номером 2 кроме цикла длины 5 включает еще дерево из трех ребер.
Рисунок 6.43
Множества ребер, образующие границы граней, могут быть разными для разных плоских укладок одного и того же графа.
Пример. На рисунке 6.44 показаны две плоские укладки одного графа. В левой укладке (рисунок 6.44а) есть две грани, границы которых являются простыми циклами длины 5. В правой укладке (рисунок 6.44б) таких граней нет, но есть грани, ограниченные циклами длины 4 и 6.
а б
Рисунок 6.44
Теорема (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего вершин, ребер и компонент связности, равно .
Определение. Эксцентриситет вершины в связном графе – это расстояние от до наиболее удаленной от нее вершины.
Пример. Эксцентриситет вершины 8 графа на рисунке 6.45 равен .
Рисунок 6.45
Определение. Наименьший из эксцентриситетов называется радиусом графа .
Пример. Найдем все эксцентриситеты графа на рисунке 6.46: .
Рисунок 6.46
Наименьший эксцентриситет равен 2, следовательно, радиус графа .
Наибольший эксцентриситет равен диаметру графа.
Определение. Вершина называется центральной вершиной графа , если на ней достигается минимум эксцентриситетов, то есть .
Вершина называется периферийной, если .
Определение. Простая цепь, расстояние между концами которой равно , называется диаметральной цепью.
Пример. На рисунке 6.47 все вершины, кроме вершины 2, являются периферийными, (1,2,3) – диаметральная цепь.
Рисунок 6.47
Определение. Центром графа называется множество всех его центральных вершин; центр может состоять из единственной вершины, может – из двух и более вершин.
Пример. В графе на рисунке 6.46 два центра – вершины 3 и 5.
Центр графа может совпадать с множеством всех вершин. Например, центр простой цепи при четном числе вершин состоит ровно из двух вершин, а при нечетном – из одной; для цикла же все вершины являются центральными.
Задача нахождения центральных вершин графа постоянно возникает в практической деятельности людей. Пусть, например, граф представляет сеть дорог, т.е. вершины его соответствуют отдельным населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, магазины. В подобных ситуациях критерий оптимальности часто заключается в оптимизации «наихудшего» случая, т.е. в минимизации расстояния от места обслуживания до наиболее удаленного пункта. Следовательно, местами размещения должны быть центральные вершины графа.
Реальные задачи (их называют минимаксными задачами размещения) отличаются от идеальной тем, что приходится ещё учитывать другие обстоятельства – фактические расстояния между отдельными пунктами, стоимость, время проезда и прочее. Для того чтобы учесть это, используют взвешенные графы.
Эйлеровы графы
Определение. Эйлеров цикл (эйлерова линия, замкнутая эйлерова цепь, эйлерова цепь) – это цикл, содержащий все ребра графа.
Определение. Граф, содержащий эйлеров цикл, называется эйлеровым графом (рисунок 6.48).
Рисунок 6.48
Определение. Если граф содержит разомкнутую цепь, содержащую все ребра этого графа, то такой граф называется полуэйлеровым (рисунок 42).
Рисунок 6.49
Теорема 6.5. Если в связном графе все вершины четны, то этот граф содержит эйлеров цикл.
Верно и обратное утверждение: если граф содержит эйлеров цикл, то все его вершины четны.
Теорема 6.6. Если в связном графе две вершины нечетны, а все остальные – четны, то этот граф содержит эйлерову разомкнутую цепь.
Всякую линию, которую можно провести, проходя по заданным участкам точно по одному разу, называют уникурсальной. Применительно к эйлеровым графам провести уникурсальную линию – это значит пройти по всем ребрам графа по одному разу, не отрывая карандаш от бумаги. Заметим, что разомкнутая уникурсальная линия всегда начинается с нечетной вершины и заканчивается в другой нечетной вершине. Если же начать обход полуэйлерового графа с четной вершины, то уникурсальную линию, ни замкнутую, ни разомкнутую, построить не удастся.
Эйлеровы графы иногда называют уникурсальными.
Теорема 6.7. Если в связном графе содержится нечетных вершин, то в нем имеется разомкнутых эйлеровых цепей, в совокупности содержащих все ребра графа точно по одному разу.
Используя понятие уникурсальной линии, эту теорему можно сформулировать следующим образом: если в связном графе содержится нечетных вершин, то в нем имеется разомкнутых уникурсальных линий. Чтобы изобразить такой граф, карандаш придется оторвать от бумаги не менее раз.
Пример. Граф на рисунке 6.50 содержит четыре нечетные вершины, следовательно, . При его изображении карандаш от бумаги придется оторвать один раз. Если начать с вершины 1, то получим две уникурсальные линии: 1,3,4,2,1,2,4 и 2,3.
Рисунок 6.50
Теорема 6.8. В любом связном графе можно построить замкнутый маршрут, проходящий через каждое ребро точно два раза.
Чтобы убедиться в справедливости этой теоремы, достаточно каждое ребро графа заменить двумя параллельными ребрами и считать, что маршрут проходит по каждому ребру точно один раз. Тогда все вершины станут четными, и такой граф будет содержать эйлеров цикл.
Из этой теоремы следует, что любой граф можно изобразить, не отрывая карандаш от бумаги и проходя по каждому ребру не более двух раз.
Пример. Граф, приведенный на рисунке 6.50, можно изобразить в виде последовательности вершин так: 1,2,4,2,1,3,2,3,4, откуда следует, что два раза карандаш прошел только по ребру {2,3}.
Теорема Эйлера. Граф содержит эйлеров цикл тогда и только тогда, когда он связен и степени всех его вершин – четные.
Алгоритм нахождения эйлерова цикла (алгоритм Флери)
Шаг 1. Начиная с произвольной вершины , присвоить произвольному ребру номер 1. Затем вычеркнуть ребро и перейти в вершину .
Шаг 2. Пусть – вершина, в которую перешли в результате выполнения предыдущего шага, и – номер, присвоенный некоторому ребру на этом шаге. Выбрать любое ребро, инцидентное вершине , причём мост выбирать только в том случае, когда нет других возможностей; присвоить выбранному ребру номер и вычеркнуть его.
Шаг 3. Повторять шаг 2 пока не все ребра вычеркнуты.
Гамильтоновы графы
Определение. Гамильтонов путь (или гамильтонова цепь) – путь (цепь), содержащий каждую вершину графа ровно один раз.
Определение. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.
Понятие гамильтонова цикла впервые появилось в связи с задачей о кругосветном путешествии, которую рассматривал сэр Уильям Гамильтон: обойти все вершины графа – названия столиц различных стран – по одному разу и вернуться в исходный пункт.
Рисунок 6.51 – Додекаэдр
Задача нахождения гамильтонова цикла с наименьшим весом хорошо известна как задача коммивояжера.
Определение. Гамильтонов граф – это граф, содержащий гамильтонов цикл (рисунок 6.52).
Рисунок 6.52 – Гамильтонов граф
Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым (рисунок 6.53).
Рисунок 6.53– Полугамильтонов граф
Алгоритм Робертса-Флореса (метод перебора Робертса-Флореса) нахождения гамильтоновых циклов в графе
Алгоритм начинается с построения матрицы , где элемент есть -я вершина (допустим, ), для которой в графе существует дуга . Вершины можно упорядочить произвольно, образовав элементы -го столбца матрицы . Число строк матрицы будет равно наибольшей полустепени исхода вершины.
Рисунок 6.54 – Граф
Матрица М:
|
a |
b |
c |
d |
e |
f |
|
|
1 |
b |
c |
a |
c |
c |
a |
|
2 |
– |
e |
d |
f |
d |
b |
|
3 |
– |
– |
– |
– |
– |
c |
Все вершины по очереди записываем во множество .
Поиск всех гамильтоновых циклов производится так (вершина берется в качестве отправной вершины):
|
№ |
Множество |
Комментарии |
|
1 |
Добавляем первую возможную вершину в столбце (вершину ). |
|
|
2 |
Добавляем первую возможную вершину в столбце (вершину ). |
|
|
3 |
Первая возможная вершина в столбце не является возможной (), добавляем следующую вершину в столбце (вершину ). |
|
|
4 |
Добавляем вершину . |
|
|
5 |
В столбце нет возможных вершин. Возвращение. |
|
|
6 |
В столбце нет возможных вершин. Возвращение. |
|
|
7 |
В столбце нет возможных вершин. Возвращение. |
|
|
8 |
Добавляем вершину . |
|
|
9 |
Добавляем вершину . |
|
|
10 |
Добавляем вершину . |
|
|
11 |
Добавляем вершину . |
|
|
12 |
Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение. |
|
|
13 |
Возвращение. |
|
|
14 |
Возвращение. |
|
|
15 |
Добавляем вершину . |
|
|
16 |
Добавляем вершину . |
|
|
17 |
Добавляем вершину . |
|
|
18 |
Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение. |
|
|
19 |
Возвращение. |
|
|
20 |
Возвращение. |
|
|
21 |
Возвращение. |
|
|
22 |
Возвращение. |
|
|
23 |
Возвращение. |
|
|
24 |
Конец поиска. |
В результате получаем два гамильтоновых цикла (рис. 6.55).
Рисунок 6.55 – Гамильтоновы циклы в графе
Определение. Реберным графом графа называется граф имеющий столько же вершин, сколько ребер у графа . Ребро между двумя вершинами графа существует тогда и только тогда, когда ребра графа , соответствующие этим двум вершинам, смежны (т. е. инцидентны одной и той же вершине графа ).
Пример. На рисунке 6.56 изображен исходный граф, а на рисунке 47 – соответствующий ему реберный.
Рисунок 6.56
Рисунок 6.57
Гамильтонов граф является двусвязным, так как между каждой парой вершин существует не менее чем две различные простые цепи.
Признаки существования гамильтоновых циклов, путей и контуров
Общий признак, при помощи которого для любого графа можно было бы определить, имеет он гамильтонов цикл или нет, не найден до сих пор. Существуют некоторые достаточные условия гамильтоновости графа (все графы предполагаются связными и простыми).
Если в графе есть висячая вершина (со степенью, равной единице), то гамильтонов цикл в нем отсутствует (рисунок 6.58).
Рисунок 6.58
Теорема (условие Дирака). Если число вершин графа не менее трех и степень любой вершины не менее , то граф является гамильтоновым.
Теорема (условие Оре). Если в графе с вершинами () сумма степеней любых двух вершин и является не меньшей, чем (), то граф является гамильтоновым.
Теорема Бонди-Хватала. Пусть для упорядоченной по возрастанию последовательности степеней вершин , , графа выполнены импликации , , тогда – гамильтонов граф.
Теорема (условие Харари). Реберный граф гамильтонов тогда и только тогда, когда в существует цикл, содержащий хотя бы по одной вершине из каждого ребра графа .
Следствие. Если граф либо эйлеров, либо гамильтонов, то реберный граф гамильтонов.
Теорема (признак Кенига). В полном орграфе (любая пара вершин которого соединяется хотя бы в одном направлении) всегда существует гамильтонов путь.