Стягивающее дерево
Cтраница 1
 |
Примеры функции CIR ( е, Т. [1] |
Стягивающее дерево Г выделено волнистой линией. [2]
Стягивающее дерево первой глубины [9] для графа G - это стягивающее дерево, порожденное движением из корня через непосредственных потомков в G, причем в качестве очередного узла всегда выбирается потомок последнего узла из списка рассмотренных узлов, который еще обладает потомком вне описка. [3]
 |
Стягивающие деревья, построенные с помощью алгоритма ( а и. [4] |
Каждое стягивающее дерево, построенное указанным алгоритмом, имеет любопытное свойство, которое мы сейчас опишем. [5]
Алгоритм для построения стягивающего дерева с минимальной стоимостью может быть отнесен к типу разбиений. Такие алгоритмы разбивают множество вершин или ребер в соответствии с определенными требованиями. Обычно сначала делается пробное разбиение на несколько классов, а затем последовательная проверка и замена элементов, не удовлетворяющих каким-то ограничениям, до тех пор пока не будут выполнены все условия. [6]
Тесно связана с задачей нахождения стягивающего дерева задача построения фундаментального множества циклов. ГУМ) содержит в точности один цикл1), который мы будем обозначать через Се. [7]
Для доказательства того, что алгоритм 2.3 корректно строит стягивающее дерево произвольного связного графа, достаточно отметить следующие три факта. Таким образом алгоритм строит связный граф. [8]
Стягивающее дерево первой глубины [9] для графа G - это стягивающее дерево, порожденное движением из корня через непосредственных потомков в G, причем в качестве очередного узла всегда выбирается потомок последнего узла из списка рассмотренных узлов, который еще обладает потомком вне описка. [9]
Один ( не очень существенный) недостаток изложенного алгоритма для построения минимального стягивающего дерева состоит в предположении, что с самого начала у нас уже есть по крайней мере одно стягивающее дерево. С другой стороны, если сначала нужно построить стягивающее дерево, то стягивающее дерево с минимальной стоимостью получается почти без дополнительных усилий. Очевидный метод получения какого-либо стягивающего дерева состоит в построении множества его ребер таким образом, чтобы на каждом шаге прибавлялось по одному ребру и проверялось, не образует ли добавленное ребро цикл с ребрами, уже включенными в множество. Какие изменения нужно внести в этот алгоритм для того, чтобы гарантировать получение минимального стягивающего дерева. Ответ на этот вопрос дает следующий алгоритм. [10]
Рассматриваемый алгоритм несколько необычен для комбинаторных алгоритмов: отталкиваясь от произвольно выбранного начального стягивающего дерева, он ведет прямо к стягивающему дереву минимальной стоимости. Когда окажется, что совершить очередную замену невозможно, имеется гарантия, что найдено стягивающее дерево минимальной стоимости. Так происходит потому, что в пространстве стягивающих деревьев отсутствуют локальные минимумы, из которых нужно было бы выбираться для достижения абсолютного минимума. [11]
На рис. 2.11 показано, как при помощи этого алгоритма находятся все три стягивающих дерева полного графа с тремя вершинами. Процедура заканчивается, когда граф распадается на две компоненты или превращается в единственную вершину. G, полученный слиянием вершин. Заметим, что информация о том, какие вершины были слиты, должна сохраняться для того, чтобы по стягивающему дереву было можно восстановить исходный граф. [12]
Предположим, что дерево Т, построенное по алгоритму замены, не является стягивающим деревом с минимальной стоимостью; иначе говоря, оно дает только локальный минимум в том смысле, что невозможно сделать замену, уменьшающую его стоимость. Тогда в множестве стягивающих деревьев с глобальным минимумом стоимости существует дерево U, ближайшее к Г в том смысле, что имеет с ним столько общих ребер, сколько вообще возможно. [13]
Множество ребер, оставшееся после того, как будет невозможно дальнейшее выбрасывание, составляет стягивающее дерево минимальной стоимости. [14]
Способом, аналогичным использованному для алгоритма 2.3, можно доказать, что данный алгоритм корректно строит стягивающее дерево для произвольного связного графа за О ( т) шагов. [15]
Страницы: 1 2 3