Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
ребро; • • • • A A A A A ¢ ¢ ¢ ¢ ¢ • • • ¢ ¢ ¢ ¢ ¢ • • • • • A A A A A ¡ ¡ ¡ ¡ ¡ • • • • ©© ©© © ¢ ¢ ¢ ¢ ¢ Рис. 4.32 144 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4) любые две несовпадающие вершины графа G соединяет единственная простая цепь; 5) G — ациклический граф, такой, что если какую-либо пару его несмеж- ных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. ¤ Пусть G = hM; Ri — неорграф. Часть G 0 = hM 0 ; R 0 i графа G называется остовом или каркасом графа G, если M = M 0 и G 0 — лес, который на любой связной компоненте графа G образует дерево. Таким образом, если G — связ- ный граф, то остов G 0 является деревом, которое будем называть остовным деревом графа G. Понятие остова для орграфа G определяется как часть G 0 графа G, для которой F (G 0 ) является остовом графа F (G). Аналогично вводится понятие остовного дерева для связного орграфа G. Очевидно, что в каждом графе существует остов: разрушая в каждой связной компоненте циклы, т. е. удаляя лишние ребра, получаем остов. Пример 4.8.1. В качестве остова графа G, изображенного на рис. 4.33, можно взять лес с ребрами 2, 3, 4, 6, 7 (вообще говоря, остов определяется неоднозначно). ¤ Из теоремы 4.8.1. вытекает Следствие 4.8.2. Число ребер произвольного неорграфа G, которые необходимо удалить для получения остова, не зависит от последователь- ности их удаления и равно m−n+c, где m — число ребер, n — число вершин, c — число компонент связности графа G. Доказательство. Действительно, если i-я компонента связности C i графа G содержит n i вершин, то по теореме 4.8.1 соответствующее дерево K i остова содержит n i −1 ребро. Следовательно, для получения K i из компонен- ты C i нужно удалить m i −(n i −1) ребер, где m i — число ребер в C i . Суммируя удаляемые ребра по всем компонентам связности и замечая, что c P i=1 m i = m, c P i=1 n i = n, получаем, что необходимо удалить c P i=1 (m i − n i + 1) = m − n + c ребер. ¤ Число ν(G) m − n + c называется цикломатическим числом или цик- лическим рангом графа G. Число ν ∗ (G) n − c называется коциклическим рангом или корангом. Таким образом, ν ∗ (G) есть число ребер, входящих в любой остов графа G, и ν(G) + ν ∗ (G) = m. 4.8. ОСТОВЫ ГРАФОВ 145 • • • • • • • 5 2 3 1 4 6 7 8 • • • • • • ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ 2 3 1 4 3 3 3 5 1 2 Рис. 4.33 Рис. 4.34 Из следствия 4.8.2. вытекают следующие два утверждения. Следствие 4.8.3. Неорграф G является лесом тогда и только тогда, когда ν(G) = 0. ¤ Следствие 4.8.4. Неорграф G имеет единственный цикл тогда и толь- ко тогда, когда ν(G) = 1. ¤ Опишем алгоритм нахождения остова минимального веса во взвешен- ном графе. Эта задача возникает при проектировании линий электропере- дач, дорог и т. п., когда требуется заданные центры (вершины) соединить некоторой системой каналов связи (ребер) так, чтобы любые два центра бы- ли связаны либо непосредственно соединяющим их каналом (ребром), либо через другие центры и каналы, т. е. цепью, у которой общая длина (или, на- пример, стоимость) каналов связи была минимальной. Искомая сеть будет остовом минимального веса полного графа. Алгоритм, решающий задачу нахождения остова минимального веса во взвешенном графе G = hM; Ri, заключается в следующем. 1. Строим граф T 1 , состоящий из множества вершин M и един- ственного ребра u 1 , которое имеет минимальный вес. 2. Если граф T i уже построен и i < n − c, где n = |M|, c = c(G), то стро- им граф T i+1 , добавляя к множеству ребер графа T i ребро u i+1 , имеющее минимальный вес среди ребер, не входящих в T i и не составляющих циклов с ребрами из T i Приведенный алгоритм, в частности, позволяет находить остов в невзве- шенном графе, положив w(u i ) = 1 для всех ребер u i ∈ R. Пример 4.8.2. На рис. 4.34 показан остов минимального веса взвешен- ного графа. Вес остова равен 9. ¤ 146 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 4.9. Обходы графа по глубине и ширине. Решение задачи коммивояжера При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершин, удовлетворяющих определен- ным свойствам. Пусть G = hM; Ri — связный неориентированный граф, T — некоторый остов графа G, a — некоторая фиксированная вершина, называемая корнем дерева T . Разместим вершины из M по этажам • • • • • • • • • • • • • • • • • • • ¡ ¡ ¡ @ @ @ @ @ @ ¡ ¡ @ @ HH H ¡ ¡ @ @ a 1 2 3 4 5 Рис. 4.35 таким образом, чтобы корень a находился на верхнем этаже, смежные с ним верши- ны занимали этаж на единицу ниже, смежные с отмеченными вершинами — еще на единицу ниже и т. д. (рис. 4.35). Таким образом, полу- чаем e(a) + 1 этажей, где e(a) — эксцентриситет вершины a. Опишем обход графа по глубине. При таком обходе после очередной рас- смотренной вершины выбирается смежная с ней вершина следующего этажа. Если очередная рассмотренная вершина висячая и ее достижение не дает желаемого решения задачи, то возвращаемся до ближайшей вершины сте- пени > 3 и просматриваем вершины другого, еще не пройденного маршрута в таком же порядке и т. д. На рис. 4.36 показана очередность обхода вершин по глубине графа, изоб- раженного на рис. 4.35. При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа производится только после просмот- ра всех вершин данного этажа. На рис. 4.37 показан порядок обхода по ши- рине графа, изображенного на рис. 4.35. Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и по- иск по ширине — эквивалентны. Если же достаточно найти одну вершину с определенным свойством, то целесообразность применения поиска решения по глубине или по ширине определяется структурой дерева. Если дерево является достаточно широким, а висячие вершины расположены на срав- нительно близких этажах, то целесообразно вести поиск по глубине. Для глубоких узких деревьев, когда висячие вершины могут встретиться на раз- личных этажах и их разброс по этажам достаточно велик, предпочтение отдается поиску по ширине. 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 147 • • • • • • • • • • • • • • • • • • • ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ @ @ HH HH ¡ ¡ @ @ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 • • • • • • • • • • • • • • • • • • • ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ @ @ HH HH ¡ ¡ @ @ 1 2 5 11 16 17 6 3 7 12 13 4 8 9 14 15 18 19 10 Рис. 4.36 Рис. 4.37 Отметим, что при компьютерной реализации обходов по глубине и ши- рине целесообразно использовать задание дерева структурой смежности вер- шин. Часто при решении задач их разбивают на несколько более простых задач, которые, в свою очередь, разбиваются на более простые подзадачи и так до тех пор, пока не появляются подзадачи, под- дающиеся непосредственному решению. Такое разбиение задач можно представить в виде дерева следующим образом. Если задача A разбивается на подзадачи A(1, 1), A(1, 2), . . . , A(1, n 1 ), подзадача A(1, i) — на подза- дачи A(2, i, 1), . . . , A(2, i, n 2,i ) и т. д., то получается дерево, изображенное на рис. 4.38. Для решения задач используются обходы таких деревьев с поиском по глубине или ширине. Опишем данный подход на примере решения задачи коммивояжера методом ветвей и границ. Пусть W = (w ij ) — матрица весов графа G = hM; Ri, не имеющего пе- тель, где M = {1, 2, . . . , n}. Для простоты будем считать, что все веса w ij неотрицательны. Найдем нижнюю оценку весов гамильтоновых циклов. Для этого в матрице весов найдем минимальные числа каждой строки: w 1k 1 , w 2k 2 , . . ., w nk n . Очевидно, что вес произвольного гамильтонова цикла не мень- ше w 1k 1 + w 2k 2 + . . . + w nk n . Преобразуем матрицу весов, вычитая из каж- дой строки соответствующее число w ik i . Получаем матрицу W ∨ = (w ∨ ij ), где w ∨ ij = w ij − w ik i . В ней найдем минимальные числа каждого столбца: w ∨ l 1 1 , w ∨ l 2 2 , . . ., w ∨ l n n , и преобразуем ее, вычитая из каждого столбца соответ- ствующее число w ∨ l j j : W ∗ = (w ∗ ij ), где w ∗ ij = w ∨ ij − w ∨ l j j . Для любого гамиль- тонова цикла X справедлива оценка веса w(X) цикла X: w(X) > h, где h = w 1k 1 + w 2k 2 + . . . + w nk n + w ∨ l 1 1 + w ∨ l 2 2 + . . . + w ∨ l n n 148 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • A A(1, 1) A(1, 2) A(1, n 1 ) · · · A(2, 1, 1) · · · A(2, 1, n 21 ) A(2, n 1 , 1) · · · A(2, n 1 , n 2n 1 ) ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ ´ ´ ´ ´ ´ Q Q Q Q Q ¤ ¤ ¤ ¤¤ C C C CC · · · ¤ ¤ ¤ ¤¤ C C C CC · · · ¤ ¤ ¤ ¤¤ C C C CC · · · ¤ ¤ ¤ ¤¤ C C C CC · · · ¤ ¤ ¤ ¤¤ C C C CC · · · Рис. 4.38 Обозначим через (a 1 , a 2 , . . . , a k ){b 1 , b 2 , . . . , b t } множество гамильтоновых циклов, в которых первые k вершин a 1 , a 2 , . . ., a k , а (k + 1)-я вершина a k+1 не принадлежит множеству {b 1 , b 2 , . . . , b t }. Используя введенные обозначе- ния, можем разбить нашу задачу на две подзадачи, поделив множество га- мильтоновых циклов на множества (1, k 1 )∅ и (1){k 1 } (рис. 4.39). При рассмотрении множества (1, k 1 )∅ отождествим в графе G вершины 1 и k 1 (обозначим новую вершину через x) и получим граф G 0 с множеством вершин {x, 2, . . . , k 1 − 1, k 1 + 1, . . . , n} и матрицей весов W 0 = ∞ w ∗ k 1 2 w ∗ k 1 3 · · · w ∗ k 1 ,k 1 −1 w ∗ k 1 ,k 1 +1 · · · w ∗ k 1 n w ∗ 21 ∞ w ∗ 23 · · · w ∗ 2,k 1 −1 w ∗ 2,k 1 +1 · · · w ∗ 2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w ∗ k 1 −1,1 w ∗ k 1 −1,2 w ∗ k 1 −1,3 · · · ∞ w ∗ k 1 −1,k 1 +1 · · · w ∗ k 1 −1,n w ∗ k 1 +1,1 w ∗ k 1 +1,2 w ∗ k 1 +1,3 · · · w ∗ k 1 +1,k 1 −1 ∞ · · · w ∗ k 1 +1,n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w ∗ n1 w ∗ n2 w ∗ n3 · · · w ∗ n,k 1 −1 w ∗ n,k 1 +1 · · · ∞ . Для графа G 0 найдем нижнюю оценку h 0 весов гамильтоновых циклов аналогично тому, как найдены оценки h. Тогда нижняя оценка h 1 весов га- мильтоновых циклов множества (1, k 1 )∅ равна h + h 0 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 149 H µ´ ¶³ (1, k 1 )∅ h 1 ±° ²¯ (1){k 1 } h 2 ±° ²¯ (1, k 1 , k k 1 )∅ h 11 ±° ²¯ (1, k 1 ){k k 1 } h 12 ±° ²¯ (1, m 1 )∅ h 21 ±° ²¯ (1){k 1 , m 1 } h 22 ±° ²¯ (1, k 1 , k k 1 , k k k1 )∅ h 111 µ´ ¶³ ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ @ @ @ · · · · · · · · · ¤ ¤ ¤ C C C C C C ¤ ¤ ¤ @ @ @ ¢ ¢ ¢ · · · · · · · · · · · · Рис. 4.39 При рассмотрении множества (1){k 1 } в матрице весов W ∗ элемент w ∗ 1k 1 заменяется на ∞ и по полученной матрице W находится нижняя оценка h 00 весов гамильтоновых циклов графа с матрицей весов W 00 . Тогда нижняя оценка h 2 весов гамильтоновых циклов множества (1){k 1 } равна h + h 00 Каждая из подзадач разбивается на свои подзадачи, и этот процесс с оце- ниванием весов гамильтоновых циклов продолжается до тех пор, пока не оты- щется самая низкая из оценок, являющаяся весом некоторого гамильтонова цикла, который и будет иметь минимальный вес. При рассмотрении подзадач целесообразно вести поиск в глубину, при котором на каждом следующем этаже выбирается та подзадача, которая имеет меньшую нижнюю оценку. Пример 4.9.1. Рассмотрим граф с матрицей весов W = 1 2 3 4 5 6 ∞ 13 7 5 2 9 8 ∞ 4 7 5 ∞ 8 4 ∞ 3 6 2 5 8 1 ∞ 0 1 ∞ 6 1 4 ∞ 9 10 0 8 3 7 ∞ . Найдем минимальные числа строк: à 2 4 2 0 1 0 ! , где 2 = w 15 , 4 = w 23 , 2 = w 36 , 0 = w 45 , 1 = w 53 , 0 = w 62 |