Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
 Скачать 1.36 Mb.
|
|
вернуться обратно, пройдя по каждому мосту ровно один раз? Неориентированный мультиграф G, представляющий задачу, показан на рис. 3.28. Вершины x 1 , соответствуют берегам реки, x 2 , островам, ребра мультиграфа — мостам. Следовательно, на языке теории графов задача формулируется следующим образом существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа? Выдающимся математиком и механиком Л. Эйлером сформулирован и доказан критерий того, что связный неориентированный мульти- граф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, называется эйлеровым, и муль- тиграф, в котором имеется эйлеров цикл, также называется эйлеро- вым. Теорема 3.7.1. Связный неориентированный мультиграф является эйлеровым тогда и только тогда, когда степень каждой из его вершин — четное число. Мультиграф, изображенный на рис. 3.28, не содержит эйлеров цикл, поскольку в нем есть вершины, имеющие нечетную степень. Более того, все его вершины имеют нечетную степень. Опишем алгоритм построения эйлерова цикла в эйлеровом мульти- графе. Этот алгоритм задается следующими правилами. Выбрать произвольно некоторую вершину a. 2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший номера предыдущего вычеркнутого ребра d d Рис. Рис. 3.28 3.7. ОБХОДЫ ГРАФОВ 4. Находясь в вершине x, не выбирать ребро, соединяющее x с если имеется возможность иного выбора. Находясь в вершине x, не выбирать ребро, ко 2 3 4 5 6 7 Рис. 3.29 торое является перешейком (те. ребром, при удалении которого граф, образованный невычеркну- тыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер. П р им ер. Найдем эйлеров цикл в эйлеровом графе, изображенном на рис. 3.29. После выбора вершины a и прохождения ребер и 2 имеются три возможности выбора ребра 3, 6 или 7. Так как ребро является перешейком, выбираем следующее ребро из оставшихся, например. Далее обходим оставшиеся ребра и получаем эйлеров цикл, 2, 3, 4, 5, 6, 7, Будем говорить, что набор реберно непересекающихся цепей покрывает граф G, если каждое ребро графа G входит в одну из этих цепей. Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопожатиях число k четно. Рассмотрим граф G , полученный добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами графа G нечетной степени. Поскольку степени всех вершин графа G четны, G содержит эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, содержащих все ребра графа G, те. покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересе- кающихся цепей, имеет не более 2r вершин нечетной степени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2. Тем самым доказана Теорема 3.7.2. Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непе- ресекающихся цепей равно В частности, при k = 2 граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащая все ребра графа, называется эйлеровой. Мы рассмотрели обходы ребер графа. Следующей нашей целью является изучение обходов вершин графа. Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам такой цикл также Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ называется гамильтоновым. Гамильтоновой называется и простая цепь, содержащая все вершины графа. Очевидно, что любой граф, ребра которого образуют простой цикл, является гамильтоновым, аграф, показанный на рис. 3.29, — негамильтоновым. Несмотря на схожесть задач о нахождении эйлеровых и гамиль- тоновых циклов, решение последней значительно сложнее. Известны следующие достаточные условия существования гамильтоновых циклов в связном неорграфе G без петель, имеющем n 3 вершин: Теорема 3.7.3. Если для любых двух различных несмежных вершин и b графа G выполняется условие deg a + deg b n, то существует гамильтонов цикл. Следствие 3.7.4. Если для любой вершины a графа G выполнено условие deg a n/2, то существует гамильтонов цикл. С задачей нахождения гамильтонова цикла связана следующая задача коммивояжера. Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми известны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный город. Если таких маршрутов много, требуется найти кратчайший из них. Математическая постановка задачи выглядит так найти гамильто- нов цикл минимального веса. Отметим некоторые практические задачи, сводящиеся к задаче коммивояжера. Пусть граф задает сеть коммуникаций между фиксированными центрами. Необходимо построить маршрут, обеспечивающий посещение всех центров ровно по одному разу. Имеется станок с числовым программным управлением, который высверливает отверстия в печатных платах по заданной программе. Составляя граф, в котором вершины соответствуют требуемым отверстиям, получаем задачу нахождения обхода вершин, такого, что суммарное время, затраченное на него, было бы минимальным Остовы графов Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являются дере- вья. На рис. 3.30 изображен лес, состоящий из двух деревьев 3.8. ОСТОВЫ ГРАФОВ e e e e ¡ ¡ ¡ ¡ ¡ • • • ¡ ¡ ¡ ¡ ¡ • • • • • e e e Рис. Теорема 3.8.1. Для неорграфа G без петель, содержащего n вершин, следующие условия эквивалентны) G — дерево) G — связный граф, содержащий n − 1 ребро) G — ациклический граф, содержащий n − 1 ребро) любые две несовпадающие вершины графа G соединяет единственная простая цепь) G — ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. Пусть G = M ; R — неорграф. Часть G = M ; R графа G называется остовом или каркасом графа G, если M = M и G — лес, который на любой связной компоненте графа G образует дерево. Таким образом, если G — связный граф, то остов G является деревом, которое будем называть остовным деревом графа Понятие остова для орграфа G определяется как часть G графа, для которой F (G ) является остовом графа F (G). Аналогично вводится понятие остовного дерева для связного орграфа Очевидно, что в каждом графе существует остов разрушая в каждой связной компоненте циклы, те. удаляя лишние ребра, получаем остов. П р им ер. В качестве остова графа G, изображенного на рис. 3.31, можно взять лесс ребрами 2, 3, 4, 6, 7 (вообще говоря, остов определяется неоднозначно). Из теоремы 3.8.1. вытекает Следствие 3.8.2. Число ребер произвольного неорграфа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m − n + c, где m — число ребер — число вершин, c — число компонент связности графа Доказательство. Действительно, если я компонента связности графа G содержит n вершин, то по теореме 4.8.1 соответствующее дерево K i остова содержит n i − 1 ребро. Следовательно, для Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 2 3 1 4 6 7 8 • • • • • • d d d 2 3 1 4 3 3 3 5 1 Рис. Рис. получения K i из компоненты C i нужно удалить m i − (n i − 1) ребер, где m i — число ребер в C i . Суммируя удаляемые ребра по всем компонентам связности и замечая, что c i=1 m i = m, c i=1 n i = n, получаем, что необходимо удалить c i=1 (m i − n i + 1) = m − n + c ребер. Число ν(G) = m − n + c называется цикломатическим числом или циклическим рангом графа G. Число ν ∗ (G) = n − c называется коциклическим рангом или корангом. Таким образом, ν ∗ (G) есть число ребер, входящих в любой остов графа G, и ν(G) + ν ∗ (G) = Очевидны следующие два следствия. Следствие 3.8.3. Неорграф G является лесом тогда и только тогда, когда ν(G) = Следствие 3.8.4. Неорграф G имеет единственный цикл тогда и только тогда, когда ν(G) = Опишем алгоритм нахождения остова минимального веса во взвешенном графе. Эта задача возникает при проектировании линий электропередач, дороги т. п, когда требуется заданные центры (вершины) соединить некоторой системой каналов связи (ребер) так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом (ребром, либо через другие центры и каналы, те. цепью, у которой общая длина (или, например, стоимость) каналов связи была минимальной. Искомая сеть будет остовом минимального веса полного графа. Алгоритм, решающий задачу нахождения остова минимального веса во взвешенном графе G = M; R , заключается в следующем. Строим граф T 1 , состоящий из множества вершин M и единственного ребра u 1 , которое имеет минимальный вес. Если граф T i уже построен и i < n − c, где n = |M |, c = c(G), то строим граф T i+1 , добавляя к множеству ребер графа T i ребро u имеющее минимальный вес среди ребер, не входящих вине составляющих циклов с ребрами из T i 3.8. ОСТОВЫ ГРАФОВ 75 Приведенный алгоритм, в частности, позволяет находить остов в невзвешенном графе, положив w(u i ) = 1 для всех ребер u i ∈ Пример. На рис. 3.32 показан остов минимального веса взвешенного графа. Вес остова равен При решении прикладных задач часто возникает необходимость обхода вершин графа, связанная с поиском вершин, удовлетворяющих определенным свойствам. Пусть G = M; R — связный неориентированный граф, T — некоторый остов графа G, a — некоторая фиксированная вершина, называемая корнем дерева T . Разместим вершины из M по этажам таким образом, чтобы корень a находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами — еще на единицу ниже и т. д. (рис. 3.33). Таким образом, получаем e(a) + 1 этажей, где e(a) — эксцентриситет вершины Опишем обход графа по глубине. При та d d d d d d d rr r d d a 1 2 3 Риском обходе после очередной рассмотренной вершины выбирается смежная с ней вершина следующего этажа. Если очередная рассмотренная вершина висячая и ее достижение не дает желаемого решения задачи, то возвращаемся до ближайшей вершины степени и просматриваем вершины другого, еще не пройденного маршрута в таком же порядке и т. д. На рис. 3.34 показана очередность обхода вершин по глубине графа, изображенного на рис. При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа производится только после просмотра всех вершин данного этажа. На рис. 3.35 показан порядок обхода по ширине графа, изображенного на рис. Очевидно, что при обходе всех вершин оба подхода поиск в глубину и поиск по ширине — эквивалентны. Если же достаточно найти одну d d d d d d d d d rr rr d d 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 • • • • • • • • • • • • • • • • • • • d d d d d d d d d d rr rr d d 1 2 5 11 16 17 6 3 7 12 13 4 8 9 1415 18 19 Рис. Рис. 3.35 Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ вершину с определенным свойством, то целесообразность применения поиска решения по глубине или по ширине определяется структурой дерева. Если дерево является достаточно широким, а висячие вершины расположены на сравнительно близких этажах, то целесообразно вести поиск по глубине. Для глубоких узких деревьев, когда висячие вершины могут встретиться на различных этажах и их разброс поэта- жам достаточно велик, предпочтение отдается поиску по ширине. Отметим, что при компьютерной реализации обходов по глубине и ширине целесообразно использовать задание дерева структурой смежности вершин Фундаментальные циклы Пусть G = M; R — неорграф, имеющий n вершин, m ребер и c компонент связности, T — остов графа G. В § 3.8 отмечалось, что имеет ν ∗ (G) = n−c ребер u 1 , . . . , u n−c , которые будем называть ветвями остова T . Оставшиеся m−n+c ребер v 1 , v 2 , . . . , v m−n+c , не входящие в T , будем называть хордами остова T . Согласно теореме 3.8.1, п. если к лесу T добавить произвольную хорду v i , тов полученном графе найдется ровно один цикл, который обозначим через C i . Цикл C i состоит из хорды v и некоторых ветвей остова T , которые принадлежат единственной простой цепи, соединяющей вершины хорды v i . Цикл C i называется фундаментальным циклом графа G относительно хорды v i остова T . Множество {C 1 , . . . , C m−n+c } всех фундаментальных циклов относительно хорд остова T называется фундаментальным множеством циклов графа G относительно остова T . Отметим, что мощность фундаментального множества циклов равна цикломатическому числу ν(G) = m − n + Обозначим через (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 ), определенный последующему правилу ij = 1, если w j ∈ C i , 0, если w j / ∈ Теперь фундаментальное множество циклов можно задать с помощью матрицы фундаментальных циклов, строки которой являются векторами. РАЗРЕЗЫ a 21 a 22 a 2m a ν(G),1 a ν(G),2 . . . Так как каждый фундаментальный цикл C i содержит ровно одну хорду, а именно v i , то матрица C имеет вид = 1 0 1 0 1 a 1,ν(G)+1 a 1m a 2,ν(G)+1 a 2m a ν(G),ν(G)+1 . . . Таким образом, C = (C 1 |C 2 ), где C 1 — единичная матрица порядка ν(G). П р им ер. Найдем матрицу фундаментальных циклов графа, изображенного на рис. 3.36. Так как ν(G) = 8 − 6 + 1 = то для получения остова удаляем из графа d d d d d 1 2 3 4 5 6 7 Рис. три ребра. Сопоставим этим ребрам номера, 2, Ребрам, входящим в остов, поставим в соответствие номера 4, 5, 6, 7, 8. Легко видеть, что фундаментальный цикл C 1 , соответствующий хорде 1, состоит из ребер 1, 4, 6, цикл из ребер 2, 6, 7, цикл C 3 — из ребер 3, 6, 7, 8. Поэтому матрица фундаментальных циклов 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 . § 3.10. Разрезы Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью называется связный орграф G = M; R без петель потоком в сети называется функция ϕ : R → Z, которая ставит в соответствие дуге некоторое число — вес дуги. В этих задачах фундаментальную роль играют изучение поперечных сечений сети (те. множеств дуг, которые соединяют вершины двух непересекающихся множеств вершин Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ и нахождение ограниченного поперечного сечения, которое является самым узким местом. Эти узкие места определяют пропускную способность системы в целом. Пусть G = M; R — неорграф M = {M 1 , M 2 } • • • • • • T T T Разрез M 1 M 2 Рис. 3.37 — разбиение множества M. Разрезом графа G (по разбиению M) называется множество всех ребер, соединяющих вершины из с вершинами из рис. 3.37). Отметим, что в связном графе любой разрез непуст. Непустой разрез K неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество K K не является разрезом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро стем, чтобы полученное множество было непустым разрезом. Теорема 3.10.1. В конечном неорграфе G = M; R , имеющем c компонент связности, множество ребер K тогда и только тогда является коциклом, когда граф M ; R \ K имеет (c + 1) компонент связности. Понятия остова и коцикла являются противоположными в том смысле, что остову соответствует минимальное множество ребер, которые связывают посредством маршрутов все вершины связного графа, а коцикл состоит из минимального множества ребер, отделяющего некоторые вершины связного графа от остальных. Следующие две почти очевидные теоремы дают информацию о связи остовов с разрезами, а также циклов с разрезами. Теорема 3.10.2. В связном неорграфе остовное дерево имеет по крайней мере одно общее ребро с любым из разрезов графа. Теорема 3.10.3. В связном неорграфе любой цикл имеет с любым разрезом четное число общих ребер. В условиях, указанных в предыдущем параграфе, рассмотрим неор- граф G с остовом T . Снова пусть u 1 , u 2 , . . ., u n−c — ветви остова T Удаляя из остова T произвольную ветвь u i , получаем лесс+ компонентами связности, те. каждое ребро u является разрезом остова по некоторому разбиению {M 1 , рис. В графе G могут найтись еще какие-то ребра v i 1 , v i 2 , . . ., v являющиеся хордами T ), которые соединяют вершины из и M 2 . Множество образует простой разрез, который называется фундаментальным разрезом графа G относительно ветви u i 3.10. РАЗРЕЗЫ 79 остова T . Множество {K 1 , K 2 , . . . , K n−c } всех фундаментальных разрезов графа G называется фундаментальным множеством коциклов графа G относительно остова T . Отметим, что мощность фундаментального множества коциклов не зависит от выбора остова T и равна корангу ν ∗ (G) = n − Аналогично фундаментальным циклам каж- • • • • • • • u Рис. дому фундаментальному разрезу K i ставится в соответствие вектор b i = (b i1 , . . . . . . , b определяемый по правилу b ij = 1, если w j ∈ K i , 0, если w j / ∈ Фундаментальное множество коциклов задается матрицей фундаментальных разрезов K, строки которой являются векторами b |