Новиков Ф.А. Дискретная математика для программистов (860615), страница 61
Текст из файла (страница 61)
Связный граф может иметь много остовов.ОТСТУПЛЕНИЕЕсли задать длины рёбер, то можно поставить задачу нахождения кратчайшего остова. Этазадача имеет множество практических интерпретаций. Например, пусть задано множествоаэродромов и нужно определить минимальный (по сумме расстояний) набор авиарейсов,который позволил бы перелететь с любого аэродрома на любой другой. Решением этойзадачи будет кратчайший остов полного графа расстояний между аэродромами.ЗАМЕЧАНИЕСуществует множество различных способов найти какой-то остов графа.
Например, алгоритм поиска в глубину строит остов (по рёбрам возврата). Множество кратчайших путейиз заданной вершины ко всем остальным также образует остов. Однако этот остов можетне быть кратчайшим.Пример На рис. 9.17 показаны диаграммы (слева направо) графа, дерева кратчайших путей из вершины 1 с суммарным весом 5 и два кратчайших остова этогографа.1Д ж о з е ф Бернард Краскал (р. 1928).328Глава 9. ДеревьяРис. 9 . 1 7 . Граф, дерево кратчайших путей и два кратчайших остова9.5.2. Схема алгоритма построения кратчайшего остоваРассмотрим следующую схему алгоритма построения кратчайшего остова. ПустьТ — множество непересекающихся деревьев, являющихся подграфами графа G.Вначале Т состоит из отдельных вершин графа G, в конце Т содержит единственный элемент — кратчайший остов графа G.Алгоритм 9.11 Построение кратчайшего остоваВход: граф G(V,E), заданный матрицей длин рёбер С.Выход: кратчайший остов Т.T: = Vwhile в Т больше одного элемента doвзять любое поддерево из Тнайти к нему ближайшеесоединить эти деревья в Тend whileОБОСНОВАНИЕВозьмём произвольное дерево Т* и выберем ближайшее к немудерево Tj в Т, Ti Г) Tj = 0 .
ПоложимАц:=mind(ti,tj).JtiCTiJjETj'Так как с самого начала все вершины G покрыты деревьями из Т, a Tj выбирается ближайшим к Т^ то Д ^ всегда реализуется на некотором ребре с длиной Cij.Далее индукцией по шагам алгоритма 9.11 покажем, что все рёбра, включенныев деревья из Т, принадлежат кратчайшему остову — SST1. Вначале выбранныхрёбер пет, поэтому их множество включается в кратчайший остов. Пусть теперьвсе рёбра, добавленные в Т, принадлежат SST.
Рассмотрим очередной шаг алгоритма. Пусть на этом шаге добавлено ребро (i,j), соединяющее поддерево Ti споддеревом Tj. Если (i,j) £ SST, то, поскольку SST является деревом и, сталобыть, связен, 3(i*,j*) G SST, соединяющее Ti с остальной частью SST. Тогдаудалим из SST ребро (i*,j*) и добавим ребро (i,j): SST': = SST- (г*, j*) + (г, j).Полученный подграф SST' является остовом, причём более коротким, чем SST,что противоречит выбору SST.•* SST — Shortest Spanning Tree — стандартное обозначение для кратчайшего остова.9.5. Кратчайший остов329ЗАМЕЧАНИЕРазличные способы выбора поддерева для наращивания па первом шаге тела цикла даютразличные конкретные варианты алгоритма построения SST.9.5.3.
Алгоритм КраскалаСледующий алгоритм, известный как алгоритм Краскала, находит кратчайшийостов в связном графе.Алгоритм 9.12 Алгоритм КраскалаВход: список Е рёбер графа G с длинами, упорядоченный в порядке возрастаниядлин.Выход: множество Т рёбер кратчайшего остова.Т: = 0к: = 1 { номер рассматриваемого ребра }for г from 1 to р - 1 dowhile z(T + E[k}) > 0 doк : = к + 1 { пропустить это ребро }end whileТ: = Т + Е[к] { добавить это ребро в SST }к: = к + 1 { и исключить его из рассмотрения }end forД Л Я обоснования алгоритма Краскала достаточно показать, чтовыдерживается схема алгоритма предыдущего подраздела. Действительно, поскольку в множестве рёбер Т нет циклов по построению, это множество сутьсовокупность рёбер некоторого множества деревьев.
Если множество Т содержитболее одного дерева, то существует ребро, при добавлении которого не возникаетцикла — оно соединяет два дерева в Т. Добавляемое ребро — кратчайшее возможное, зиачит, на нём реализуется расстояние между некоторыми деревьями вТ. По построению в конце работы алгоритма множество рёбер Т содержит р— 1элемент, а значит, является искомым остовом.•ОБОСНОВАНИЕЗАМЕЧАНИЕИсследование алгоритма Краскала дало толчок развитию теории жадных алгоритмов,см. 2.6.Семейство всех таких подмножеств множества рёбер графа, которыене содержат циклов, является матроидом.ТЕОРЕМА330Глава 9.
ДеревьяПустое множество рёбер пе содержит циклов и аксиома М\(см. 2.6.1) выполнена. Далее, если множество рёбер не содержит циклов, то любое его подмножество также не содержит циклов, и аксиома М2 выполнена. Пустьтеперь Е' С Е — произвольное множество рёбер, a G' — правильный подграфграфа G, образованный этими рёбрами. Очевидно, что любое максимальное несодержащее циклов подмножество множества Е' является объединением остовов компонент связности графа G' и по теореме 9.1.2 содержит p(G') - k(G')элементов.
Таким образом, все максимальные не содержащие циклов подмножества произвольного множества рёбер содержат одинаковое количество элементов, и по теореме 2.6.2 семейство ациклических подмножеств рёбер образуетматроид.•ДОКАЗАТЕЛЬСТВОТаким образом, алгоритм Краскала как жадный алгоритм (см. 2.6.4), применённый к матроиду, находит ациклическое подмножество рёбер наименьшего веса.По построению алгоритма (основной цикл до р — 1) это подмножество рёбердревочисленно, а значит, является кратчайшим остовом.9.5.4. Алгоритм ПримаВ алгоритме Прима 1 кратчайший остов порождается в процессе разрастания одного дерева, к которому присоединяются одиночные вершины. При этом длякаждой вершины v, кроме начальной, используются две пометки: a[v] — этоближайшая к v вершина, уже включённая в остов, a fl[v] — это длина ребра,соединяющего v с остовом.
Если вершину v ещё нельзя соединить с остовомодним ребром, то а[г>]: = 0, @[v]: = оо.Алгоритм 9.13 Алгоритм ПримаВход: граф G(V,E), заданный матрицей длин рёбер С.Выход: множество Т рёбер кратчайшего остова,select и е V { выбираем произвольную вершину }S:={u} { S — множество вершин, включённых в кратчайший остов }Т : — 0 { Т — множество рёбер, включённых в кратчайший остов }for v £ V - и doif v & Г (и) thena[v]: = u {и — ближайшая вершина остова }f3[v\: = С [и, v] { С[и, v] — длина соответствующего ребра }elsea[v]: = 0 { ближайшая вершина остова неизвестна }P[v]: = оо { и расстояние также неизвестно }end ifend forfor i from 1 to p - 1 do1Роберт Клей Прим (p. 1921).Комментарии331х : = оо { начальное значение для поиска ближайшей вершины }for V е V \ S doif j3[v] < х thenw: = v { нашли более близкую вершину }x:=(3[v] { и расстояние до неё }end ifend forS: = S + w { добавляем найденную вершину в остов }Т: = Т + (a[w],w) { добавляем найденное ребро в остов }for v е Г(ги) doif v S thenif 0[v] > C[v, w] thena[v}\ = w { изменяем ближайшую вершину остова }0[v]: = C[v, w] {и длину ведущего к ней ребра }end ifend ifend forend forАлгоритм Прима буквально следует схеме алгоритма 9.11.
В качестве первого из соединяемых деревьев используется одно и то же разрастающеесядерево Т, а в качестве второго — ближайшая одиночная вершина.•ОБОСНОВАНИЕОТСТУПЛЕНИЕЗадача о нахождении кратчайшего остова принадлежит к числу немногих задач теорииграфов, которые можно считать полностью решёнными. Между тем, если измеиить условия задачи, на первый взгляд даже незначительно, то она оказывается значительно болеетрудной. Рассмотрим следующую задачу.
Пусть задано множество городов на плоскости инужно определить минимальный (по сумме расстояний) набор железнодорожных линий,который позволил бы переехать из любого города в любой другой. Кратчайший остов полного графа расстояний между городами не будет являться решением этой (практически,очевидно, очень важной) задачи, известной как задача Штейнера. В задаче Штейнера допускается введение дополнительных вершин, называемых точками Штейнера. Нарис. 9.18 приведены, соответственно, диаграммы кратчайшего остова, наивного «решения» задачи Штейнера и правильного решения для случая, когда города расположены ввершинах квадрата. Задача Штейнера на плоскости хорошо изучена, в частности, известномного важных свойств точного решения.
Например, известно, что каждая точка Штейнераимеет степень 3 и отрезки в ней встречаются под углом 120°. Тем не менее до сих порнеизвестно достаточно эффективных алгоритмов решения данной задачи, и она остаётсяпредметом интенсивных исследований.КомментарииМатериал этой главы затрагивает вопросы, которые очень часто возникают впрактическом программировании. Поэтому различные сведения о деревьях можно найти не только в специальных учебниках по теории графов, но и в книгах по332Глава 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
