Новиков Ф.А. Дискретная математика для программистов (860615), страница 62
Текст из файла (страница 62)
ДеревьяЩv.»1V,V-VaV.X жV,V>Р и с . 9 . 1 8 . Кратчайший остов, приближённое и точное решения задачи Ш т е й н е р апрограммированию и конструированию эффективных алгоритмов. В качестве рекомендуемых для программистов источников назовём [2], [14], [26]. Алгоритмы9.1 и 9.2 заимствованы из редкой книги [6], в которой приведено большое числоалгоритмов на графах, в том числе пе очень широко известных. Алгоритмы 9.3 и9.4 — программистский фольклор, переработанный автором. Алгоритмы 9.5-9.7общеизвестны.
Алгоритмы операций с деревом сортировки (алгоритмы 9.8-9.10)описаны в [14], откуда они заимствованы с некоторыми дополнительными уточнениями способов реализации. В книге [26] можно найти краткие и доступныеописания алгоритмов работы с АВЛ-деревьями. Подробное изложение и анализ алгоритмов работы с различными классами деревьев имеется в прекрасномучебнике [27]. Алгоритмы поиска кратчайшего остова (алгоритмы 9.11-9.13)принадлежат к числу известных классических алгоритмов, их описание можнонайти во многих источниках, например, в [21].Упражнения9.1.
Нарисовать диаграммы всех деревьев с 7 вершинами.9.2. Допустим, что в ордереве все узлы, кроме листьев, имеют одну и ту же полустепепь исхода п. В этом случае говорят, что дерево имеет постояннуюширину ветвления п. Оценить высоту h ордерева, которое имеет р узлови постоянную ширину ветвления п.9.3. Составить алгоритм преобразования обратной польской записи арифметического выражения в прямую польскую запись.9.4. Какой вид будет иметь дерево сортировки после того, как в него последовательно добавили следующие текстовые элементы: «1», «2», «3», «4», «5»,«6», «7», «8», «9», «10», «11», «12», «13», «14», «15», «16», «17», «18», «19»?9.5. Доказать, что полный граф Кр имеет р(р~2^ остовов (это утверждение известно как формула Кэли1.).1Артур Кэли ( 1 8 2 1 - 1 8 9 5 )Глава 10Циклы, независимостьи раскраскаПосле рассмотрения ациклических связных графов, то есть деревьев, естественно перейти к рассмотрению графов с циклами.
Некоторые задачи, связанные сциклами, в частности, с гамильтоновыми циклами, оказываются трудпорешаемыми, так называемыми переборными задачами. В этой главе па примере задачиотыскания наибольшего независимого множества вершин рассматриваются подходы к программному решению таких задач. К числу переборных задач относитсяи задача раскрашивания графов, которая имеет много приложений в программировании. С раскраской связана задача об укладывании графа па заданнойповерхности, имеющая приложения в электронике.Таким образом, в этой заключительной главе рассматриваются некоторые известные задачи на графах и указываются связи между ними. В частности, приводятсярешеиия тех исторических задач, с которых мы начали изложение теории графовв главе 7.10.1. Фундаментальные циклы и разрезыПервый раздел главы посвящёп установлению структуры множеств циклов иразрезов в графе, с точки зрения векторных пространств.10.1.1.
Циклы и разрезыЦикл может входить только в одну компоненту связности графа G(V, Е), а внесвязном графе понятие разреза является вырожденным, поэтому без ограничения общности в этом разделе граф G(V,E) считается связным.Цикл пе может содержать одно ребро более одного раза, поэтому в этом разделецикл рассматривается как множество рёбер. В этой связи можно дать эквивалентное определение простого цикла: простым называется цикл, никакое собственноеподмножество которого циклом не является.334Глава 10.
Циклы, независимость и раскраскаНапомним, что разрезом связного графа называется множество рёбер, удалениекоторых делает граф несвязным. Заметим, что любое разбиение множества вершин V на два непустых подмножества V\ Ф 0 и V2 ф 0, V\ П V2 = 0 , V\ U V2 = V,определяет разрез -S1: = {(г?1,г>г) € Е \ v\ е Vi к v2 е V2}, поскольку правильныеподграфы G1 и G2, определяемые подмножествами V\ и V2 соответственно, являются, очевидно, компонентами связности графа G - S.
Заметим далее, чтомножества V\ и V2 определяют друг друга: Vi = V \V2, V2 = V \ Vi, поэтомудостаточно задать только одно из них. Естественно ввести обозначениеVC7 С V ( и = f V \ £ / ) .Введём обозначение E(Vi, V2) для множества рёбер, соединяющих два дизъюнктных непустых подмножества вершин графа G(V,E):E(V.ь V2) = f { К v2) е E |€ Vi к v2 e V2} ,где Vi С V, V2 С V, Vi Ф 0 , V2 Ф 0 , Vi П V2 = 0 . Заметим, что E(Vi, V2) == E(V2,Vl).Разрез связного графа G(V, E), определяемый непустым подмножеством U множества вершин V, называется правильным разрезом и обозначается S(U):S(U) =f {{vltv2)e E \ ы euк v2 eu}=E(u,u).Правильный разрез не содержит «лишних» рёбер, то есть таких рёбер, включениеили исключение которых не меняет компонент связности, получаемых при удалении рёбер разреза.
Ясно, что всякий разрез содержит некоторый правильныйразрез.Л Е М М А Симметрическая разность двух различных правильных разрезов, определяемых множествами V\ uV2, является правильным разрезом, определяемым симметрической разностью множеств V\ и V2:У\фУ2=^S(Vi) Д S(V2) = S{V1 Д V2).ДОКАЗАТЕЛЬСТВО«Пересечение» правильных разрезов S ( V I ) и S(V 2 ) образуетразбиение множества вершин V на четыре подмножества (рис. 10.1):Vn : = Vi П V2,Vio : = Vi П V^,Vbi : = Vi ПV 0 0 : = VTnT^.В этих обозначенияхS(Vi) = E(VluVoi)И ВД О, Vol) U E(Vn,V<DO) U ВД0, V00),S(V2) = E(VU, Vio) U ВДЬ Vio) U E(V1U Voo) U E(V01, V00),откуда, учитывая, что £(Vio, Voi) = £(Voi, Vio), имеем:S(VI) Д S(V2) = ВДI, VOI) U E(VI0, V00) U E{ViU Vio) U E(V0u V&o).Заметим, чтоVi Д V2 =(Vi п Ц ) и (Vi n V2) = Vio и Vol,Vi Д V2 =(Vi П V2) и (TT П V2) = Vn и Voo.10.1.
Фундаментальные циклы и разрезы335Поэтому= ад0, vn) и Вдо, Voo) и адь Vn) и адь и»),и учитывая, что £7(Vi0, Vii) = £(Vn, Ую) и E(\oi, Vii) = J5(Vn, V0i), окончательно имеем S(Vi) A S(V2) = S(VL Д V2).•s{v1д v2)Простым разрезом называется минимальный разрез, то есть такой разрез, никакое собственное подмножество которого разрезом не является. Простой разрезявляется правильным.ЗАМЕЧАНИЕЧем больше в графе циклов, тем труднее его разрезать. В дереве, напротив, каждое ребросамо по себе является разрезом.10.1.2. Фундаментальная система циклови циклический рангПусть T(V,ET) — некоторый остов графа G(V, Е).
Кодеревом T*(V, Е?) остоваТ называется остовный подграф, такой, что Е? = Е \ Ет. (Кодерево не является деревом!) Рёбра кодерева называются хордами остова. По теореме 9.1.2 обосновных свойствах деревьев каждая хорда е е Т* остова Т порождает ровноодин простой цикл, обозначим его Ze. Таким образом, имеем систему простыхцикловZ = {^е}еет*>определяемых выбранным остовом Г, которая называется фундаментальной системой циклов. Циклы фундаментальной системы называются фундаментальными, а количество циклов в (данной) фундаментальной системе называетсяциклическим рангом (или цикломатическим числом) графа G и обозначается m(G).ТЕОРЕМАЛюбой цикл в связном графе G(V, Е) можно представить как симметрическую разность нескольких фундаментальных циклов из системы Z, определяемой произвольным остовом Т.336Глава 10.
Циклы, независимость и раскраскаДОКАЗАТЕЛЬСТВОЕСЛИ В графе G нет циклов, то это дерево, G = T,T* = 0,Z = 0,и утверждение теоремы тривиально. Рассмотрим цикл Z в графе G. Этот циклсодержит хорды е ь . . . , еп £ Т*. (Такие хорды в Z обязательно есть, в противномслучае Z с Т, что невозможно, поскольку Т — дерево.) Докажем индукцией поп, что Z = Z e , Д . . .
Д Zen. База: пусть п = 1, тогда е\ & Т, Z — е\ С Т иZ = Zei, так как если бы Z ф Z e i , то концы е\ были бы соединены в Т двумяцепями, что невозможно по теореме 9.1.2. Пусть (индукционное предположение)Z = Z e i д . . . д Zem для всех циклов Z с числом хорд m < п. Рассмотрим циклZenхордами e i , . .
. , e n е Т* и цикл ZCn (рис. 10.2). Имеем Z ' : = Z Д Zen == (Z - еп) U (Zen - еп) — тоже цикл (возможно, не простой). Но Z' содержиттолько п—1 хорд e i , . . . , е п _ ь По индукционному предположению Z' = Z ei . Д . . .. . . Д ZCn_,. Имеем:Z = Z' Д ZKn = (Z ei Д .
. . Д Zen_,) Д Z en = Z ei Д . . . Д z e n _ 1 д z e n .•СЛЕДСТВИЕКоличество циклов в фундаментальной системе равно числу хордостова: m(G) = q - р + 1.ДОКАЗАТЕЛЬСТВОm(G)= q{T*)= q(G)- q(T)= q - (p - 1) = q - p + 1.•Пример На рис. 10.3 представлена система фундаментальных циклов, определяемых некоторым остовом. Рёбра остова выделены жирными линиями, а соответствующие фундаментальные циклы, их четыре — Z\ = {(г^,^), (^2,^3), (^3,^1)},Z2 = {(v2,v5), (v5,v3), («3,^2)}» Z3 = {(и2, V5), {v5,V6), (V6,V3), {V3,V2)}, Z 4 == {(^2,^4), (г»4, ^5), (^5,1*2)}, — пунктирными контурами.ЗАМЕЧАНИЕСовокупность всевозможных симметрических разностей фундаментальных циклов содержит множеств больше, чем нужно: в неё входят не только все циклы графа G, но инекоторые объединения таких циклов. В частности, симметрическая разность двух (фундаментальных) циклов, которые не имеют общих вершин, снова даёт два этих же цикла.Иногда множество объектов, определяемое всевозможными циклическими разностямифундаментальных циклов, называют множеством циклических векторов.33710.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
