XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

Компонентами ориентированного дерева являются его подграфы, порожденные множеством вершин, расположенных на некотором пути из корня в лист. Остовным лесом (деревом) неориентированного (ориентированного) графа называют любой его остовный подграф, являющийся лесом (деревом).

Теорема 5.3. У всякого неориентированного графа существует максимальный остовный лес. М Поскольку неориентированный лес — зто произвольный ациклический граф, то достаточно показать, что всякий неориентированный граф содержит максимальный остовный ациклический подграф.

Рассмотрим произвольный неориентированный граф Се = = (У, Е). Если он ациклический, то утверждение очевидно. В противном случае в нем есть хотя бы один цикл. Выберем один ю циклов графа и обозначим его С1. Удалим ю цикла С1 какое-нибудь ребро. Обозначим его е1. Так как цикл— зто простая цепь, то удаление ребра е1 приводит к подграфу С1 = (г', Е1(е11) графа Се, в котором будет по крайней мере одним циклом меньше, чем в графе Се. В то же время любые две вершины, соединенные цепью в исходном графе, будут соединены цепью и в подграфе С1.

Если граф С1 ациклический, то он и будет искомым максимальным остовным лесом исходного графа, так как возвращение удаленного ре. бра е1 приведет к появлению цикла. Если же граф С1 имеет циклы, то поступим с ним точно так же, как с графом Се, а именно, выбрав какой-нибудь его цикл Сз, удалим из него одно ребро — обозначим его ег. В силу конечности множеств ребер исходного графа через конечное число п > 1 шагов, на каждом из которых удаляется ровно одно ребро некоторого 305 5.3.

Деревья цикла графа С, получим некоторый его ациклический подграф С„= (У, Т), где Т = Е 1 (е~,..., е„), причем подграф С„~ = = (У, Е 1(ем ..., е„~)) содержит цикл, проходящий по ребру е„. Покажем, что добавление к множеству ребер Т хотя бы одного ребра из ранее удаленных, т.е. любого ребра вз множества (ем ..., е„), приведет к появлению цикла. Действительно, на каждом шаге описанной выше процедуры происходит удаление нового цикла графа Се, т.е. все циклы См Сз, ..., С„попарно различны. Для каждого 1 = 1, и рассмотрим два случая: 1) цикл С; содержит только одно из удаленных ребер, а именно ребро е;; 2) цикл С; содержит не менее двух удаленных ребер, т.е. вместе с ребром е; он содержит по крайней мере еще одно ребро е Е (еь...,е„). Очевидно, что в первом случае добавление ребра е; к множеству ребер Т приведет к появлению цикла, а именно цикла С;.

Рассмотрим второй случай. Для простоты будем считать, что есть только одно ребро е1, отличное от ребра е;, которое содержится в цикле С, (случай нескольких таких ребер анализируется аналогично). Так как ребро е. содержится в некотором цикле С, отличном от С;, то, добавляя ребро е; к множеству ребер Т, все равно получим цикл (рис. 5.18). Действительно, если ребро е; не содержится в цикле С, то, как видно на рис.

5.18, концы ребра е; соединены цепью, не содержащей этого ребра. Тогда, согласно теореме 5.1, существует простая цепь (не содержащая ребра е;), соединяющая его концы. Добавляя к ней Рис. 5.18 306 5. ТЕОРИЯ ГРАФОВ ребро е;, получим цикл. Воли же ребро е; содержится в цикле С., то удаление этого ребра приведет к исчезновению вместе с циклом С; и цикла Су, что невозможно, так как С; и Су — циклы, удаляемые на разных шагах описанной въппе процедуры (на самом деле можно показать, что в рассматриваемой ситуации ребро еу, а вместе с ним и цикл С, удаляется позже ребра е;). Таким образом, всегда найдется цепь, соединяющая концы ребра е, (и не содержащая этого ребра).

Следовательно, существует и цикл, содержащий ребро е; (но не содержащий ребра е.). Итак, добавляя к подграфу С„= (К Т) произвольное ребро из множества (еь ..., е„), получим цикл. Следовательно, этот подграф и будет искомым максимальным остовным лесом гра- фа С. ь Утверждение теоремы сохраняет силу и для ориентированных графов.

Доказательство в этом случае будет несколько более сложным, и мы его не приводим. Далее в этой главе мы опишем некоторые способы нахождения множества циклов неориентированного графа и способы построения максимальных остоиных лесов. Эти задачи решаются на основе приведенных ниже алгритмов поиска в глубину. 5.4. Остовное дерево наименьшего веса Следующая задача известна в теории графов под названием задачи Штебнерш на шюскости заданы и точек; нужно соединить их отрезками прямых таким образом, чтобы суммарная длина отрезков была наименьшей. В процессе поиска решения разрешено вводить новые точки; „длина" отрезка, соединяющего две заданные точки, не обязательно понимается буквально геометрически — это может быть некоторая количественная оценка „цены" прохождения из точки в точку по какой-то ломаной линии.

5.4. Остоакое дерево папмепашего кеса 307 Можно дать следующую графовую интерпретацию задачи Штейнера. Дан меорпемтиироеамиый граФ Со = (Уш О) без ребер. Требуетсл найти неориентированый граф С = (У, Т) со специальными свойствами. Мы предполагаем, что каждому ребру любого неориентированного графа, получаемого в процессе решения задачи, можно сопоставить неотрицательное число, называемое весом этого ребра. При этом, во-первых, искомый граф С должен быть кеориеюиироеаммььк деревом, во-вторых, его множество вершин должно включать множество вершин исходного графа, т.е.

Уо С У, и, в-третьих, сумма весов его ребер должна быть наименьшей. Требование, чтобы искомый граф с4 был неориентированным деревом, вызвано тем, что в нем любую пару вершин должна соединять единственнал Пень, так как в противном случае граф не будет иметь наименьшую сумму весов.

Действительно, если существуют хотя бы две цепи, соединяющие какую-то пару вершин, то выбирается та, сумма весов ребер которой меньше. Если же предположить, что в рассматриваемой ситуации имеются хотя бы две цепи с одинаковым весом, то все равно для оптимального решения выбирается какая-то одна цепь (и тогда оптимальное решение не единственно). Эффективных алгоритмов', дающих точное решение задачи Штейнера, не существует. Однако известны эффективные алгоритмы, находящие некоторые приближения точного решения. Одно из таких решений дает плгормпьы Хросыала. Неориентироваиный (ориентированный) граф, у которого каждому ребру (дуге) сопоставлено некоторое действительное число, называют взвешенным или раэдееченным графом.

Это число называют весом или деепзыоб ребра (дуги). Как ' Алгоритм счптают зффектлпемым, если слозсеосшь ааеорешма выражаетса фупкцпей, ограниченной сверху некоторым полкпомом от параметра, характеризующего „объем" ксходаых дапкых. Даа задачи Штайнера зтпм параметром еаакетск число аершик графа бе. 308 Л. ТЕОРИЯ ГРАФОВ правило, мы рассматриваем граф с натуральными метками ребер (дуг). Алгоритм Краскала вычисляет для заданного взвешенного неориентированного графа С осшовное дерево с наименьшей суммой весов ребер — осшовное дерево наименьшеео веса. Существенное отличие только что сформулированной задачи от задачи Штейнера (в ее графовой постановке) состоит в том, что в новой задаче множество вершин при поиске остовного дерева наименьшего веса не меняется.

Поэтому алгоритм Краскзла и дает лишь некоторое приближение решения задачи Штейнера. При описании алгоритма будем использовать способ хранения данных, называемый очередью. Элементы данных в очереди упорядочиваются по времени поступления. Элементы можно добавлять в очередь и извлекать из очереди. В каждый момент времени доступен только один элемент, который был помещен в очередь раньше других, — „голова" очереди.

При добавлении новый элемент помещается в „хвост" очереди, т.е. работа ведется по обычному для очереди правилу — „первым пришел — первым вышел". Чтобы извлечь из очереди некоторый элемент, не доступный в текущий момент, надо извлечь все ранее поступившие элементы, начиная с „головы" очереди.

Рассмотрим алгоритм нахождения остовного дерева наименьшего веса (алгоритм Краскзла). Пусть дан связный неориентированный граф 0 = (У, Е) с числовыми неотрицательными весами ребер. Вес ребра е обозначим ~р(е). В результате работы алгоритма получим остовное дерево Т = (К Н) графа С, такое, что сумма ), ~р(е) является наиеен меньшей. Отсортируем все ребра исходного графа по возрастанию весов и сформируем иэ них очередь так, чтобы в „голове" очереди находилось ребро с наименьшим весом, а в „хвосте"— с наибольшим и веса ребер не убывали от „головы" очереди к „хвосту".

о.4. Остоввое дерево иаимеиыпего веса Метод состоит в „сшивании" искомого дерева из компоневпд остовного леса. Первоначально осдповвмй лес представляет собой множество юолированных вершин исходного графа, т.е. его множество ребер пусто. На первом шаге из очереди извлекается ребро наименьшего веса и добавляется к множеству ребер исходного дерева.

На последующих шагах алгоритма из очереди извлекается по одному ребру. Если это ребро соединяет вершины, принадлежащие разным компонентам текущего остовного леса, то оно добавляется к текущему множеству ребер искомого дерева, а указанные компоненты сливаются в одну. Иначе ребро отбрасывается. Процесс повторяется до тех пор, пока число компонент остовного леса не окажется равным 1. Можно показать, что эта компонента и будет искомым остоиным деревом наименьшего веса. Переходим к формальному описанию алгоритма. Алгоритм Краскала 1. Множество ребер Н искомого остовного дерева полагаем пустым (Н = И). 2. Формируем множество 78 = Цддд), ..., (е„Ц, элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса.

Каждая такая компонента состоит из единственной вершины. 3. Сортируем множество ребер Е исходного графа по возрастанию весов и формируем очередь Я, элементами которой являются ребра графа С. 4. Если множество Уя содержит более одного элемента (т.е. остовный лес состоит из нескольких компонент) и очередь Я не пуста, переходим на шаг 5, если иначе — на шаг Т.

5. Извлекаем из очереди Я ребро е. Если ковддм ребра е принадлежат различным множествам вершин иди 1~1 из Уя,то переходим на шаг 6, если иначе, то отбрасываем ювлеченное ребро и возвращаемся на шаг 4. З1О 5. ТЕОРИЯ ГРАФОВ б. Объединяем множества вершин У и У. (полагая Ж = = У. О У1), удаляем множества У и Уу из множества Уя и добавляем в Уя множество И~.

Добавляем ребро е в множество Н. Возвращаемся на шаг 4. Т. Прекращаем работу. Множество Н есть множество ребер полученного остовного дерева. Доказательство корректности алгоритма Краснела, т.е. доказательство того факта, что выдаваемое алгоритмом остовное дерево действительно является остовным деревом навменьшего веса, мы не приводим. На рис. 5.19, а-д для неориентированного графа показана последовательность построения остовного дерева наименьшего веса. Заметим, что результат работы алгоритма в общем случае зависит от порядка следования ребер одинакового веса в очереди.

Характеристики

Список файлов книги