Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
задача формулируется следующим образом: существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа? Выдающимся математиком и механиком Л. Эйлером сформулирован и до- казан критерий того, что связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, называется эйлеровым, и мультиграф, в котором име- ется эйлеров цикл, также называется эйлеровым. Теорема 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. ¤ 4.7. ОБХОДЫ ГРАФОВ 139 Будем говорить, что набор реберно непересекающихся цепей покрывает граф 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, то существует гамильтонов цикл. ¤ 140 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ С задачей нахождения гамильтонова цикла связана следующая задача коммивояжера. Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми из- вестны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город. Если таких маршрутов много, требуется найти кратчайший из них. Математическая постановка задачи выглядит так: найти гамильтонов цикл минимального веса. Решение этой проблемы мы рассмотрим в § 4.9, а здесь отметим некоторые практические задачи, сводящиеся к задаче ком- мивояжера. 1. Пусть граф задает сеть коммуникаций между фиксированными цен- трами. Необходимо построить маршрут, обеспечивающий посещение всех центров ровно по одному разу. 2. Имеется станок с числовым программным управлением, который вы- сверливает отверстия в печатных платах по заданной программе. Составляя граф, в котором вершины соответствуют требуемым отверстиям, получаем задачу нахождения обхода вершин, такого, что суммарное время, затрачен- ное на него, было бы минимальным. § 4.8. Остовы графов Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являются деревья. На рис. 4.32 изображен лес, состоящий из двух деревьев. Теорема 4.8.1. Для неорграфа G без петель, содержащего n вершин, следующие условия эквивалентны: 1) G — дерево; 2) G — связный граф, содержащий n − 1 ребро; 3) G — ациклический граф, содержащий n − 1 ребро; • • • • A A A A A ¢ ¢ ¢ ¢ ¢ • • • ¢ ¢ ¢ ¢ ¢ • • • • • A A A A A ¡ ¡ ¡ ¡ ¡ • • • • ©© ©© © ¢ ¢ ¢ ¢ ¢ Рис. 4.32 4.8. ОСТОВЫ ГРАФОВ 141 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. 142 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • • • • 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. ¤ 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 143 § 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. Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и по- иск по ширине — эквивалентны. Если же достаточно найти одну вершину с определенным свойством, то целесообразность применения поиска решения по глубине или по ширине определяется структурой дерева. Если дерево является достаточно широким, а висячие вершины расположены на срав- нительно близких этажах, то целесообразно вести поиск по глубине. Для глубоких узких деревьев, когда висячие вершины могут встретиться на раз- личных этажах и их разброс по этажам достаточно велик, предпочтение отдается поиску по ширине. 144 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • • • • • • • • • • • • • • • • ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ @ @ 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 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 145 • 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 146 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 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 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 147 Вычитая соответствующие числа w ik i из каждой строки, получим матрицу W ∨ = ∞ 11 5 3 0 7 4 ∞ 0 3 1 ∞ 6 2 ∞ 1 4 0 5 8 1 ∞ 0 1 ∞ 5 0 3 ∞ 8 10 0 ∞ 3 7 ∞ . После нахождения наименьших значений по столбцам (4, 0, 0, 1, 0, 0) и вы- читания из каждого столбца матрицы W ∨ соответствующего числа w l i j об- разуется матрица W ∗ = ∞ 11 5 2 0 7 0 ∞ 0 2 1 ∞ 2 2 ∞ 0 4 0 1 8 1 ∞ 0 1 ∞ 5 0 2 ∞ 8 6 0 ∞ 2 7 ∞ . Суммируя элементы w ik i и w i j j , получаем нижнюю оценку h = 14. Так как w 15 = min{w 1i | i = 1, . . . , n}, то множество гамильтоновых циклов разобьем на два множества (1, 5)∅ и (1){5} (рис. 4.40). При рассмотрении множества (1, 5)∅ получаем матрицу весов W 0 = x 2 3 4 6 x 2 3 4 6 ∞ 5 0 2 8 0 ∞ 0 2 ∞ 2 2 ∞ 0 0 1 8 1 ∞ 1 6 0 8 2 ∞ графа G 0 , образованного отождествлением вершин 1 и 5 графа G. Мини- мальные элементы строк матрицы W 0 образуют столбец 0 0 0 1 0 , поэтому (W 0 ) ∨ = ∞ 5 0 2 ∞ 0 ∞ 0 2 ∞ 2 2 ∞ 0 0 0 7 0 ∞ 0 6 0 8 2 ∞ , 148 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ H (1, 5)∅ (1, 5, 3)∅ (1, 5, 3, 4)∅ (1, 5, 3, 4, 6)∅ (1){5} (1, 5){3} (1, 5, 3){4} (1, 5, 3, 4){6} ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ HH HH HH ¡ ¡ ¡ PPP PPP PPPP ¡ ¡ ¡ XXXX XXXX XXXX X 14 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 16 ±° ²¯ 17 ±° ²¯ 17 ±° ²¯ ∞ ±° ²¯ Рис. 4.40 а минимальные элементы столбцов матрицы (W 0 ) ∨ образуют нулевую стро- ку, и значит, (W 0 ) ∗ = (W 0 ) ∨ . Таким образом, оценка h 1 будет равна h + h 0 = = 14 + 1 = 15. Рассматривая множество (1){5}, мы должны в матрице W ∗ заменить эле- мент w ∗ 15 = 0 на ∞. Тогда оценка h 2 будет h + h 0 = 14 + 2 = 16. Поскольку h 1 < h 2 , выбираем множество (1, 5)∅ и соответствующую мат- рицу весов (W 0 ) ∗ . Теперь в силу того, что (w ∗ ) x3 = 0, разобьем множе- ство гамильтоновых циклов из множества (1, 5)∅ на множества (1, 5, 3)∅ и (1, 5){3} (рис. 4.40). Рассматривая случай (1, 5, 3)∅, получаем матрицу ве- сов W 00 = x 2 4 6 x 2 4 6 ∞ 2 0 0 0 ∞ 2 ∞ 0 7 ∞ 0 6 0 2 ∞ графа G 00 , образованного отождествлением вершин x и 3 графа G 0 . Оценка h 11 равна 15, а (W 00 ) ∗ = W 00 . При рассмотрении множества (1, 5){3} в матрице (W 0 ) ∗ заменяем элемент (w 0 ) ∗ 23 = 0 на ∞ и получаем оценку h 12 = h 1 +2 = 17. 4.10. УПОРЯДОЧЕННЫЕ И БИНАРНЫЕ ДЕРЕВЬЯ 149 Так как h 11 < h 12 , выберем множество (1, 5, 3)∅ с матрицей ве- сов (W 00 ) ∗ = W 00 . Поскольку (W 00 ) ∗ x4 = 0, рассмотрим множества циклов (1, 5, 3, 4)∅ и (1, 5, 3){4}. Для оценивания весов в множестве (1, 5, 3, 4)∅ отож- дествим вершины x и 4 в графе G 00 и получим граф G 000 с матрицей весов W 000 = x 2 6 x 2 6 ∞ 7 0 0 ∞ ∞ 6 0 ∞ . Очевидно, что h 111 = h 11 = 15, а (W 000 ) ∗ = W 000 . Рассматривая случай (1, 5, 3){4}, заменяем в матрице (W 00 ) ∗ элемент (w 00 ) ∗ x4 = 0 на ∞ и получаем оценку h 112 = h 11 + 2 = 17. Так как h 111 < h 112 , то переходим к рассмотрению множества (1, 5, 3, 4)∅, состоящего из двух гамильтоновых циклов (1, 5, 3, 4, 2, 6, 1) и (1, 5, 3, 4, 6, 2, 1). Первый из этих циклов будет иметь вес ∞, поскольку (W 000 ) 26 = ∞, а вес второго цикла 15, что соответствует оценке h 111 = 15. Поскольку оценки h 2 , h 12 и h 112 больше h 111 , соответствующие множества не содержат гамиль- тонова цикла веса, меньшего 15, и поэтому цикл (1, 5, 3, 4, 6, 2, 1) является гамильтоновым циклом минимального веса. § 4.10. Упорядоченные и бинарные деревья Определим по индукции понятие упорядоченного дерева: 1) пустое множество и список (a), где a — некоторый элемент, является упорядоченным деревом; 2) если T 1 , T 2 , . . . , T n — непустые упорядоченные деревья, a — некоторый новый элемент, то список T = (a, T 1 , T 2 , . . . , T n ) есть упорядоченное дерево. При этом элемент a называется корнем упорядоченного дерева T ; 3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2. Если T 1 , T 2 , . . . , T n — упорядоченные деревья, то список (T 1 , T 2 , . . . , T n ) называется упорядоченным лесом. Для заданного упорядоченного дерева T определим множество S(T ) его упорядоченных поддеревьев: • если T = ∅, то S(T ) = ∅; • если T = (a), то S(T ) = {(a)}; • если T = (a, T 1 , T 2 , . . . , T n ), то S(T ) = S(T 1 ) ∪ . . . ∪ S(T n ) ∪ {T }. 150 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ ' & $ % 1 ' & $ % 2 ' & $ % 3 µ´ ¶³ 4 µ´ ¶³ 5 ¶ µ ³ ´ 6 µ´ ¶³ 7 ±° ²¯ 8 ±° ²¯ 9 1 2 4 5 3 6 8 9 7 Рис. 4.41 Рис. 4.42 Непустое упорядоченное дерево T может интерпретироваться в виде си- стемы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T ) так, что: 1) если T 0 — поддерево упорядоченного дерева T 00 , T 0 , T 00 ∈ S(T ), то для соответствующих множеств X 0 и X 00 выполняется включение X 0 ⊆ X 00 ; 2) если T 0 не является поддеревом упорядоченного дерева T 00 и T 00 не яв- ляется поддеревом упорядоченного дерева T 0 (где T 0 , T 00 ∈ S(T )), то соответ- ствующие множества не пересекаются. Пример 4.10.1. Упорядоченному дереву (1, (2, (4), (5)), (3, (6, (8), (9)), (7))) соответствует система множеств, изображенная на рис. 4.41. ¤ Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях. На рис. 4.42 представлен уступчатый список, соответствующий упорядочен- ному списку из примера 4.10.1. Согласно следующему тезису любая схема, в которой заданы определен- ные приоритеты между элементами, может рассматриваться как некоторое упорядоченное дерево. Тезис. Любая иерархическая классификационная схема интерпретиру- ется некоторым упорядоченным деревом. 4.10. УПОРЯДОЧЕННЫЕ И БИНАРНЫЕ ДЕРЕВЬЯ 151 Например, в виде упорядоченного дерева представляется любой терм. На рис. 4.43 изображено упорядоченное дерево, соответствующее терму t = a − b · (c : d + e : f ). Частным случаем упорядоченного дерева является бинарное дерево. дерево. Определение бинарного дерева повторяет k − k a k × k b k + k : k : k c k d k e k f ¡ ¡ @ @ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ ¡ ¡ © © © © Рис. 4.43 определение для упорядоченного дерева с ограни- чением n ∈ {0, 1, 2} в п. 2. При этом для бинарного дерева T = ((a), T 1 , T 2 ), бинарное под- дерево T 1 называется левым поддеревом, а T 2 — правым поддеревом. Бинарные деревья имеют более простое устрой- ство, чем упорядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответ- ствует некоторому бинарному дереву. Опишем алгоритм преобразования упорядоченного леса T = (T 1 , T 2 , . . . , T n ) в бинарное дерево B(T ). 1. Если n = 0, B(T ) ∅. 2. Если n > 0, то корнем бинарного дерева B(T ) является корень a 1 упорядоченного дерева T 1 , левое поддерево дерева B(T ) — бинарное дерево B(T 11 , T 12 , . . ., T 1m ), где T 1 = (a 1 , T 11 , T 12 , . . . , T 1m ), правое поддерево дере- ва B(T ) — бинарное дерево B(T 2 , . . . , T n ). На рис 4.44б представлено бинарное дерево, соответствующее упорядо- ченному лесу (T 1 , T 2 ), изображенному на рис 4.44а. A µ´ ¶³ B µ´ ¶³ C µ´ ¶³ H µ´ ¶³ ¡ ¡ ¡ @ @ @ D µ´ ¶³ E µ´ ¶³ I µ´ ¶³ F µ´ ¶³ J µ´ ¶³ G µ´ ¶³ ¡ ¡ ¡ @ @ @ A µ´ ¶³ B µ´ ¶³ C µ´ ¶³ H µ´ ¶³ E µ´ ¶³ I µ´ ¶³ D µ´ ¶³ F µ´ ¶³ J µ´ ¶³ G µ´ ¶³ ¡ ¡ ¡ ª - ? - ¡ ¡ ¡ ª ? - ? - а б Рис. 4.44 152 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 4.11. Фундаментальные циклы Пусть G = hM; Ri — неорграф, имеющий n вершин, m ребер и c ком- понент связности, T — остов графа G. В § 4.8 отмечалось, что T имеет ν ∗ (G) = n − c ребер u 1 , . . . , u n−c , которые будем называть ветвями остова T . Оставшиеся m − n + c ребер v 1 , v 2 , . . . , v m−n+c , не входящие в T , будем называть хордами остова T . Согласно теореме 4.8.1, п. 5, если к лесу T до- бавить произвольную хорду v i , то в полученном графе найдется ровно один цикл, который обозначим через C i . Цикл C i состоит из хорды v i и некоторых ветвей остова T , которые принадлежат единственной простой цепи, соеди- няющей вершины хорды v i . Цикл C i называется фундаментальным циклом графа G относительно хорды v i остова T . Множество {C 1 , . . . , C m−n+c } всех фундаментальных циклов относительно хорд остова T называется фун- даментальным множеством циклов графа G относительно остова T . От- метим, что мощность фундаментального множества циклов равна циклома- тическому числу ν(G) = m − n + c. Обозначим через (w 1 , w 2 , . . . , w m ) последовательность (v 1 , v 2 , . . . , v m−n+c , u 1 , u 2 , . . . , u n−c ) всех ребер графа G. Тогда фундаментальному циклу C i соответствует вектор a = (a i1 , . . . , a im ), определенный по следующему правилу: a ij = ( 1, если w j ∈ C i , 0, если w j / ∈ C i . Теперь фундаментальное множество циклов можно задать с помо- щью матрицы фундаментальных циклов, строки которой являются векторами a 1 , a 2 , . . . , a ν(G) : C a 11 a 12 . . . a 1m a 21 a 22 . . . a 2m . . . . . . . . . . . . . . . . . . . a ν(G),1 a ν(G),2 . . . a ν(G),m . 4.12. РАЗРЕЗЫ 153 Так как каждый фундаментальный цикл C i содержит ровно одну хорду, а именно v i , то матрица C имеет вид C = 1 0 1 0 1 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ a 1,ν(G)+1 . . . a 1m a 2,ν(G)+1 . . . a 2m . . . . . . . . . . . . . . . . . a ν(G),ν(G)+1 . . . a ν(G)m . Таким образом, C = (C 0 1 |C 0 2 ), где C 0 1 — единичная матрица порядка ν(G). Пример 4.11.1. Найдем матрицу фундаментальных циклов графа G, изображенного на рис. 4.45. Так как ν(G) = 8− • • • • • • @ @ @ @ @ @ 1 2 3 4 5 6 7 8 Рис. 4.45 − 6 + 1 = 3, то для получения остова удаляем из графа три ребра. Сопоставим этим ребрам номера 1, 2, 3. Ребрам, входящим в остов, поставим в со- ответствие номера 4, 5, 6, 7, 8. Легко видеть, что фундаментальный цикл C 1 , соответствую- щий хорде 1, состоит из ребер 1, 4, 6, цикл C 2 — из ребер 2, 6, 7, цикл C 3 — из ребер 3, 6, 7, 8. Поэтому матрица фундаментальных циклов C имеет вид C = 1 2 3 4 5 6 7 8 C 1 C 2 C 3 1 0 0 0 1 0 0 0 1 ¯ ¯ ¯ ¯ ¯ ¯ 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 . ¤ § 4.12. Разрезы Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи воз- никают, например, при изучении потоков в сетях (сетью называется связ- ный орграф G = hM; Ri без петель; потоком в сети G называется функция ϕ: R → Z, которая ставит в соответствие дуге некоторое число — вес ду- ги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т. е. множеств дуг, которые соединяют вершины двух непе- ресекающихся множеств вершин) и нахождение ограниченного поперечного 154 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ сечения, которое является самым узким местом. Эти узкие места определя- ют пропускную способность системы в целом. Пусть G = hM; Ri — неорграф M = {M 1 , M 2 } — разбиение множества M . Разрезом графа G (по разбиению M) называется множество всех ребер, соединяющих вершины из M 1 с ¾ ½ » ¼ ¾ ½ » ¼ • • • • • • 6 6 6 Разрез M 1 M 2 Рис. 4.46 вершинами из M 2 (рис. 4.46). Отметим, что в связном графе любой разрез непуст. Непустой разрез K неорграфа G называется про- стым разрезом или коциклом, если любое непустое собственное подмножество K 0 $ K не является разре- зом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро с тем, чтобы полученное множество было непустым разрезом. Теорема 4.12.1. В конечном неорграфе G = hM; Ri, имеющем c ком- понент связности, множество ребер K тогда и только тогда является коциклом, когда граф hM; R \ Ki имеет (c + 1) компонент связности. ¤ Понятия остова и коцикла являются противоположными в том смысле, что остову соответствует минимальное множество ребер, которые связыва- ют посредством маршрутов все вершины связного графа, а коцикл состоит из минимального множества ребер, отделяющего некоторые вершины связ- ного графа от остальных. Следующие две почти очевидные теоремы дают информацию о связи остовов с разрезами, а также циклов с разрезами. Теорема 4.12.2. В связном неорграфе остовное дерево имеет по край- ней мере одно общее ребро с любым из разрезов графа. ¤ Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым раз- резом четное число общих ребер. ¤ В условиях, указанных в предыдущем параграфе, рассмотрим неор- граф G с остовом T . Снова пусть u 1 , u 2 , . . ., u n−c — ветви остова T . Удаляя из остова T произвольную ветвь u i , получаем лес с (c + 1) компонентами связности, т. е. каждое ребро u i является разрезом остова T по некоторому разбиению {M 1 , M 2 } (рис. 4.47). В графе G могут найтись еще какие-то ребра v i 1 , v i 2 , . . ., v i j (являю- щиеся хордами T ), которые соединяют вершины из M 1 и M 2 . Множество 4.12. РАЗРЕЗЫ 155 K i = {u i , v i 1 , . . . , v i j } образует простой разрез, который называется фунда- ментальным разрезом графа G относительно ветви u i остова T . Множе- ство {K 1 , K 2 , . . . , K n−c } всех фундаментальных разрезов графа G называет- ся фундаментальным множеством коциклов графа G относительно осто- ва T . Отметим, что мощность фундаментального множества коциклов не за- висит от выбора остова T и равна корангу ν ∗ (G) = n − c. Аналогично фундаментальным циклам каж- º ¹ · ¸ º ¹ · ¸ • • • • • • • u i M 1 M 2 Рис. 4.47 дому фундаментальному разрезу K i ставится в соответствие вектор b i = (b i1 , . . . , b im ), опре- деляемый по правилу b ij = ( 1, если w j ∈ K i , 0, если w j / ∈ K i . Фундаментальное множество коциклов задает- ся матрицей фундаментальных разрезов K, строки которой являются век- торами b 1 , b 2 , . . ., b ν ∗ (G) : K = b 11 . . . b 1m b 21 . . . b 2m . . . . . . . . . . . . . . . b ν ∗ (G),1 . . . b ν ∗ (G),m . Поскольку каждый фундаментальный разрез K i содержит ровно одну ветвь, а именно u i , матрица K имеет вид K = b 11 . . . b 1,ν ∗ (G) b 21 . . . b 2,ν ∗ (G) . . . . . . . . . . . . . . . . . b ν ∗ (G),1 . . . b ν ∗ (G),ν ∗ (G) ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ 1 0 1 0 1 . Таким образом, K = (K 0 1 |K 0 2 ), где K 0 2 — единичная матрица порядка ν ∗ (G). Отметим, что если C = (C 0 1 |C 0 2 ) — соответствующая матрица фундаменталь- ных циклов, то K 0 1 = (C 0 2 ) T Пример 4.12.1. Найдем матрицу фундаментальных разрезов графа G = = hM; Ri, изображенного на рис. 4.45. Поскольку ν ∗ (G) = 6 − 1 = 5, имеется пять фундаментальных разрезов. Ребру 4 соответствует коцикл K 1 = {1, 4}, 156 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ так как при удалении ребра 4 из остова T множество вершин M разбивается на две части: {a 1 } и M \ {a 1 }, а ребра 1 и 4 образуют разрез по разбиению {{a 1 }, M \ {a}}. Аналогично ребру 5 соответствует коцикл K 2 = {5}, реб- ру 6 — коцикл K 3 = {1, 2, 3, 6}, ребру 7 — коцикл K 4 = {2, 3, 7}, ребру 8 — коцикл K 5 = {3, 8}. Следовательно, матрица фундаментальных разрезов имеет вид K = 1 2 3 4 5 6 7 8 K 1 K 2 K 3 K 4 K 5 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 . ¤ § 4.13. Векторные пространства, связанные с графами Рассмотрим алгебраическую систему Z 2 = h{0, 1}; ⊕, ¯i с двухместны- ми операциями кольцевого сложения ⊕ и умножения ¯, задаваемыми следу- ющими правилами: 0⊕0 = 1⊕1 = 0, 1⊕0 = 0⊕1 = 1, 0¯0 = 0¯1 = 1¯0 = 0, 1 ¯ 1 = 1. Система Z 2 является булевым кольцом (см. § 2.6) и, более того, образует поле. Пусть G = hM; Ri — связный неорграф, имеющий n вершин и m ребер u 1 , u 2 , . . ., u m . Произвольному множеству ребер A ⊆ R поставим в соответствие вектор a = (a 1 , a 2 , . . . , a m ), положив a i ( 1, если u i ∈ A, 0, если u i / ∈ A. Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора (a 1 , a 2 , . . . , a m ) нулей и единиц най- дется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества ребер R и множе- ством всех наборов длины m, состоящих из нулей и единиц: P(R) ↔ {0, 1} m Пусть a = (a 1 , . . . , a m ) и b = (b 1 , . . . , b m ) — наборы (векторы) из {0, 1} m . Опре- делим сложение векторов с помощью соотношения a⊕b = (a 1 ⊕b 1 , . . . , a m ⊕b m ) по правилам, определенным в поле Z 2 . Кроме этого, определим произведение векторов на элементы λ ∈ {0, 1}, положив λ¯a = (λ¯a 1 , . . . , λ¯a m ). Множе- ство векторов {0, 1} m с операциями сложения ⊕ и умножения ¯ на элементы 4.13. ВЕКТОРНЫЕ ПРОСТРАНСТВА, СВЯЗАННЫЕ С ГРАФАМИ 157 поля Z 2 образует линейное пространство над полем Z 2 . Это пространство обозначим через V m (Z 2 ). Отметим, что сложение ⊕ векторов a и b соответствует кольцевой сумме множеств ребер A и B, представляемых этими векторами. Действительно, равенство a i ⊕ b i = 1 выполняется тогда и только тогда, когда a i = 1, b i = 0 (т. е. u i ∈ A \ B) или a i = 0, b i = 1 (т. е. u i ∈ B \ A). Следовательно, сумме a ⊕ b соответствует множество (A \ B) ∪ (B \ A) = A ⊕ B. Внутреннее произведение векторов a = (a 1 , a 2 , . . . , a m ) и b = (b 1 , b 2 , . . . , b m ) определяется соотношением (a, b) = a 1 ¯ b 1 ⊕ a 2 ¯ b 2 ⊕ . . . ⊕ a m ¯ b m . Равенство (a, b) = 0 означает, что четное число произведений a i ¯ b i равно 1. Для таких произведений a i = 1, b i = 1 и, следовательно, соответствующие векторам a и b множества ребер A и B имеют четное число общих ребер. Множество ребер A называется границей (кограницей), если A есть объ- единение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A 1 ⊕ A 2 границ (кограниц) A 1 и A 2 также является границей (когра- ницей). Следовательно, множества V Γ = {a | вектор a соответствует некоторой границе}, V K = {b | вектор b соответствует некоторой когранице} образуют линейные подпространства пространства V m (Z 2 ). Теорема 4.13.1. 1. Если {C 1 , C 2 , . . . , C m−n+1 } — фундаментальное мно- жество циклов графа G, то множество B C {a 1 , a 2 , . . . , a m−n+1 } векто- ров, соответствующих фундаментальным циклам, образует базис подпро- странства границ V Γ . 2. Если {K 1 , K 2 , . . . , K n−1 } — фундаментальное множество коциклов графа G, то множество B K = {b 1 , b 2 , . . . , b n−1 } векторов, соответствую- щих фундаментальным разрезам, образует базис подпространства когра- ниц V K . Следствие 4.13.2. 1. Размерность dim V Γ подпространства границ V Γ равна цикломатическому числу ν(G), а размерность dim V K подпростран- ства кограниц V K равна корангу ν ∗ (G). 2. Любой цикл (коцикл) в графе можно представить в виде коль- цевой суммы некоторых фундаментальных циклов (разрезов). 158 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Два подпространства V 1 и V 2 векторного пространства V m (Z 2 ) называют- ся ортогональными (обозначается V 1 ⊥V 2 ), если для любых векторов a ∈ V 1 и b ∈ V 2 их внутреннее произведение (a, b) равно 0. Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K име- ет четное число общих ребер, т. е. для соответствующих векторов a и b их внутреннее произведение (a, b) равно нулю. В частности, для любых векто- ров a i ∈ B C и b j ∈ B K справедливо (a, b) = 0. Так как множества B C и B K образуют базисы подпространств V Γ и V K , то V Γ ⊥V K Отметим также, что при умножении матрицы фундаментальных цик- лов C на транспонированную матрицу фундаментальных разрезов K T в поле Z 2 строка a i умножается на столбец b j по правилу внутреннего про- изведения и (a i , b j ) = 0. Это означает, что C · K T = 0, а также K · C T = 0. Упражнение.Проверить, что для матриц C и K из примеров 4.11.1 и 4.12.1 справедливо C · K T = 0. § 4.14. Раскраски графов Пусть G = hM; Ri — неорграф без петель. Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если [a, b] — ребро, то вер- шины a и b имеют различные цвета. Хроматическим числом χ(G) графа G называется минимальное число цветов, требующееся для раскраски G. Пример 4.14.1. Так как в полном графе K n любые две различные вер- шины связаны ребром, то χ(K n ) = n. ¤ Многие практические задачи сводятся к построению раскрасок графов. Пример 4.14.2. 1. Рассмотрим задачу составления расписания. Пред- положим, что нужно прочесть несколько лекций за кратчайшее время. Чте- ние каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лек- тор). Построим граф G, вершины которого биективно соответствуют лекци- ям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие верши- нам одного цвета, могут читаться одновременно. Напротив, любое допусти- мое расписание определяет раскраску графа G. Оптимальные расписания 4.14. РАСКРАСКИ ГРАФОВ 159 соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно χ(G). 2. Рассмотрим граф G, вершины которого — страны, а ребра соединяют страны, имеющие общую границу. Числу χ(G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет. ¤ Существуют и практические задачи, связанные с раскраской ребер в муль- тиграфе. Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для про- извольного неориентированного мультиграфа G = hM, U, P i реберным муль- тиграфом L(G) называется тройка hU, M, P 0 i, где P 0 ⊆ U × M × U, и выпол- няется (u, a, v) ∈ P 0 тогда и только тогда, когда в мультиграфе G вершина a является концом ребер u и v. Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G). Пример 4.14.3. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводни- ка, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами — проводники. ¤ Неорграф G называется бихроматическим, если χ(G) = 2. Неорграф G = hM; Ri называется двудольным, если множество всех ребер графа G образует разрез графа G, т. е. для некоторого разбиения множества вершин {M 1 , M 2 } концы любого ребра принадлежат разным частям разбиения. Теорема 4.14.1. Пусть G — неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны: 1) G — бихроматический граф; 2) G — двудольный граф; 3) G не содержит циклов нечетной длины. ¤ Следствие 4.14.2. Если G — лес, то χ(G) 6 2. ¤ Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа G. Теорема 4.14.3. Для любого неорграфа G без петель выполняется нера- венство χ(G) 6 deg(G) + 1. ¤ 160 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным. Алгоритм последовательной раскраски. 1. Произвольная вершина a 1 графа G принимает цвет 1. 2. Если вершины a 1 , . . . , a i раскрашены l цветами 1, 2, . . . , l, l 6 i, то новой произвольно взятой вершине a i+1 припишем минимальный цвет, не исполь- зованный при раскраске вершин из множества {a j | ρ(a i+1 , a j ) = 1, j < i}. ¤ Для некоторых классов графов последовательная раскраска является ми- нимальной. В общем случае это не так. § 4.15. Планарные графы Неорграф G называется планарным, если его можно изобразить на плос- кости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости на- зывается плоским. Таким образом, если граф имеет плоское изображение, то он является планарным. Пример 4.15.1. Граф K 4 (рис. 4.48а) планарен, поскольку может быть изображен, как показано на рис. 4.48б. ¤ Граф, описанный в примере 4.14.2, п. 2, является планарным. Также пла- нарным является граф, вершины которого — отверстия печатной платы, а ребра — проводники печатной платы, соединяющие отверстия. Рассмотрим операцию подразбиения ребра в графе G = hM; Ri. После подразбиения ребра [a, b] ⊆ R получается граф G 0 = hM 0 ; R 0 i, где M 0 = M∪ ∪{ab}, R 0 = (R\[a, b])∪[a, ab]∪[ab, b], т. е. ребро [a, b] заменяется на (a, b)-цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер. • • • • ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ • • • • ¢ ¢ ¢ ¢ ¢ ¢ ¡ ¡ ¡ A A A A A A @ @ @ а б Рис. 4.48 4.15. ПЛАНАРНЫЕ ГРАФЫ 161 • • • • • • • • • • • ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ @ @ @ @ @ @ ©© ©© ©© ©© ©© © © HH HH HH HH HH H H K 5 K 3,3 Рис. 4.49 Не всякий неорграф является планарным. Критерий планарности опи- сывает Теорема 4.15.1 (теорема Понтрягина—Куратовского). Неорграф G пла- нарен тогда и только тогда, когда G не содержит часть, гомеоморфную K 5 или K 3,3 (рис. 4.49). ¤ Эквивалентная форма критерия планарности описана в следующей тео- реме. Теорема 4.15.2. Тогда и только тогда неорграф G планарен, когда G не содержит частей, стягиваемых (т. е. получаемых последовательностью отождествлений вершин, связанных ребрами) к графу K 5 или K 3,3 (рис. 4.49). ¤ Вместе с тем трехмерного евклидова пространства оказывается доста- точно для изображения любого конечного и счетного графа без пересечения дуг вне их концов. Теорема 4.15.3. Любой граф, состоящий не более чем из 2 ω вершин, может быть изображен в пространстве R 3 без пересечения дуг вне их концов. Доказательство. Пусть G = hM; Ri — граф, для которого |M| 6 2 ω Тогда имеем |R| 6 2 ω . Расположим все точки графа G на некоторой пря- мой l и каждой дуге из R разнозначно сопоставим плоскость, содержащую прямую l. Искомое изображение графа G получается после проведения всех дуг в соответствующих плоскостях. ¤ Известна оценка хроматического числа планарных графов. 162 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Теорема 4.15.4 (теорема о четырех красках). Если G — планарный граф, то χ(G) 6 4. ¤ При исследовании принципиальной электрической схемы радиоэлектрон- ного устройства с точки зрения возможности ее реализации с помощью пе- чатного монтажа или монтажа на слоях микросхемы важно знать ответ на следующие вопросы: |