![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Принципы, положенные в основу алгоритмов построения дерева MST
Задача определения дерева MST относится к одной из тех, которым в этой книге уделяется наибольшее внимание. Основные подходы к ее решению были получены задолго до разработки современных структур данных и современных технологий анализа рабочих характеристик алгоритмов, еще в те времена, когда определение дерева MST конкретного графа, содержавшего, скажем, тысячу ребер, представляло собой невыполнимую задачу. Как будет показано далее, некоторые новые алгоритмы определения MST отличаются от старых, главным образом, способами использования и реализации современных алгоритмов и структур данных в рамках базовых задач, которые (в совокупности с мощью современных компьютеров) дают возможность вычислять деревья MST, состоящие из миллионов и даже миллиардов ребер. Одно из определяющих свойств дерева (см. раздел 5.4) заключается в том, что добавление ребра в дерево порождает уникальный цикл. Это свойство является определяющим для доказательства двух фундаментальных свойств деревьев MST, к изучению которых мы сейчас перейдем. Все алгоритмы, с которыми мы сталкиваемся, основаны на одном или двух таких свойствах. Первое из этих свойств, на которое мы далее будем ссылаться как на свойство сечения, относится к идентификации ребер, которые должны входить в дерево MST заданного графа. Несколько основных термином из теории графов, определение которых мы дадим ниже, позволяют получить компактную формулировку этого свойства, что мы и сделаем. Часть 5. Алгоритмы на графах
Иногда мы описываем сечение графа путем описания некоторого множества вершин графа, подразумевая под этим, что сечение содержит само это множество и его дополнение. По существу, мы используем сечения графа в тех случаях, когда оба указанных выше множества не пусты — в противном случае пересекающие ребра отсутствуют. Свойство 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. Алгоритмы на графах
Свойство цикличности служит также основой условия оптимальности, которое характерно для деревьев MST: из него следует, что каждое ребро любого графа, не содержащегося в заданном MST, есть максимальное ребро цикла, который оно образует с ребрами MST. Свойства сечения и цикличности образуют основу для классических алгоритмов, которые будут исследоваться применительно к задаче определения дерева MST. Мы будем рассматривать ребра по одному за раз, используя сечения с целью проверки их пригодности для использования в качестве ребер дерева MST, или свойство цикличности с целью определения возможности их отбрасывания за ненадобностью. Эти алгоритмы различаются по их способности эффективно идентифицировать сечения и циклы. Первый подход к поиску дерева MST, который мы намерены исследовать во всех подробностях, заключается в постепенном построении MST, добавляя одно ребро за раз: мы начинаем построение с произвольной вершины и рассматриваем ее как дерево MST, состоящее из одной вершины, затем добавляем к нему V— 1 вершин, при этом каждый раз выбираем минимальное ребро, которое соединяет вершину, уже включенную в дерево MST, с вершиной, которая еще не содержится в MST. Этот метод известен как алгоритм Прима (Prim's algorithm), и он будет рассматриваться в разделе 20.3. Свойство 20.3. Алгоритм Прима вычисляет дерево MST любого связного графа. Доказательство: В соответствии с подробным описанием, изложенным в разделе 20.2, рассматриваемый метод есть обобщенный метод поиска на графе. Непосредственно из свойства 18.12 вытекает тот факт, что выбранные ребра образуют остовное дерево. Чтобы показать, что они представляют собой дерево MST, применим механизм сечения с использованием для этих целей вершин, входящих в MST, в качестве первого подмножества и вершин, не входящих в MST, в качестве второго подмножества. ■ Еще один подход к вычислению дерева MST предусматривает многократное применение свойства цикличности: мы добавляем ребра по одному за раз во мнимое дерево MST, с удалением максимального ребра из цикла, если таковой был образован (см. упражнения 20.33 и 20.71). Этому методу уделяется меньше внимание, чем другим рассмотренным нами алгоритмам, в силу трудностей, связанных с поддержкой структуры данных, которые обеспечивают реализацию операции " удалить самое длинное ребро цикла". Второй подход отыскания дерева MST, который будет изучаться во всех подробностях, предусматривает обработку ребер в порядке возрастания их длины (первым обрабатывается наиболее короткое) с добавлением в MST каждого ребра, которое не образует цикла с ребрами, включенными в MST раньше; при этом процесс останавливается после того, как будут добавлены V— 1 ребер. Этот метод известен как алгоритм Крускала (Kruskal's algorithm), который подробно рассматривается в разделе 20.4. Глава 20, Минимальные остовные деревья
Третий подход к построению дерева 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. Алгоритмы на графах
> 20.26. Присвойте метки, соответственно, от 0 до 5 следующим точкам на плоскости: (1, 3) (2, 1) (6, 5) (3, 4) (3, 7) (5, 3). Принимая длину ребра в качестве его веса, найдите дерево MST для графа, заданного множеством ребер 1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3. 20.27. Предположим, что граф образуется ребрами с различными весами. Должно ли 20.28. Ответьте на вопрос упражнений 20.27 применительно к самому длинному ребру 20.29. Приведите встречный пример, показывающий, почему не гарантирует нахож 20.30. Предположим, что все ребра заданного графа обладают различными весами. 20.31. Пусть задано дерево MST графа G, предположим, что из графа G удалено не 20.32. Постройте дерево MST, которое получается после многократного применения 20.33. Докажите, что многократное применение свойства цикла приводит к постро 20.34. Опишите, как адаптировать алгоритмы из данного раздела (при необходимос
|