Файл: Учебника по курсу Основы дискретной математики и логики.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 243
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
. Другими словами, в полном графе каждая вершина соединяется ребрами со всеми другими вершинами. Полный граф имеет максимально возможное число ребер.
Обозначение полного графа с p[пэ] вершинами и правило нахождения числа его ребер приведены в формуле (3.28). Обоснуем указанное правило. Если рассматриваемый граф имеет p[пэ] вершин, то из каждой его вершины выходит p − 1[пэ минус одно] ребро. Тогда из всех p[пэ] вершин выходит p(p
− 1)[пэ, умноженное на пэ минус один] ребер. При таком подсчете каждое ребро было учтено два раза. Поэтому окончательный ответ получаем делением этого произведения на два.
На рис. 3.21 изображены полные графы с тремя, четырьмя и пятью вершинами.
Слайд 75
Пусть G[жэ] – неориентированный граф без кратных ребер, имеющий множество вершин V[вэ] и множество ребер E[е]. Граф G[жэ] называется двудольным, если множество его вершин разбито на непересекающиеся подмножества V
1
[вэ один] и V
2
[вэ два] и всякое ребро инцидентно вершине из V
1
[вэ один] и вершине из V
2
[вэ два]. Множества V
1
[вэ один] и V
2
[вэ два] называются долями двудольного графа.
Если в двудольном графе каждая вершина из V
1
[вэ один] соединяется ребрами со всеми вершинами из V
2
[вэ два], то граф называется полным
Если, наоборот, исходный граф состоит из одних лишь вершин, то дополнительным к нему будет полный граф с теми же вершинами.
Если граф D[дэ] является дополнением графа G[жэ], а граф F[эф] дополнением графа D[дэ], то графы G[жэ] и F[эф] совпадают.
Слайд 80
Пусть G[жэ] – неориентированный граф, в котором для любых двух вершин существует соединяющая их цепь.
Расстоянием между вершинами u[у] и v[вэ]
называется длина кратчайшей цепи, соединяющей эти вершины. Обозначение для расстояния между вершинами графа приведено в формуле (3.34).
Наибольшее из расстояний между вершинами графа называется диаметром графа.
Максимальное удаление от вершины v[вэ] в графе G[жэ] определяется формулой (3.35).
Центром графа называется вершина с наименьшим максимальным удалением от нее.
Максимальное удаление от центра называется радиусом графа.
Формула (3.36) определяет радиус графа с помощью математических символов.
Центр не обязательно единственный. В полном графе радиус равен 1 и любая вершина является центром.
Множество вершин, находящихся на одинаковом расстоянии от вершины v[вэ], называется ярусом вершины v[вэ].
Для графа D[дэ], изображенного на рис. 3.30, диаметр равен двум, радиус – единице, центром графа является вершина 4.
Слайд 81
Рассмотрим граф, изображенный на рис. 3.31. Расстояния между его вершинами представлены соотношениями (3.37). Диаметр графа равен
Одной из характеристик орграфа является число его компонент сильной связности. Обозначение для данной величины приведено в формуле
(3.41). Орграф G[жэ] является сильно связным тогда и только тогда, когда он имеет одну компоненту сильной связности.
Граф G[жэ], изображенный на рис. 3.33, не является сильно связным, так как имеет три компоненты сильной связности. Им соответствуют множества вершин, представляемые формулой (3.42). Сами компоненты сильной связности графа G изображены на рис. 3.34.
Слайд 84
Орграф G[жэ] называется односторонне связным, если для любых его вершин и u[у] и v[вэ] существует либо путь из u[у] в v[вэ], либо путь из v[вэ] в u[у].
Очевидно, что если орграф является сильно связным, то он будет и односторонне связным.
Граф, изображенный на рис. 3.35, не является односторонне связным, так как, скажем, из вершины 1 нет пути в вершину 5 и, наоборот, из вершины
5 нет пути в вершину 1.
На рис. 3.36, а представлен односторонне связный граф, не являющийся сильно связным.
Пусть G[жэ] – ориентированный граф, имеющий множество вершин
V[вэ] и множество ребер E[е].
Графом, ассоциированным с орграфом
G[жэ], называется неориентированный граф G
1
[жэ один], имеющий то же множество вершин
V[вэ] и множество ребер E
1
[е один] получающееся из множества E[е] заменой всех дуг на неориентированные ребра.
Орграф G[жэ] называется слабо связным, если ассоциированный с ним неориентированный граф является связным.
На рис. 3.36, б представлен слабо связный граф, не являющийся односторонне связным.
Слайд 85
Рассмотрим способ нахождения компонент связности с помощью ЭВМ.
Чтобы в n[эн]-вершинном графе или орграфе G[же] существовал маршрут из вершины v
i
[вэ итое] в вершину v
j
[вэ житое], необходимо и достаточно, чтобы итый-житый элемент матрицы 3.43 был отличен от нуля.
Составим из матрицы B[бэ], определенной в формуле (3.44), матрицу
C[цэ], используя правило (3.45).
Матрица C называется матрицей связности, если G[же] – неориентированный граф, и матрицей достижимости, если G[же] – орграф.
Граф G[же] будет содержать маршрут из вершины v
i
[вэ итое] в вершину v
j
[вэ житое] тогда и только тогда, когда элемент C
ij
[цэ итое житое] равен 1.
Значит, матрица C[цэ] содержит информацию о существовании связей между различными элементами графа с помощью маршрутов. Если все элементы матрицы связности равны единице, то граф является связным.
В случае неориентированного графа матрица C[цэ] совпадает с транспонированной и является матрицей связности.
В случае ориентированного графа транспонированная матрица C[цэ] называется матрицей контрдостижимости, так как если итый-житый элемент матрицы
C[цэ] показывает наличие пути из вершины v
i
[вэ итое] в вершину v
j
[вэ житое], то житый-итый элемент транспонированной матрицы показывает наличие обратного пути из вершины вэ житое в вершину вэ итое.
Матрицы достижимости и контрдостижимости можно использовать для нахождения сильных компонент орграфа.
Рассмотрим матрицу, определенную в формуле (3.46), где операция звездочка означает поэлементное произведение матриц. Элемент матрицы
S[эс] равен 1 тогда и только тогда, когда вершины v
i
[вэ итое] и v
j
[вэ житое] взаимно достижимы. Следовательно, компонента сильной связности, содержащая вершину v
i
[вэ итое], состоит из элементов v
j
[вэ житое], для которых элемент v
ij
[вэ итое-житое] равен единице.
Слайд 86
Тема 3.3. Деревья. Остов графа. Понятия планарного, эйлерова и гамильтонова графов
Деревья заслуживают отдельного и подробного рассмотрения по двум причинам.
Деревья являются в некотором смысле простейшим классом графов.
Для них выполняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять на деревьях.
Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях.
Неориентированный связный граф без циклов называется деревом, или свободным деревом. Граф, состоящий из нескольких деревьев, называется лесом. Таким образом, компонентами связности леса являются деревья.
Примеры деревьев представлены на рис. 3.37, 3.38.
Слайд 87
На рис. 3.39 изображены диаграммы всех различных деревьев с 5 вершинами, а на рис. 3.40 – диаграммы всевозможных деревьев с 6 вершинами.
Для всякого неориентированного графа G[жэ] следующие утверждения эквивалентны.
1. G[жэ]
– дерево, то есть связный граф без циклов.
2. Любые две вершины соединены в G[жэ] единственной простой цепью.
3. G[жэ]– связный граф, и удаление любого ребра делает граф несвязным.
4. G[жэ] – связный граф, в котором число ребер на единицу меньше числа вершин.
Обозначение полного графа с p[пэ] вершинами и правило нахождения числа его ребер приведены в формуле (3.28). Обоснуем указанное правило. Если рассматриваемый граф имеет p[пэ] вершин, то из каждой его вершины выходит p − 1[пэ минус одно] ребро. Тогда из всех p[пэ] вершин выходит p(p
− 1)[пэ, умноженное на пэ минус один] ребер. При таком подсчете каждое ребро было учтено два раза. Поэтому окончательный ответ получаем делением этого произведения на два.
На рис. 3.21 изображены полные графы с тремя, четырьмя и пятью вершинами.
Слайд 75
Пусть G[жэ] – неориентированный граф без кратных ребер, имеющий множество вершин V[вэ] и множество ребер E[е]. Граф G[жэ] называется двудольным, если множество его вершин разбито на непересекающиеся подмножества V
1
[вэ один] и V
2
[вэ два] и всякое ребро инцидентно вершине из V
1
[вэ один] и вершине из V
2
[вэ два]. Множества V
1
[вэ один] и V
2
[вэ два] называются долями двудольного графа.
Если в двудольном графе каждая вершина из V
1
[вэ один] соединяется ребрами со всеми вершинами из V
2
[вэ два], то граф называется полным
двудольным графом. Обозначение полного двудольного графа в случае, когда множество V
1
[вэ один] имеет n[эн]элементов, а множество V
2
[вэ два] −
m[эм] элементов, приведено в формуле (3.29). На рис. 3.22 изображен полный двудольный граф с тремя вершинами в каждой доле. К первой доле относятся вершины верхнего ряда, ко второй – вершины нижнего ряда.
Cлайд 76
Рассмотрим другие примеры полных двудольных графов. Обратимся к рис. 3.23. На нем изображены графы K
1,2
[ка один два], K
5,1
[ка пять один ]и K
4,3
[ка четыре три ]. В первую долю графа K
1,2
[ка один два] входит вершина 1, во вторую – вершины 2 и 3. В графе K
5,1
[ка пять один] одна доля образована вершинами 1, 2, 3, 4, 5, другая состоит из одной вершины 6. К первой доле графа K
4,3
[ка четыре три] относятся относятся вершины 1, 2, 3, 4, ко второй – вершины 5, 6, 7.
Граф K
1,2
[ка один два] имеет два ребра, граф K
5,1
[ка пять один] – пять ребер, в графе K
4,3
[ка четыре три] двенадцать ребер. В общем случае количество ребер полного двудольного графа равно произведению числа вершин первой доли и числа вершин второй доли.
На рис. 3.24 изображены двудольные графы G[жэ] и D[дэ], не являющиеся полными. Граф G[жэ] имеет шесть вершин и пять ребер. К первой доле относятся вершины 1, 2, 3, ко второй – вершины 4, 5, 6. У графа
D[дэ] семь вершин и пять ребер. Первую долю образуют вершины 1, 2, 3, 4, вторую – вершины 5, 6,7.
Cлайд 77
Всякий неориентированный граф можно сделать ориентированным, заменив каждое ребро парой дуг, идущих в противоположных направлениях.
Будем называть смешанными графы, которые могут содержать и неориентированные ребра, и дуги. Неориентированные графы и орграфы являются частными случаями смешанных графов. Говоря об операциях над
1
[вэ один] имеет n[эн]элементов, а множество V
2
[вэ два] −
m[эм] элементов, приведено в формуле (3.29). На рис. 3.22 изображен полный двудольный граф с тремя вершинами в каждой доле. К первой доле относятся вершины верхнего ряда, ко второй – вершины нижнего ряда.
Cлайд 76
Рассмотрим другие примеры полных двудольных графов. Обратимся к рис. 3.23. На нем изображены графы K
1,2
[ка один два], K
5,1
[ка пять один ]и K
4,3
[ка четыре три ]. В первую долю графа K
1,2
[ка один два] входит вершина 1, во вторую – вершины 2 и 3. В графе K
5,1
[ка пять один] одна доля образована вершинами 1, 2, 3, 4, 5, другая состоит из одной вершины 6. К первой доле графа K
4,3
[ка четыре три] относятся относятся вершины 1, 2, 3, 4, ко второй – вершины 5, 6, 7.
Граф K
1,2
[ка один два] имеет два ребра, граф K
5,1
[ка пять один] – пять ребер, в графе K
4,3
[ка четыре три] двенадцать ребер. В общем случае количество ребер полного двудольного графа равно произведению числа вершин первой доли и числа вершин второй доли.
На рис. 3.24 изображены двудольные графы G[жэ] и D[дэ], не являющиеся полными. Граф G[жэ] имеет шесть вершин и пять ребер. К первой доле относятся вершины 1, 2, 3, ко второй – вершины 4, 5, 6. У графа
D[дэ] семь вершин и пять ребер. Первую долю образуют вершины 1, 2, 3, 4, вторую – вершины 5, 6,7.
Cлайд 77
Всякий неориентированный граф можно сделать ориентированным, заменив каждое ребро парой дуг, идущих в противоположных направлениях.
Будем называть смешанными графы, которые могут содержать и неориентированные ребра, и дуги. Неориентированные графы и орграфы являются частными случаями смешанных графов. Говоря об операциях над
графами, под словом «граф» мы будем понимать смешанный граф, а под словом «ребро» – неориентированное ребро или дугу. Для того чтобы различать неориентированные ребра и дуги, для обозначения первых мы будем использовать квадратные скобки, а для обозначения вторых – круглые скобки.
Пусть G[жэ] – граф с множеством вершин V[вэ] и множеством ребер
E[е], G
1
[жэ один] – граф со множеством вершин V
1
[вэ один] и множеством ребер E
1
[е один]. Говорят, что граф G
1
[жэ один] является подграфом графа
G[жэ], если V
1
[вэ один] является подмножеством V[вэ], а E
1
[е один] – подмножеством E[е]. Подграф G
1
[жэ один] называется собственным подграфом графа G[жэ], если G
1
[жэ один] не совпадает с G[жэ].
Пусть граф G
1
[жэ один] имеет множество вершин V
1
[вэ один] и множество ребер E
1
[е один], а граф G
2
[жэ два] множество вершин V
2
[вэ два] и множество ребер E
2
[е два].
Объединением графов G
1
[жэ один] и G
2
[жэ два] называется граф G[жэ], определяемый формулой (3.30). Формула (3.31) задает граф, являющийся пересечением графов G
1
[жэ один] и G
2
[жэ два], а формула (3.32) определяет симметрическую разность, или сумму по модулю 2, графов G
1
[жэ один] и
G
2
[жэ два].
Пусть G[жэ] граф с n[эн]вершинами без петель и кратных ребер. На множестве его вершин V[вэ] построим полный граф, имеющий множество ребер M[эм]. Дополнением графа G[жэ] называется граф, определяемый формулой (3.33).
Слайд 78
Рассмотрим графы G
1
[жэ один] и G
2
[жэ два], изображенные на рис.
3.25, а и 3.25, б соответственно. Вершины a
1
[а один] и a
2
[а два] графа G
1
[жэ один] соединяет неориентированное ребро, то есть двигаться по нему можно как от a
1
[а один] к a
2
[а два], так и от a
2
[а два] к a
1
[а один]. Поэтому мы рассматриваем его как совокупность двух дуг. Остальные ребра данных
Пусть G[жэ] – граф с множеством вершин V[вэ] и множеством ребер
E[е], G
1
[жэ один] – граф со множеством вершин V
1
[вэ один] и множеством ребер E
1
[е один]. Говорят, что граф G
1
[жэ один] является подграфом графа
G[жэ], если V
1
[вэ один] является подмножеством V[вэ], а E
1
[е один] – подмножеством E[е]. Подграф G
1
[жэ один] называется собственным подграфом графа G[жэ], если G
1
[жэ один] не совпадает с G[жэ].
Пусть граф G
1
[жэ один] имеет множество вершин V
1
[вэ один] и множество ребер E
1
[е один], а граф G
2
[жэ два] множество вершин V
2
[вэ два] и множество ребер E
2
[е два].
Объединением графов G
1
[жэ один] и G
2
[жэ два] называется граф G[жэ], определяемый формулой (3.30). Формула (3.31) задает граф, являющийся пересечением графов G
1
[жэ один] и G
2
[жэ два], а формула (3.32) определяет симметрическую разность, или сумму по модулю 2, графов G
1
[жэ один] и
G
2
[жэ два].
Пусть G[жэ] граф с n[эн]вершинами без петель и кратных ребер. На множестве его вершин V[вэ] построим полный граф, имеющий множество ребер M[эм]. Дополнением графа G[жэ] называется граф, определяемый формулой (3.33).
Слайд 78
Рассмотрим графы G
1
[жэ один] и G
2
[жэ два], изображенные на рис.
3.25, а и 3.25, б соответственно. Вершины a
1
[а один] и a
2
[а два] графа G
1
[жэ один] соединяет неориентированное ребро, то есть двигаться по нему можно как от a
1
[а один] к a
2
[а два], так и от a
2
[а два] к a
1
[а один]. Поэтому мы рассматриваем его как совокупность двух дуг. Остальные ребра данных
графов являются ориентированными, то есть двигаться по ним можно только в направлении стрелок. Граф, являющийся объединением данных графов, изображен на рис. 3.25, в. Для его построения мы объединяем множества вершин и множества ребер исходных графов. Результатом объединения ориентированного ребра с неориентированным, соединяющим те же вершины, является неориентированное ребро.
На рис. 3.25, г представлен граф, получающийся в результате применения к исходным графам операции пересечения. Он состоит только из одного ориентированного ребра, так как пересечением неориентированного ребра с ориентированным, соединяющим те же вершины, является ориентированное ребро. Других общих ребер у исходных графов нет.
Граф, представляющий собой симметрическую разность заданных графов, изображен на рис. 3.25, д. Все три его ребра являются ориентированными. Множество его вершин получается в результате объединения множеств вершин исходных графов. Множество ребер представляет собой симметрическую разность множеств ребер графов G
1
[жэ один] и G
2
[жэ два]. Для нахождения этой разности из множества ребер первого графа убираем те ребра, которые есть во втором графе.
Слайд 79
Остановимся на примерах графов, дополнительных к данным.
Рассмотрим граф G[жэ], изображенный на рис. 3.26. Он имеет два неориентированных ребра и одно ориентированное. Дополнительный к нему граф представлен на рис. 3.27. Ему принадлежат те и только те ребра, которых нет в графе G[жэ]. Одно из них ориентированное, три – неориентированные.
Отметим, что если исходный граф является полным, то его дополнением будет граф, имеющий те же вершины и не имеющий ребер. На рис. 3.28 изображен полный граф D[дэ], а на рис. 3.29 – его дополнение.
На рис. 3.25, г представлен граф, получающийся в результате применения к исходным графам операции пересечения. Он состоит только из одного ориентированного ребра, так как пересечением неориентированного ребра с ориентированным, соединяющим те же вершины, является ориентированное ребро. Других общих ребер у исходных графов нет.
Граф, представляющий собой симметрическую разность заданных графов, изображен на рис. 3.25, д. Все три его ребра являются ориентированными. Множество его вершин получается в результате объединения множеств вершин исходных графов. Множество ребер представляет собой симметрическую разность множеств ребер графов G
1
[жэ один] и G
2
[жэ два]. Для нахождения этой разности из множества ребер первого графа убираем те ребра, которые есть во втором графе.
Слайд 79
Остановимся на примерах графов, дополнительных к данным.
Рассмотрим граф G[жэ], изображенный на рис. 3.26. Он имеет два неориентированных ребра и одно ориентированное. Дополнительный к нему граф представлен на рис. 3.27. Ему принадлежат те и только те ребра, которых нет в графе G[жэ]. Одно из них ориентированное, три – неориентированные.
Отметим, что если исходный граф является полным, то его дополнением будет граф, имеющий те же вершины и не имеющий ребер. На рис. 3.28 изображен полный граф D[дэ], а на рис. 3.29 – его дополнение.
Если, наоборот, исходный граф состоит из одних лишь вершин, то дополнительным к нему будет полный граф с теми же вершинами.
Если граф D[дэ] является дополнением графа G[жэ], а граф F[эф] дополнением графа D[дэ], то графы G[жэ] и F[эф] совпадают.
Слайд 80
Пусть G[жэ] – неориентированный граф, в котором для любых двух вершин существует соединяющая их цепь.
Расстоянием между вершинами u[у] и v[вэ]
называется длина кратчайшей цепи, соединяющей эти вершины. Обозначение для расстояния между вершинами графа приведено в формуле (3.34).
Наибольшее из расстояний между вершинами графа называется диаметром графа.
Максимальное удаление от вершины v[вэ] в графе G[жэ] определяется формулой (3.35).
Центром графа называется вершина с наименьшим максимальным удалением от нее.
Максимальное удаление от центра называется радиусом графа.
Формула (3.36) определяет радиус графа с помощью математических символов.
Центр не обязательно единственный. В полном графе радиус равен 1 и любая вершина является центром.
Множество вершин, находящихся на одинаковом расстоянии от вершины v[вэ], называется ярусом вершины v[вэ].
Для графа D[дэ], изображенного на рис. 3.30, диаметр равен двум, радиус – единице, центром графа является вершина 4.
Слайд 81
Рассмотрим граф, изображенный на рис. 3.31. Расстояния между его вершинами представлены соотношениями (3.37). Диаметр графа равен
наибольшему из расстояний, то есть четырем. Из равенств (3.37) находим максимальные удаления от вершин графа G[жэ]. Их значения определяются формулами (3.38). Центрами графа являются вершины 1, 2, 4 и 5 с наименьшим максимальным удалением. Радиус графа G[жэ] равен максимальному удалению от центра, то есть двум.
Вершина 1 имеет 4 яруса. Первый ярус образуют вершины 2 и 3, второй – вершины 4 и 5, третий – вершина 6, четвертый – вершина 7.
Столько же ярусов имеет вершина 7.
У вершины 2 графа 3 яруса. Один из них образован вершинами 1 и 5, другой – вершинами 3, 4 и 6, третий – вершиной 3. Вершины 3 и 6 также имеют по 3 яруса.
Число ярусов вершины 4 равно двум. Первый ярус состоит из вершин
3, 5 и 6, второй – из вершин 1, 2 и 7. Столько же ярусов у вершины 5.
Слайд 82
Пусть G[жэ] – неориентированный граф.
Говорят, что вершины u[у] и v[вэ] в графе G[жэ] связаны отношением достижимости, если существует соединяющая их цепь. Граф, в котором любые две вершины связаны отношением достижимости, называется связным. Тривиальный граф, состоящий из изолированной вершины, по определению считается связным. Граф, не являющийся связным, называется несвязным.
Отношение достижимости вершин является отношением эквивалентности.
Компонентой связности графа G[жэ] называется такой его связный подграф, который не является собственным подграфом никакого другого связного подграфа графа G[жэ].
Классы эквивалентности по отношению достижимости образуют разбиение множества вершин графа G[жэ] на подмножества вершин, входящих в одну компоненту связности. Для построения компоненты
Вершина 1 имеет 4 яруса. Первый ярус образуют вершины 2 и 3, второй – вершины 4 и 5, третий – вершина 6, четвертый – вершина 7.
Столько же ярусов имеет вершина 7.
У вершины 2 графа 3 яруса. Один из них образован вершинами 1 и 5, другой – вершинами 3, 4 и 6, третий – вершиной 3. Вершины 3 и 6 также имеют по 3 яруса.
Число ярусов вершины 4 равно двум. Первый ярус состоит из вершин
3, 5 и 6, второй – из вершин 1, 2 и 7. Столько же ярусов у вершины 5.
Слайд 82
Пусть G[жэ] – неориентированный граф.
Говорят, что вершины u[у] и v[вэ] в графе G[жэ] связаны отношением достижимости, если существует соединяющая их цепь. Граф, в котором любые две вершины связаны отношением достижимости, называется связным. Тривиальный граф, состоящий из изолированной вершины, по определению считается связным. Граф, не являющийся связным, называется несвязным.
Отношение достижимости вершин является отношением эквивалентности.
Компонентой связности графа G[жэ] называется такой его связный подграф, который не является собственным подграфом никакого другого связного подграфа графа G[жэ].
Классы эквивалентности по отношению достижимости образуют разбиение множества вершин графа G[жэ] на подмножества вершин, входящих в одну компоненту связности. Для построения компоненты
связности достаточно взять один класс эквивалентности и перенести на его вершины ребра из графа G[жэ].
Одной из характеристик графа является число его компонент связности. Обозначение для данной величины приведено в формуле (3.39).
Граф G[жэ] является связным тогда и только тогда, когда он имеет одну компоненту связности. Граф, состоящий из двух или более изолированных вершин, называется вполне несвязным.
Граф G, изображенный на рис. 3.32, имеет две компоненты связности.
Формула (3.40) представляет множества V
1
[вэ один] и V
2
[вэ два] вершин, входящих соответственно в первую и вторую компоненты.
Слайд 83
Пусть теперь G – ориентированный граф.
Говорят, что вершины u[у] и v[вэ] в орграфе G[жэ] связаны отношением двусторонней достижимости, если существует как путь из u[у] в
v[вэ], так и путь из v[вэ] в u[у]. Орграф, в котором любые две вершины связаны отношением двусторонней достижимости, называется сильно связным. Тривиальный граф, состоящий из изолированной вершины, по определению считается сильно связным.
Отношение двусторонней достижимости вершин является отношением эквивалентности.
Компонентой сильной связности орграфа G[жэ] называется такой его сильно связный подграф, который не является собственным подграфом никакого другого сильно связного подграфа орграфа G.
Классы эквивалентности по отношению двусторонней достижимости образуют разбиение множества вершин орграфа G[жэ] на подмножества вершин, входящих в одну компоненту сильной связности. Для построения компоненты сильной связности достаточно взять один класс эквивалентности и перенести на его вершины дуги из орграфа G[жэ].
Одной из характеристик графа является число его компонент связности. Обозначение для данной величины приведено в формуле (3.39).
Граф G[жэ] является связным тогда и только тогда, когда он имеет одну компоненту связности. Граф, состоящий из двух или более изолированных вершин, называется вполне несвязным.
Граф G, изображенный на рис. 3.32, имеет две компоненты связности.
Формула (3.40) представляет множества V
1
[вэ один] и V
2
[вэ два] вершин, входящих соответственно в первую и вторую компоненты.
Слайд 83
Пусть теперь G – ориентированный граф.
Говорят, что вершины u[у] и v[вэ] в орграфе G[жэ] связаны отношением двусторонней достижимости, если существует как путь из u[у] в
v[вэ], так и путь из v[вэ] в u[у]. Орграф, в котором любые две вершины связаны отношением двусторонней достижимости, называется сильно связным. Тривиальный граф, состоящий из изолированной вершины, по определению считается сильно связным.
Отношение двусторонней достижимости вершин является отношением эквивалентности.
Компонентой сильной связности орграфа G[жэ] называется такой его сильно связный подграф, который не является собственным подграфом никакого другого сильно связного подграфа орграфа G.
Классы эквивалентности по отношению двусторонней достижимости образуют разбиение множества вершин орграфа G[жэ] на подмножества вершин, входящих в одну компоненту сильной связности. Для построения компоненты сильной связности достаточно взять один класс эквивалентности и перенести на его вершины дуги из орграфа G[жэ].
Одной из характеристик орграфа является число его компонент сильной связности. Обозначение для данной величины приведено в формуле
(3.41). Орграф G[жэ] является сильно связным тогда и только тогда, когда он имеет одну компоненту сильной связности.
Граф G[жэ], изображенный на рис. 3.33, не является сильно связным, так как имеет три компоненты сильной связности. Им соответствуют множества вершин, представляемые формулой (3.42). Сами компоненты сильной связности графа G изображены на рис. 3.34.
Слайд 84
Орграф G[жэ] называется односторонне связным, если для любых его вершин и u[у] и v[вэ] существует либо путь из u[у] в v[вэ], либо путь из v[вэ] в u[у].
Очевидно, что если орграф является сильно связным, то он будет и односторонне связным.
Граф, изображенный на рис. 3.35, не является односторонне связным, так как, скажем, из вершины 1 нет пути в вершину 5 и, наоборот, из вершины
5 нет пути в вершину 1.
На рис. 3.36, а представлен односторонне связный граф, не являющийся сильно связным.
Пусть G[жэ] – ориентированный граф, имеющий множество вершин
V[вэ] и множество ребер E[е].
Графом, ассоциированным с орграфом
G[жэ], называется неориентированный граф G
1
[жэ один], имеющий то же множество вершин
V[вэ] и множество ребер E
1
[е один] получающееся из множества E[е] заменой всех дуг на неориентированные ребра.
Орграф G[жэ] называется слабо связным, если ассоциированный с ним неориентированный граф является связным.
На рис. 3.36, б представлен слабо связный граф, не являющийся односторонне связным.
Слайд 85
Рассмотрим способ нахождения компонент связности с помощью ЭВМ.
Чтобы в n[эн]-вершинном графе или орграфе G[же] существовал маршрут из вершины v
i
[вэ итое] в вершину v
j
[вэ житое], необходимо и достаточно, чтобы итый-житый элемент матрицы 3.43 был отличен от нуля.
Составим из матрицы B[бэ], определенной в формуле (3.44), матрицу
C[цэ], используя правило (3.45).
Матрица C называется матрицей связности, если G[же] – неориентированный граф, и матрицей достижимости, если G[же] – орграф.
Граф G[же] будет содержать маршрут из вершины v
i
[вэ итое] в вершину v
j
[вэ житое] тогда и только тогда, когда элемент C
ij
[цэ итое житое] равен 1.
Значит, матрица C[цэ] содержит информацию о существовании связей между различными элементами графа с помощью маршрутов. Если все элементы матрицы связности равны единице, то граф является связным.
В случае неориентированного графа матрица C[цэ] совпадает с транспонированной и является матрицей связности.
В случае ориентированного графа транспонированная матрица C[цэ] называется матрицей контрдостижимости, так как если итый-житый элемент матрицы
C[цэ] показывает наличие пути из вершины v
i
[вэ итое] в вершину v
j
[вэ житое], то житый-итый элемент транспонированной матрицы показывает наличие обратного пути из вершины вэ житое в вершину вэ итое.
Матрицы достижимости и контрдостижимости можно использовать для нахождения сильных компонент орграфа.
Рассмотрим матрицу, определенную в формуле (3.46), где операция звездочка означает поэлементное произведение матриц. Элемент матрицы
S[эс] равен 1 тогда и только тогда, когда вершины v
i
[вэ итое] и v
j
[вэ житое] взаимно достижимы. Следовательно, компонента сильной связности, содержащая вершину v
i
[вэ итое], состоит из элементов v
j
[вэ житое], для которых элемент v
ij
[вэ итое-житое] равен единице.
Слайд 86
Тема 3.3. Деревья. Остов графа. Понятия планарного, эйлерова и гамильтонова графов
Деревья заслуживают отдельного и подробного рассмотрения по двум причинам.
Деревья являются в некотором смысле простейшим классом графов.
Для них выполняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять на деревьях.
Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях.
Неориентированный связный граф без циклов называется деревом, или свободным деревом. Граф, состоящий из нескольких деревьев, называется лесом. Таким образом, компонентами связности леса являются деревья.
Примеры деревьев представлены на рис. 3.37, 3.38.
Слайд 87
На рис. 3.39 изображены диаграммы всех различных деревьев с 5 вершинами, а на рис. 3.40 – диаграммы всевозможных деревьев с 6 вершинами.
Для всякого неориентированного графа G[жэ] следующие утверждения эквивалентны.
1. G[жэ]
– дерево, то есть связный граф без циклов.
2. Любые две вершины соединены в G[жэ] единственной простой цепью.
3. G[жэ]– связный граф, и удаление любого ребра делает граф несвязным.
4. G[жэ] – связный граф, в котором число ребер на единицу меньше числа вершин.