Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
r−2 = b 2 = 3, b r−3 = b 1 = 2. Таким образом, кратчайший (1, 4)-маршрут задается последовательностью вершин (1, 2, 3, 5, 4). ¤ Следующий алгоритм, алгоритм Дейкстры, более эффективен, чем ал- горитм Форда—Беллмана, но используется только для взвешенных графов, в которых веса всех дуг неотрицательны. Итак, пусть G = hM; Ri — взвешенный граф, W = (w ij ) — матрица весов графа G, где w ij > 0; a i — выделенный источник. Зададим стро- ку D (1) = (d (1) 1 , d (1) 2 , . . . , d (1) n ), полагая, как и в алгоритме Форда—Беллмана, d (1) i = 0, d (1) j = w ij , i 6= j. Обозначим через T 1 множество вершин M \ {a i }. Предположим, что на шаге s уже определены строка D (s) = (d (s) 1 , . . . , d (s) n ) и множество вершин T s . Выберем теперь вершину a j ∈ T s так, что d (s) j = = min{d (s) k | a k ∈ T s }. Положим T s+1 T s \ {a j }, D (s+1) (d (s+1) 1 , . . . , d (s+1) n ), где d (s+1) k = min{d (s) k , d (s) j + w jk }, если a k ∈ T s+1 , и d (s+1) k = d (s) k , если a k / ∈ T s+1 На шаге s = n − 1 образуется строка D (n−1) w-расстояний между верши- ной a i и остальными вершинами графа: d (n−1) j = ρ w (a i , a j ). Отметим, что для реализации алгоритма Форда—Беллмана требуется по- рядка n 3 операций, тогда как в алгоритме Дейкстры необходимо выполнить порядка n 2 операций. 138 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пример 4.5.3. Рассмотрим взвешенный граф G с матрицей весов W = 0 1 ∞ ∞ ∞ ∞ ∞ 0 5 2 ∞ 7 ∞ ∞ 0 ∞ ∞ 1 2 ∞ 1 0 4 ∞ ∞ ∞ ∞ 3 0 ∞ ∞ ∞ ∞ ∞ 1 0 и источником 1 (рис. 4.26). Тогда по алгоритму Дейкстры T 1 = {2, 3, 4, 5, 6}, D (1) = (0, 1, ∞, ∞, ∞, ∞), T 2 = {3, 4, 5, 6}, D (2) = (0, 1, 6, 3, ∞, ∞), T 3 = {3, 5, 6}, D (3) = (0, 1, 4, 3, 7, 7), T 4 = {5, 6}, D (4) = (0, 1, 4, 3, 7, 5), T 5 = {5}, D (5) = (0, 1, 4, 3, 6, 5) (в D (s) подчеркнута величина d (s) j , для которой T s+1 = T s \{a j }). Таким образом, ρ w (1, 1) = 0, ρ w (1, 2) = 1, ρ w (1, 3) = = 4, ρ w (1, 4) = 3, ρ w (1, 5) = 6, ρ w (1, 6) = 5. ¤ Опишем теперь алгоритм нахождения крат- • • • • • • 6 6 ? - - @ @ @ @ @ @ R ¾ R j Y 1 4 5 2 6 3 (1) (1) (1) (2) (5) (1) (7) (4) (3) (2) Рис. 4.26 чайших маршрутов в бесконтурном графе. Так же, как и в алгоритме Дейкстры, для выпол- нения этого алгоритма необходимо порядка n 2 операций. Прежде всего заметим, что в конечном бес- контурном графе G = hM; Ri вершины можно перенумеровать так, что каждая дуга будет иметь вид (a i , a j ), где i < j. Действительно, в конечном бесконтурном графе всегда суще- ствует вершина a, в которую не заходит ни одна дуга. Обозначим эту верши- ну через a 1 и рассмотрим граф G 1 , полученный из G удалением вершины a 1 Граф G 1 также является бесконтурным и, следовательно, содержит верши- ну a 0 , в которую не заходит ни одна дуга графа G 1 . Вершину a 0 обозначим через a 2 , а граф, полученный из G 1 удалением вершины a 2 , — через G 2 Продолжая процесс, получим в результате искомую нумерацию a 1 , a 2 , . . ., a n вершин графа G. Пример 4.5.4. На рис. 4.27 приведен пример нумерации вершин бес- контурного взвешенного графа, при которой из (a i , a j ) ∈ R следует i < j (в скобках указаны веса взвешенных дуг). ¤ 4.6. СТЕПЕНИ ВЕРШИН 139 Предположим, что в бесконтурном графе G = h{a 1 , a 2 , . . . , a n }; Ri для произвольной дуги (a i , a j ) выполняется условие i < j. Заметим, что при такой нумерации все элементы матрицы весов, стоящие под главной диа- гональю, равны ∞. Найдем расстояние от a 1 до всех вершин графа. Рассмотрим строку D (1) = (d (1) 1 , d (1) 2 , . . . , d (1) n ), где d (1) 1 = 0; d (1) j = w 1j ; j > 2. Если на шаге s строка D (s) = (d (s) 1 , d (s) 2 , . . . , d (s) n ) определена, положим D (s+1) (d (s+1) 1 , d (s+1) 2 , . . . , d (s+1) n ), где d (s+1) j min{d (s) j , d (s) k + w kj }, для k < j и (a k , a j ) ∈ R, j = 1, . . . , n. Данный алгоритм является аналогом ал- горитма Форда—Беллмана, учитывающим бесконтурность графа G, и при s = n − 1 получаем d (n−1) j = ρ w (a 1 , a j ). Пример 4.5.5. Для графа G, изображенного • • • • • • • • ¡ ¡ ¡ ¡ µ - @ @ @ @ R - - - ¡ ¡ ¡ ¡ µ ¡ ¡ ¡ ¡ µ 6 - 1 2 3 4 5 6 7 8 (−2) (2) (−5) (6) (3) (1) (1) (7) (10) (1) Рис. 4.27 на рис. 4.27, имеем W = 0 1 ∞ 2 ∞ ∞ 1 ∞ ∞ 0 −2 ∞ 7 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 10 ∞ ∞ ∞ ∞ ∞ 0 −5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 6 ∞ 1 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 , D (1) = (0, 1, ∞, 2, ∞, ∞, 1, ∞), D (2) = (0, 1, −1, 2, −3, ∞, 1, 4), D (3) = (0, 1, −1, 2, −3, 3, 1, −2) = D (4) = D (5) = D (6) = D (7) . ¤ Отметим, что если в приведенных алгоритмах ∞ заменить на −∞, min — на max, то получим алгоритмы, которые позволяют в графах, не имеющих контуров положительных весов, находить маршруты наибольшей длины. § 4.6. Степени вершин Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a, т. е. число ребер, концом которых является вершина a (при этом петли считаются дважды). Если G — орграф, то степени его вершин определяются как степени вершин в соответствующем неоргра- фе F (G). Аналогично вводится понятие степени вершины в мультиграфах. Степень вершины a будем обозначать через deg G a или просто deg a. Вер- шина степени 0 называется изолированной, вершина степени 1 — концевой или висячей. 140 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пример 4.6.1. Вершины графа G, изображенного на рис. 4.28, имеют следующие валентности: deg 1 = deg 2 = deg 3 = 1 (т. е. 1, 2, 3 — висячие вершины), deg 4 = 5, deg 5 = 0 (т. е. 5 — изолированная вершина). ¤ Рассмотрим сумму степеней всех вершин графа. По- • • • • • ¡ ¡ ¡ ¡ µ@ @ @ @ R g 2 3 5 1 4 Рис. 4.28 скольку каждое ребро входит в эту сумму дважды, спра- ведливо Утверждение 4.6.1 (лемма о рукопожатиях). Сум- ма степеней всех вершин графа является четным числом и равна удвоенному числу ребер. Пусть G — бесконтурный орграф. Полустепенью ис- хода deg + a вершины a называется число дуг, исходящих из a. Полустепенью захода deg − a вершины a называется число дуг, которые заходят в верши- ну a. Справедливо соотношение deg a = deg + a + deg − a. В примере 4.5.4 имеем deg 2 = 3, deg + 2 = 2, deg − 2 = 1. § 4.7. Обходы графов Опишем одну из задач, положивших начало теории графов, — задачу о кенигсбергских мостах . На рис. 4.29 схематично изображена карта г. Кенигсберга в XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мо- стами. Возник вопрос: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз? Неориентированный мультиграф G, представляющий задачу, показан на рис. 4.30. Вершины x 1 , x 4 соответствуют берегам реки, x 2 , x 3 — остро- вам, ребра мультиграфа — мостам. Следовательно, на языке теории графов • • • • ¡ ¡ ¡ @ @ @ x 1 x 2 x 4 x 3 Рис. 4.29 Рис. 4.30 4.7. ОБХОДЫ ГРАФОВ 141 задача формулируется следующим образом: существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа? Выдающимся математиком и механиком Л. Эйлером сформулирован и до- казан критерий того, что связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, называется эйлеровым, и мультиграф, в котором име- ется эйлеров цикл, также называется эйлеровым. Теорема 4.7.1. Связный неориентированный мультиграф является эйлеровым тогда и только тогда, когда степень каждой из его вершин — четное число. ¤ Мультиграф, изображенный на рис. 4.30, не содержит эйлеров цикл, поскольку в нем есть вершины, имеющие нечетную степень. Более того, все его вершины имеют нечетную степень. Опишем алгоритм построения эйлерова цикла в эйлеровом мультиграфе. Этот алгоритм задается следующими правилами. 1. Выбрать произвольно некоторую вершину a. 2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным). 3. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на еди- ницу больший номера предыдущего вычеркнутого ребра. 4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если имеется возможность иного выбора. 5. Находясь в вершине x, не выбирать ребро, ко- • • • • • • •a 1 2 3 4 5 6 7 8 Рис. 4.31 торое является перешейком (т. е. ребром, при удале- нии которого граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру). 6. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер. Пример 4.7.1. Найдем эйлеров цикл в эйлеровом графе, изображенном на рис. 4.31. После выбора вершины a и прохождения ребер 1 и 2 имеют- ся три возможности выбора: ребра 3, 6 или 7. Так как ребро 7 является перешейком, выбираем следующее ребро из оставшихся, например 3. Далее обходим оставшиеся ребра и получаем эйлеров цикл 1, 2, 3, 4, 5, 6, 7, 8. ¤ 142 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Будем говорить, что набор реберно непересекающихся цепей покрывает граф G, если каждое ребро графа G входит в одну из этих цепей. Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопо- жатиях число k четно. Рассмотрим граф G 0 , полученный добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами графа G нечетной степени. Поскольку степени всех вершин графа G 0 четны, G 0 со- держит эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, содержащих все ребра графа G, т. е. покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересекающихся цепей, имеет не более 2r вершин нечетной сте- пени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2. Тем самым доказана Теорема 4.7.2. Если связный граф содержит k вершин нечетной сте- пени, то минимальное число покрывающих его реберно непересекающихся цепей равно k/2. ¤ В частности, при k = 2 граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащая все ребра графа, называется эйлеровой. Мы рассмотрели обходы ребер графа. Следующей нашей целью является изучение обходов вершин графа. Граф называется гамильтоновым, если в нем имеется простой цикл, со- держащий каждую вершину этого графа. Сам такой цикл также называется гамильтоновым. Гамильтоновой называется и простая цепь, содержащая все вершины графа. Очевидно, что любой граф, ребра которого образуют простой цикл, является гамильтоновым, а граф, показанный на рис. 4.31, — негамильтоновым. Несмотря на схожесть задач о нахождении эйлеровых и гамильтоновых циклов, решение последней значительно сложнее. Известны следующие до- статочные условия существования гамильтоновых циклов в связном неор- графе G без петель, имеющем n > 3 вершин: Теорема 4.7.3. Если для любых двух различных несмежных вершин a и b графа G выполняется условие deg a + deg b > n, то существует гамиль- тонов цикл. ¤ Следствие 4.7.4. Если для любой вершины a графа G выполнено усло- вие deg a > n/2, то существует гамильтонов цикл. ¤ 4.8. ОСТОВЫ ГРАФОВ 143 С задачей нахождения гамильтонова цикла связана следующая задача коммивояжера. Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми из- вестны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город. Если таких маршрутов много, требуется найти кратчайший из них. Математическая постановка задачи выглядит так: найти гамильтонов цикл минимального веса. Решение этой проблемы мы рассмотрим в § 4.9, а здесь отметим некоторые практические задачи, сводящиеся к задаче ком- мивояжера. 1. Пусть граф задает сеть коммуникаций между фиксированными цен- трами. Необходимо построить маршрут, обеспечивающий посещение всех центров ровно по одному разу. 2. Имеется станок с числовым программным управлением, который вы- сверливает отверстия в печатных платах по заданной программе. Составляя граф, в котором вершины соответствуют требуемым отверстиям, получаем задачу нахождения обхода вершин, такого, что суммарное время, затрачен- ное на него, было бы минимальным. § 4.8. Остовы графов Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являются деревья. На рис. 4.32 изображен лес, состоящий из двух деревьев. Теорема 4.8.1. Для неорграфа G без петель, содержащего n вершин, следующие условия эквивалентны: 1) G — дерево; 2) G — связный граф, содержащий n − 1 ребро; 3) G — ациклический граф, содержащий n − 1 |