Дискретная математика (998286), страница 46
Текст из файла (страница 46)
Положим Ь;,В: = пйп йгсо 81). И етос, етв Так как с самого начала все вершины С покрыты деревьями из Т, то Ь;, всегда реализуется на некотором ребре с длиной с; . Далее индукцией по шагам алгоритма 9.6 покажем, что все ребра, включенные в Т, принадлежат кратчайшему остову — ББТ ".
Вначале выбранных ребер нет, поэтому их множество включается в кратчайший остов. Пусть теперь все ребра, добавленные в Т, принадлежат ББТ. Рассмотрим очередной шаг алгоритма. Пусть на этом шаге добавлено ребро (1, л), соединяющее поддерево Т; с поддеревом Т,. Если (с, л) ф ББТ, то, поскольку ББТ является деревом и, стало быть, связен, 3(в*,у*) Е ББТ, соединяющее Т, с остальной частью ББТ. Тогда удалим нз ББТ ребро (с', л*) и добавим ребро 1с, т): $$Т': = $$Т вЂ”,(ь'*, у*) + (с, у).
Полученный подграф $$Т' является остовом, причем более коротким, чем ББТ, что противоречит выбору ББТ. П ЗАМЕЧАНИЕ Различные способы выбора полдерева для наращивания на первом влаге тела цикла лают различные конкретные варианты алгоритма построения ББТ. 9.5.3.
Алгоритм Краскала Следующий жадный алгоритм, известный как алгоритм Красково, находит крат- чайший остов в связном графе. Алгоритм 9.7. Алгоритм Краскала Вход: список Е ребер графа С с длинами. Выход: множество Т ребер кратчайшего остова. У:=ш упорялочить Е в порядке возрастания длин Ь: = ! ( номер рассматриваемого ребра ) с ззт — зьпгссвс Все!своп тгсс — стандартное пбозначсяис лвв кратчайшего остова. 288 Главе 9. Деревья бог т тгош 1 Го р — 1 т(о ттнйе добавление ребра Е(Ь) образует цикл в Т бо Ь: = Ь + 1 ( пропустить это ребро ) епб чЬйе Т: = Т О (Е(Щ ( добавить ато ребро в о ЯТ ) епо Еог ОБОСНОВАНИЕ Заметим, что множество подмножеств множества ребер, не содержащих циклов, образует матроид (см. раздел 2.7). Действительно, если множество ребер не содержит цикла, то любое подмножество также не содержит цикла.
Пусть теперь Е' с Š— произвольное множество ребер, а С' — правильный подграф графа С, определяемый этими ребрами. Очевидно, что любое максимальное не содержащее циклов подмножество множества Я' является объединением остовов компонент связности С' и по теореме об основных свойствах деревьев (см. подраздел 9.1.2) содержит р(С') — 1с(С') элементов.
Таким образом, то теореме подраздела 2.7.2 множество ациклических подмножеств ребер образует матронд. Далее, рассматриваемый алгоритм, как жадный алгоритм, находит кратчайшее ациклическое подмножество множества ребер. По построению оно содержит р — 1 элемент, а значит, является искомым остовом. С) ОТСТУПЛ Е НИ Е Задача о нахождеяни кратчайшего остова принадлежит к числу немногих задач теории графов, которые можно считать полностью решенными. Между тем, если изменить условия задачи, на первый взгляд даже незначительно, то опа оказывается значительно более трудной. Рассмотрим следующую задачу.
Пусть задано множество городов на плоскости и нужно определить минимальный (по сумме расстояний) набор железнодорожных линий, который позволил бы переехать нз любого города в любой другой. Кратчайший остов полного графа расстояний между городами не будет являться решением этой (практически, очевидно, очень важной) задачи, известной как задача Штейн«тта.
На рис. 9.15 приведены, соответственно, диаграммы кратчайшего остова, наивного «решения» задачи Штейнера н правильного решения для случая, когда города расположены в вершинах квадрата эт в~ »$ Рис. 9.16. Кратчайший остов, приближенное н точное решение задачи ц1тейнеоа 259 Упражнения Комментарии Материал этой главы затрагивает вопросы, которые очень часто возникают в практическом программировании.
Поэтому различные сведения о деревьях можно найти не только в специальных учебниках по теории графов, но и в книгах по программированию и конструированию эффективных алгоритмов. В качестве рекомендуемых источников назовем [1, 8, 13]. В частности, алгоритмы операций с деревом сортировки описаны в [8], откуда они заимствованы с некоторыми дополнительными уточнениями способов реализации. В книге [13] можно найти краткие и доступные описания алгоритмов работы с АВЛ-деревьями, которые здесь опущены за недостатком места.
Упражнения 9.1. Нарисовать диаграммы всех деревьев с 7 вершинами. 9.2. Допустим, что в ордереве все узлы, кроме листьев, имеют одну и ту же полустепень исхода и. В этом случае говорят, что дерево имеет постоянную ширину ветвления и. Оценить высоту й ордерева, которое имеет р узлов и постоянную ширину ветвления и. 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. Доказать, что полный граф Кр имеет р1" з1 остовов (это утверждение известно как формула Кали). ГЛАВА 10 Циклы После рассмотрения ациклических связных графов, то есть деревьев, естественно перейти к рассмотрению графов с циклами.
10.1. Фундаментальные циклы и разрезы Первый раздел главы посвящен установлению связи векторных пространств со структурой циклов и разрезов в графе. 10.1.1. Циклы и коциклы Цикл может входить только в одну компоненту связности графа, поэтому далее без ограничения общности граф считается связным. Цикл (простой) рассматривается как множество ребер. Разрезом связного графа называется множество ребер, удаление которых делает граф несвязным. Простым разрезом называется минимальный разрез, то есть такой, никакое собственное подмножество которого разрезом не является. В этом параграфе рассматриваются только простые циклы и разрезы, далее слово епростые» опускается.
Между циклами и разрезами существует определенная двойственность, поэтому разрезы иногда называют коциклами. ЗАМЕЧАНИЕ Поскольку рассматриваются только простые циклы в коцнклы. онн могут считаться имен- но множествамн, а не последовательностями ребер. ОТСТУПЛЕНИЕ Чем больше в графе циклов, тем труднее его разрезать. В дереве, напротив, каждое ребро само по себе является разрезом. 261 10Л.
Фундаментальные циклы и разрезы 10.1.2. Независимые множества циклов и коциклов Рассмотрим операцию гн сложения по модулю 2 или симметрической разности над множествами ребер: Мг Ю Мг . = (е ~ (е Е М, гг е ф Мг) Ч (е ф Мг й е Е Мг)) . Множество М называется зависимым или линейной комбинацией множеств (Мг)",, если и М= ®Мо г=г Множество циклов (Ег)",, называется независимым, если ни один из циклов Ег не является линейной комбинацией остальных. Множество разрезов (Яг)," г называется независимым, если ни один из разрезов Яг не является линейной комбинацией остальных. ЗАМЕЧАНИ Е— Множество подмножеств ребер данного графа образует векторное пространство над двоичной арифметикой. Действительно, гв — ассоциативная и коммутативная операция.
Далее М т о = ю чг М = М и каждый элемент является своим обратным: М Е М = о. Таким образом, подмножества ребер образуют абелеау группу относительно симметричной разности. Далее определим операцию умножения вектора на скаляр: ОМ: = Ы, 1М: = М. Легко видеть, что аксиомы векторного пространства выполнены. Введенные здесь понятия линейной комбинации, зависимости н независимости являются частными случаями одноименных понятий нз разделов 2.5 и 2.7. 10.1.3.
Циклический и коциклический ранг ТЕОРЕМА Если С вЂ” связный граф, то т(~) =а-р+1, т'(с) = р — 1 Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Пиклы фундаментальной системы называются фундаментальными, а количество циклов в (данной) фундаментальной системе называется циклическим рангом, или цикломатическим числом, графа С и обозначается т(С). Максимальное независимое множество коциклов (разрезов) (или минимальное множество коциклов, от которых зависят все остальные) называется фундаментальной системой коцикгов (разрезов). Коциклы (разрезы) фундаментальной системы называются фундаментальными, а количество коциклов в (данной) фундаментальной системе называется коцикличвским рангом, или ющикломатичвским числом, графа С и обозначается т" (гг).
Пусть Т(Ъ; Ет) — остов графа С(У, Т). Кодеревом Т*(Ъ; Е') остова Т называется останный подграф, такой что Ет' = Е 1 Ет. (Кодерево не является деревами) Ребра кодерева называются хордами остова. гег Глава 1О. Циклы доказательство Рассмотрим некоторый остов Т графа С. По теореме 9.1.2 об основных свойствах деревьев каждая хорда е е Т' остова Т порождает ровно один простой цикл з,. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро (хорду е). Покажем, что любой цикл графа С зависит от (Е,),ет.. Заметим, что любой элемент фундаментальной системы зависит от фундаментальной системы, поэтому далее элементы фундаментальной системы не рассматриваем, то есть Е ф Е,. Пусть теперь некоторый цикл Е содержит ребра ем...,еь е Т".
Такие ребра в Е обязательно есть, в противном случае Е с Т, что невозможно, так как Т— дерево. Докажем индукцией цо к, что Е= Е., Ю . Ю Е,„. База: пусть /с = 1, тогда е, К Т, Е~(е1 ) с Т и Е = Ееы так как если бы Е ф Еаы то концы ег были бы соединены в Т двумя цепями, что невозможно по теореме 9.1.2. Пусть (индукционное предположение) Е = Е„Ю... Ю Е,„лля всех циклов Е с числом хорд т < к. Рассмотрим цикл Е с й хордами ем ..,, еь е Т*.
Рассмотрим Е.„. Имеем Е'. =(Е1(еь))О(Е„\(еь)) — тоже цикл (возможно; не простой). Но Е' содержит только й — 1 хорду е„..., еь ь По индукционному предположению Е' = Е„19 . щ Е,„,. Добавим к этому циклу Е,„. Имеем: Е' 9 Е,„= (Е~(еь)) 0 ((Е„\(еь)) 9 Е,„) = (Е~(еь)) 0 (еь) = Е. Таким образом, (Е,),ет. является фундаментальной системой циклов.
Поскольку все фундаментальные системы содержат одинаковое количество элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом Т. Пусть теперь е е Т. Определим разрез Я, следующим образом. Ребро е — мост в дереве Т. Следовательно, удаление ребра е разбивает множество вершин У на два подмножества У1 и Ую так что У~ С У, Уз С У, Уг 0 Уз = У, У1 П Уз = 1»1. Включим в разрез Я, ребро е и все ребра графа С, которые соединяют вершины множества У1 с вершинами множества Уз. Тогда Я, — это разрез, потому что правильные подграфы, определяемые У1 и Ую являются компонентами связности С вЂ” Я,. Разрез Я, — простой, потому что, если есть ребро, соединяющее У1 и $'з, то граф связен.
Аналогично можно показать, что (Я,),ет является фундаментальной системой разрезов. Действительно, любой разрез Я содержит хотя бы одно ребро из Т, так как Т вЂ” связный остовной подграф. Разрезы (Я,),ет независимы, так как каждый содержит уникальное ребро е. Любой разрез Я зависит от (ее),ет, Ю 8», Далее имеем гп (С) ~(8 ')ест~ 11Ет~ — р 1 и ест еп(С) КЕ»)еет ! (Ет) 1Е~ ~Ет~ Ч (Р 1) = е р+ 1 263 1Одс Эйлероэы циклы 10.2.
Эйлеровы циклы Здесь приведено исчерпывающее решение задачи о Кенигсбергских мостах (см. подраздел 7.1.1), приведшей к исторически первой успешной попытке развития теории графов как самостоятельного предмета. 10.2.1. Эйлеровы графы Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
