Основы дискретной математики В.А. Осипова (552659), страница 24
Текст из файла (страница 24)
2. Дерево — это связный граф, у которого число ребер на единицу меньше числа вершин. 3. Дерево — это граф, не содержащий циклов такой, что если любую пару несмежных вершин соединить ребром, то в полученном графе будет ровно один и притом простой цикл. Докажем эквивалентности основного определения дерева выполнимости определения 1. Действительно, поскольку С связный граф, любые две его вершины и и у связаны цепью. Если бы сУЩествовали Две Цепи о, сп, с;2, ..., с,гп У и с, е и и.2, ..., е;т, у, соединяющие с и у, то в графе существовал бы цикл с, сп, с42, ..., сс», у, с, с ь ..., с ь с, что противоречит определению дерева. Обратно, если любые две вершины графа можно соединить единственной цепью, то он, очевидно, связен.
Если бы в нем существовал цикл с, сп, с;2, ..., сп, с, то, выбрав в этом цикле две различные вершины с;р и с;д (р < у), мы показали бы наличие ДвУх Цепей см, с,в«п ..., сз, с, оп, с,.2, ..., и,р и;р и с;р, ю;р«п ..., е,у ь с;4, соеДинЯюЩих веРшины с;р и о,«. Не доказывая строго эквивалентность остальных определений дерева, заметим следующее. Если последовательно «разрушать» дерево, отбрасывая висячие вершины (т. е. вершины, степень которых равна единице) вместе с инцидентными им ребрами, то при этом, отбрасывая одну вершину, мы отбрасываем и ребро.
В конце процесса останется одна изолированная вершина. Следовательно, число ребер в этом графе на единицу меньше числа вершин. Поскольку мы уже доказали, что в дереве любые две вершины с и у соединены единственной цепью, то в силу утверждения 4.1 они соединены единственной простой цепью.
Если к дереву С добавить ребро (с, у), то это ребро вместе с единственной простой цепью, соединяющей с и у образует один и притом простой цикл. 4.5.2. Остовное дерево графа Пусть С =( '»; Я > — произвольный неориентированный граф. Остовиым деревом С' графа С называется такой его подграф, который является деревом и содержит все вершины исходного графа С. Пример 4.15. Пусть сеть связи описывается графом, вершины которого — узлы сети, ребра — каналы связи.
Если выйдут из строя некоторые каналы, то между узлами связь может 139 138 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4.5. Деревья быть нарушена. Какие каналы можно удалять без нарушения связи? Оставшийся после удаления всех таких ребер граф является остовным деревом. Остовные деревья широко используются, например, при решении задач, которые возникают в электротехнике при расчете электрических цепей. Г.
Кирхгоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике 1дуге) и в каждом контуре рассматриваемой электрической цепи. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т. д., он рассматривал структуры, содержащие только вершины и связи (ребра или дуги), причем для связей не нужно указывать, каким типам электрических элементов они соответствуют.
Таким образом, в действительности Кирхгоф заменил каждую электрическую цепь соответствующим ей графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи. Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой в теории электрических цепей), в соответствии с которой достаточно ограничиться только простыми циклами графа, определяемыми любыми из его остовных деревьев. Опишем алгоритм выделения остовного дерева связного графа с У вершинами. Алгоритм 4.7. 1.
Выбираем в С произвольную вершину и1. Эта вершина образует подграф С1 графа С, являющийся деревом. Полагаем г' = 1. 2. Если 4 = и, то ф— остовное дерево графа С. В противном случае переходим к п. 3. 3. Пусть уже построен граф С;, содержащий вершины и1, и2, ..., и; графа С, 1 < 4 < и — 1 и являющийся деревом.
Строим граф С1+1, добавляя к графу С, новую вершину иьь1 Е Е У, смежную с некоторой вершиной и графа С;, а также ребро (и;+1, и ). Присваиваем 4:= г'+ 1 и переходим к п. 2. Для обоснования алгоритма 4.7 заметим, что в силу связности обязательно найдется вершина иьь1, удовлетворяющая условию п.
3. Полученный в п. 3 граф С; ь1 — дерево. Он, очевидно, связен и не имеет циклов, так как добавленная вершина и. и1+1 является висячей, а в С; нет циклов. Используя алгоритм 4.7 выделим остовное дерево графа С, изображенного на рис. 4.21. Последовательность графов С;, получаемых в результате выполнения шагов алгоритма приведена на рис. 4.22, п~ н~ и, С, С, Ряс. 4.2Е Рис. 4.22. Поскольку и = 5, Сь — остовное дерево графа С. Заметим, что алгоритм 4.7 позволяет выделить одно из возможных остовных деревьев графа, общее число которых достаточно велико.
Например, для полного графа с и вершинами (т. е. такого и-вершинного графа, любые две вершины которого соединены ребром) оно равно и" 2. Рассмотрим связный неориентированный С =< У, Я > с и вершинами, каждому ребру д1 которого поставлен в соответствие вес (длина) 1(щ) > О. Остовное дерево 12 =< У, Я' > графа С называется минимальным, если сумма весов его ребер т. е.
С сне Р минимальна. Поиску минимальных остовных деревьев отводится решение следующих вопросов: при прокладке дорог (газопроводов, линий электропередач и т. д.) необходимо связать и пунктов некоторой сетью так, чтобы общая длина «линий связи» была минимальной. Пункты можно считать вершинами полного графа (т. е. такого и-вершинного графа, любая пара вершин которого соединена ребром), весом ребра — расстояние между пунктами. Так как разветвление дорог допускается в заданных пунктах— 146 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4.5.
Деревья вершинах, то минимальное остовное дерево и будет сетью дорог, имеющей минимальную общую длину. Алгоритм нахождения минимального остовного дерева состоит из следующих этапов. Алгоритм 4.8. (Алгоритм Краскала.) 1. Выберем в графе С ребро наименьшего веса и обозначим его 7ь 2. Если совокупность ребер Л, ~2, ..., Л 1 уже выбрана, то добавим к ней ребро Д, отличное от уже выбранных, не образующее циклов с ребрами Л, 22, ..., ~~ 1 и такое, что его вес наименьший. Через и — 1 шаг мы построим минимальное остовное дерево графа С, именно, граф Р, образованный ребрами 7п ~~, ..., 7"„1 и инцидентными им вершинами есть минимальное остовное дерево С. Для обоснования алгоритма 4.8 предположим, что некоторое другое остовное дерево Я имеет вес наименьший чем Р т.
е. 1(Я) < 1(Р). Пусть 2ь — первое из ребер таких, что 7ь Е Р и ~ь ф Я. Добавим ребро Д к дереву Я. Получим, и притом единственный цикл С, проходящий через ~~,. В цикле С существует такое ребро и, что и )с Р и в соответствии с п. 2 1(и) > 1(~ь). Заменим в Я ребро и на ребро рте Получим граф оп который также является остовным деревом, поскольку в нем нет циклов и число ребер п — 1. При этом 1(Я1) < 1(Я). Заметим, что дерево о1 имеет на одно общее ребро больше с Р чем Я. Последовательно преобразуем Я в Р строя остовные деревья ~п ~2, ..., Яь.
При этом ЦЯ) ) 1(Я1) ) ° . ) 1(Яь) ) ЦР), что противоречит условию 1(Я) < ЦР). Пример 4.16. На рис. 4.24, 1) — 7) изображена последовательность графов, получаемых в результате применения шагов алгоритма 4,8 к графу, изображенному на рис. 4.23. Вес результирующего минимального остовного дерева равен 13. п4 О2 У~ Рис. 4.23. О .
О О 2) пв Задачи и упражнения 1. Показать, что все деревья с тремя вершинами изоморфны. 2. Найти два неизоморфных дерева с четырьмя вершинами и три — с пятью. 3. Доказать, что число различных деревьев, которые можно построить па п данных вершинах, равно и" 4. Показать, что у дерева с более чем одной вершиной найдутся, по крайней мере, две висячие вершины. 5. Показать, что дерево, содержащее ровно две висячие 6) Рис. 4.24. 4.6.
Плоские граФы пи Рис. 4.26. Рис. 4.26 Рис. 4.27. 4.6. Плоские графы 142 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ вершины, является простой цепью. 6. Доказать, что цикломатическое число дерева равно нулю. 7. Определить какое-либо остовное дерево для графов. 8. Определить минимальное остовное дерево для нагруженного графа. Говорят, что неориентированный граф С вЂ” планарный, если его можно уложить на плоскости так, чтобы вершинам отвечали различные точки, ребрам — простые дуги, и чтобы никакие два ребра не имели общих точек, отличных от их границ (т. е.
ребра С могут пересекаться только в вершинах). Плоский — это планарный граф, уже уложенный на плоскости. Пример 4.17. Графы, изображенные на рис. 4.25 — планарные. На рис. 4.26 представлены их плоские изображения. Рассмотрим следующую задачу (задача о трех девушках и трех колодцах). От домов трех девушек к трем колодцам проложены тропинки (рис. 4.27). Можно ли проложить их так, чтобы никакие две тропинки не пересекались? Иными словами: является ли планарным соответствующий граф Кз з с несмежными между собой вершинами им вз, ез и Ум уг, уз такими, что каждая вершина е; смежна каждой вершине У;, 4 = 1, 2, 3? Ответ на этот вопрос будет дан ниже.
Еще один граф, планарность которого мы обсудим, это граф 145 4.6. Плоские граФы ребер и г" граней, то и — т+ )'=2. ~ — 1=т — и+1, Рис. 4.28. т < Зи — 6, т<2и — 4. Рис. 4.29. 144 Глава 4, ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Кв — полный граф с пятью вершинами, изображенный на рис. 4.28. Гранью плоского графа называется область плоскости, ограниченная ребрами и не содержащая внутри себя ни вершин, ни ребер. Край грани — это цикл, образованный граничными ребрами втой грани. Две грани смежны, если они имеют общее ребро. Географическая карта, не содержащая стран анклавов— плоский граф.
В етом графе гранями являются страны, степень каждой вершины больше или равна трем (см. рис. 4.29). У всякого плоского графа имеется единственная неограниченная грань — бесконечная грань, остальные грани конечны. В графе, изображенном на рис. 4.29 ~ — бесконечная грань, остальные грани, т. е. а, 5, с, д, е — конечны. В случае плоского графа базис циклов можно найти, используя следующее утверждение, которое приведем без доказательства. Утверждение 4.7. В связном плоском графе число различных конечных граней равно цикломатпическому числу. Следствием из итого утверждения является известная формула Эйлера: если связный плоский граф С имеет и вершин, т Действительно, поскольку число конечных граней равно цикломатическому числу г(С) = т — и + 1, то откуда и — т + г' = 2.
С помощью формулы Эйлера можно установить, что графы Ке и Кз 3 не являются планарными. Пусть С вЂ” связный плоский граф с и вершинами, т ребрами и г гранями, не являющийся деревом. Тогда а если длина любого его простого цикла больше или равна 4, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
