Принципы, положенные в основу алгоритмов построения дерева MST

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

Одно из определяющих свойств дерева (см. раздел 5.4) заключается в том, что добав­ление ребра в дерево порождает уникальный цикл. Это свойство является определяющим для доказательства двух фундаментальных свойств деревьев MST, к изучению которых мы сейчас перейдем. Все алгоритмы, с которыми мы сталкиваемся, основаны на одном или двух таких свойствах.

Первое из этих свойств, на которое мы далее будем ссылаться как на свойство сече­ния, относится к идентификации ребер, которые должны входить в дерево MST заданного графа. Несколько основных термином из теории графов, определение которых мы да­дим ниже, позволяют получить компактную формулировку этого свойства, что мы и сде­лаем.

Часть 5. Алгоритмы на графах

Определение 20.2. Сечение (cut) графа есть разделение мно­жества всех вершин графа на два непересекающихся множе­ства. Пересекающее ребро (crossing edge) есть ребро, кото­рое соединяет вершину одного множества с вершиной другого множества.

Иногда мы описываем сечение графа путем описания неко­торого множества вершин графа, подразумевая под этим, что сечение содержит само это множество и его дополнение. По существу, мы используем сечения графа в тех случаях, когда оба указанных выше множества не пусты — в противном слу­чае пересекающие ребра отсутствуют.

Свойство 20.1. (Свойство сечения). При любом сечении гра­фа каждое минимальное пересекающее ребро принадлежит не­которому дереву MST и каждое дерево MST содержит мини­мальное пересекающее ребро.

Доказательство: Проведем доказательство от противного. Предположим, что е — минимальное пересекающее ребро, которое не содержится ни в одном MST, и пусть Т есть не­которое дерево MST, которое не содержит минимального пересекающего ребра е. В любом случае T есть MST, кото­рое не содержит минимального пересекающего ребра е. Те­перь рассмотрим граф, полученный путем добавления реб­ра е в Т. В этом графе имеется цикл, который содержит ребро е, и этот цикл должен, по меньшей мере, содержать еще одно пересекающее ребро, скажем, /, которое имеет вес, равный или больший веса е (поскольку е имеет мини­мальный вес). Мы можем получить остовное дерево равно­го или меньшего веса, если удалим f и добавим е, что про­тиворечит условию минимальности T или предположению, что е не содержится в Т. ■

Если все веса ребер графа различны, он обладает единствен­ным деревом MST; свойство сечения свидетельствует о том, что кратчайшее пересекающее дерево для каждого сечения долж­но быть внутри дерева MST. Если имеют место равные веса ре­бер, мы можем получить несколько минимальных пересекаю­щих ребер. По меньшей мере, одно из них входит в состав любого заданного дерева MST, в то время как другие могут в нем быть, а могут и не быть.

На рис. 20.5 представлены несколько примеров рассмотрен­ного свойства сечения. Обратите внимание на то обстоятель­ство, что в рассматриваемом случае отсутствует требование того, что минимальное ребро должно быть единственным реб­ром MST, которое соединяет два эти множества; в самом деле, для обычных сечений существует несколько ребер, соединяю­щих вершину одного множества с вершиной другого. Если мы

РИСУНОК 20.5. СВОЙСТВО СЕЧЕНИЯ

Приведенные здесь четыре примера служат иллюст­рацией свойства 20.1. Если для одного множе­ства вершин мы выберем серый цвет, а для другого такого множества белый, то самое короткое ребро, соединяющее серую вершину с белой, принадле­жит дереву MST.

Глава 20. Минимальные остовные деревья

уверены в том, что существует одно такое ребро, мы мо­жем разработать алгоритмы типа " разделяй и властвуй", в основу которых положен походящий выбор множеств, но сейчас нас интересуют совершенно другие проблемы.

Мы используем свойство сечения в качестве основы для алгоритмов поиска деревьев MST, оно может также слу­жить условием оптимальности, которое характерно для де­ревьев MST. В частности, из выполнения условия опти­мальности следует, что каждое ребро дерева MST есть минимальное ребро, пересекающее сечение, определен­ный вершинами двух поддеревьев, соединенных этим реб­ром.

Второе свойство, которое мы будем называть свой­ством цикличности, применяется с целью выявления ребер, которые не должны входить в дерево MST графа. Други­ми словами, если мы игнорируем эти ребра, то, тем не ме­нее, не теряем возможности отыскать дерево MST.

Свойство 20.2. (Свойство цикличности). Пусть задан граф G, рассмотрим граф G', который получается в ре­зультате добавления к графу G ребра е. Добавление ребра е в дерево MST графа G и удаление максимального ребра из полученного в результате этой операции цикла дает де­рево МST графа G'.

Доказательство: Если ребро е длиннее всех других ре­бер цикла, то оно не должно содержаться в дереве MST графа G' по свойству 20.1: удаление е из любого такого дерева MST разделит последнее на две части, а е не бу­дет самым коротким ребром, соединяющим вершины каждой из полученных двух частей, поскольку это дол­жно делать какое-то другое ребро цикла. И наоборот, пусть t есть максимальное ребро цикла, построенного в результате добавления ребра е в дерево MST графа G. Удаление ребра t приводит к разбиению исходного де­рева MST на две части, а ребра графа G, соединяющие эти две части, не короче t; следовательно, е является минимальным ребром в G', которое соединяет верши­ны этих двух частей. Подграфы, индуцированные эти­ми двумя подмножествами вершин, идентичны G и G', таким образом, дерево MST для G' состоит из ребра е и из деревьев MST этих двух подмножеств.

В частности, обратите внимание на то, что если ребро е есть максимальное в цикле, то мы показали, что су­ществует дерево MST графа G', которое не содержит е (дерево MST графа G). ■

РИС. 20.6. СВОЙСТВО ЦИКЛА

Добавление ребра 1-3 в граф, показанный на рис. 20.1, приводит к тому, что дерево МST перестает быть таковым (диаграмма вверху). Чтобы найти дерево MST нового графа, мы добавляем новое ребро в МST старого графа, которое порождает цикл (диаграмма в центре). Удаляя самое длинное ребро цикла (4- 7), получаем МST нового графа (внизу). Одним из способов проверить, что остовное дерево минималь­но, заключается в проверке того факта, что каждое ребро, не входящее в это дерево MST, имеет наибольший вес в цикле, который оно образует с тремя другими ребрами. Например, на диаграмме в нижней части рисунка ребро 4-6 имеет максимальный вес в цикле 4.6-7-1-3-4.

Часть 5. Алгоритмы на графах

Глава 20, Минимальные остовные деревья

Свойство 20.4. Алгоритм Крускала вычисляет дерево MST любого связного графа. Доказательство: Мы покажем методом индукции, что этот алгоритм поддерживает лес поддеревьев MST. Если следующее рассматриваемое ребро приводит к образованию цикла, то это дерево представляет собой максимальное дерево цикла (поскольку все другие ребра были выбраны раньше в порядке, установленном сортировкой), так что даже если его проигнорировать, дерево MST все равно сохраняется в соответствии со свойством цикла. Если следующее рассматриваемое ребро не приводит к образованию цикла, примените свойство сечения, воспользовавшись сечением, определенным мно­жеством вершин, связанных с одной из вершин этого ребра ребрами дерева MST (и их дополнениями). Поскольку рассматриваемое ребро не образует цикла, это всего лишь пересекающее ребро, а поскольку мы рассматриваем ребра в порядке, установ­ленном сортировкой, это ребро минимальное и, в силу этого обстоятельства, содер­жится в дереве MST. Основанием для индукции служат V отдельных вершин; как толь­ко мы выберем V— 1 ребер, мы получаем одно дерево (дерево MST). Ни одно из неисследованных ребер не короче никакого ребра MST, и все это вместе образует цикл, следовательно, отбросив все остальных ребра, по свойству цикличности мы по­лучаем дерево MST. ■

Третий подход к построению дерева MST, который мы сейчас рассмотрим подробно, известен как алгоритм Борувки (Boruvka 's algorithm), он подробно исследуется в разделе 20.4. На первом шаге в дерево MST добавляются ребра, которые соединяют каждую вер­шину с ее ближайшим соседом. Если веса ребер различны, этот шаг порождает лес из поддеревьев дерева MST (мы сейчас докажем этот факт и рассмотрим усовершенствова­ние, которое выполняет эту задачу, даже когда в какой-то момент появляются ребра с равными весами). Затем мы добавляем в дерево MST ребра, которые соединяют каждую вершину с ее ближайшим соседом (минимальное ребро, соединяющее вершину одного дерева с вершиной другого), и повторяем этот процесс до тех пор, пока у нас не оста­нется только одно единственное дерево.

Свойство 20.5. Алгоритм Борувки вычисляет дерево MST для любого связного графа.

Сначала предположим, что веса всех ребер различны. В этом случае у каждой вершины имеется единственный ближайший сосед, дерево MST уникально, и мы знаем, что каждое ребро добавлено в соответствие со свойством сечения (это самое короткое реб­ро из тех, что пересекают сечение и соединяют некоторую вершину одного множества со всеми вершинами другого). Поскольку каждая вершина выбрана из уникального дерева MST, циклов в этом случае может и не быть, каждое добавленное ребро соединяет два дерева из леса, образуя при этом дерево больших размеров, и процесс продолжается до тех пор, пока не останется единственное дерево, а именно — дерево MST.

Если же имеются одинаковые ребра, может оказаться, что ближайших соседей будет несколько, и, возможно, появится цикл, когда мы добавляем ребро к ближайшему со­седу (см. рис. 20.7). Другими словами, мы можем включить для некоторой вершины два ребра из множества минимальных пересекающих ребер, в то время как дереву MST принадлежит одно. Во избежание подобных ситуаций, нам необходимо соответ­ствующее правило разрыва связей. Одной из возможностей является выбор на множе­стве минимальных соседей вершины с наименьшим номером. Тогда существование любого цикла приводит к противоречию: если бы v была вершиной с наибольшим но­мером в цикле, то ни одна из вершин, соседних с вершиной v, не выбрала бы ее как ближайшего соседа, в этом случае вершина v должна выбрать только одного из сво­их соседей с минимальным номером, а не двух. ■

Часть 5. Алгоритмы на графах

РИСУНОК 20.7. ЦИКЛЫ АЛГОРИТМА БОРУВКИ

В представленном на рисунке графе имеется четыре вершины, и все четыре показанных здесь ребра имеют одну и ту же длину. Когда мы соединяем каждую вершину с ближайшим соседом, мы должны решить, какое ребро выбрать из множества минимальных ребер. В верхнем примере мы выбираем 1 из вершины О, 2 из 1, 3 из 2 и 0 из 3, что приводит к образованию цикла в предполагаемом дереве MST. Каждое из ребер входит в некоторое дерево MST, но не все их них входят в каждое MST. Чтобы решить эту задачу, принимаем к исполнению правило разрыва связей, как показано в нижней части рисунка: выбираем минимальное ребро, ведущее в вершину с наименьшим индексом. Таким образом, из 1 мы выбираем 0, 0 из 1, 1 из 2 и 0 из 3, что в результате и дает дерево MST. Цикл прерван, поскольку вершина с максимальным индексом 3 не выбиралась ни из одного из ее соседей 2 или 1, а она может выбрать только одного из них (0).

Все эти алгоритмы суть специальные случаи общей парадигмы, которой все еще про­должают пользоваться исследователи, стремящиеся открыть новые алгоритмы построения MST. В частности, мы можем в произвольном порядке применять свойство сечения для вы­бора того или иного ребра в качестве ребра MST или свойство цикла для обоснования отказа включить ребро в MST и продолжать эту процедуру до тех пор, пока станет не­возможным увеличение ни числа принятых, ни числа отвергнутых ребер. На этой стадии при любом делении множества вершин графа на два подмножества имеется ребро MST, соединяющее эти два подмножества (следовательно, применение свойства сечения не приводит к увеличению числа ребер дерева MST), и все циклы графа содержат, по мень­шей мере, одно ребро, не входящее в MST (следовательно, применение свойства сече­ния не приводит к увеличению числа ребер дерева MST). Оба эти свойства в совокупно­сти позволяют вычислить полное дерево MST.

Точнее, все три алгоритма, рассматриваемые нами во всех подробностях, могут быть объединены в один обобщенный алгоритм, выполнение которого мы начинаем с того, что выбираем лес поддеревьев MST, состоящих из одной вершины (и не содержащих ника­ких ребер), выполняем процедуру добавления в дерево MST минимального ребра, соеди­няющего два любых поддерева леса, и повторяем эту процедуру V - 1 раз до тех пор, пока не останется единственное дерево MST. В соответствии со свойством сечения, ни одно из ребер, которое порождает цикл, не нужно подвергать анализу для его включе­ния в дерево MST, поскольку одно из ребер на том или ином предшествующем шаге было минимальным ребром, пересекающим некоторое сечение между поддеревьями MST, каждое из которых содержало свои вершины. По условиям алгоритма Прима, мы увели­чиваем число ребер дерева по одному за один раз; по условиям алгоритмов Крускала и Борувки, мы объединяем деревья некоторого леса.

Согласно описанию, приведенному в этом разделе и в классической литературе, для выполнения указанных выше алгоритмов должны быть разработаны высокоуровневые абстрактные операции, такие как:

■ Отыскание минимального ребра, соединяющего два поддерева.

■ Определение, будет ли образован цикл при включении конкретного ребра.

■ Удаление самого длинного ребра цикла.

Глава 20. Минимальные остовные деревья

Наша задача заключается в разработке алгоритма и структуры данных, которые по­зволили бы эффективно реализовать перечисленные операции. К счастью, эта задача пре­доставляет нам возможность эффективно использовать базовые алгоритмы и структуры данных, которые рассматривались ранее в этой книге.

С алгоритмами на деревьях MST связана долгая и интересная история, которая про­должает развиваться; мы будем к ней возвращаться по мере более близкого знакомства с ними. Наше растущее понимание различных методов реализации базовых абстрактных операций породила некоторую путаницу, окутывающую дату происхождения алгоритма. В самом деле, эти методы были впервые описаны в двадцатых годах прошлого столетия, раньше, чем появились компьютеры в том виде, в каком мы их знаем, и раньше, чем были получены фундаментальные алгоритмы сортировки и другие алгоритмы. Как нам теперь известно, выбор базовых алгоритмов и структур данных оказывает существенное влияние на производительность наших программ, даже когда мы получаем программную реали­зацию базовых схем вычислений. За последние годы исследования в области задач, для решения которых используются деревья MST, концентрируются на таких проблемах ре­ализации, которые допускают использование классических схем. В целях сохранения пос­ледовательности и четкости изложения, мы будем называть базовые подходы употребля­емыми здесь именам их исследователей, хотя абстрактные версии этих алгоритмов были исследованы намного раньше, а современные реализации используют алгоритмы и струк­туры данных, изобретенные намного позже того, когда эти методы были открыты.

До сих пор нерешенной остается задача поиска алгоритма построения деревьев MST за линейное время. Как мы сможем убедиться далее, многие реализации, которые мы бу­дем изучать, выполняются за линейное время в широком диапазоне ситуаций, имеющих место на практике, однако в худшем случае эта зависимость перестает быть линейной. Разработка алгоритмов, которые гарантированно выполняются за линейное время на раз­реженных графах, все еще остается недостижимой целью для исследователей.

Помимо естественного поиска алгоритма решения этой фундаментальной задачи, изу­чение алгоритмов построения дерева MST подчеркивает важность правильного понима­ния базовых рабочих характеристик фундаментальных алгоритмов. По мере того, как программисты продолжают использовать алгоритмы и структуры данных все более вы­сокого уровня абстракции, ситуация такого рода становится все более привычной. По­лученные нами реализации АТД обладают различными рабочими характеристиками — по мере того, как мы используем АТД в качестве компонент алгоритмов решения задач еще более высокого уровня абстракции, возможности умножаются. В самом деле, мы часто используем алгоритмы, которые основаны на использовании деревьев MST и подобных абстракций (что становится возможным благодаря эффективным реализациям, которые будут изучаться далее в этой главе), в качестве средств решения другие задач на еще бо­лее высоком уровне абстракции.

Часть 5. Алгоритмы на графах