2.2. Процедура порождения всех деревьев графа

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

(кликните для просмотра скана)

Маеды [42], Пауля [471, Чена [8] и других [20]. Однако процедурам, опирающимся на элементарные преобразования деревьев, присущ следующий недостаток: для порождения нового дерева необходимо привлекать все найденные ранее деревья. Число деревьев становится столь большим, что для хранения их необходимо (с вычислительной точки зрения) использовать вспомогательные устройства памяти, так как быстродействующая оперативная память для этой цели мала. Поскольку при обращении к вспомогательным устройствам памяти значительно возрастает время вычисления, то любой метод, базирующийся на элементарных преобразованиях деревьев, оказывается неэффективным, если не будут применяться такие преобразования, в которых используется только последнее из полученных остовных деревьев. (См. раздел 2.4.) Очевидно, что наилучшим будет такой алгоритм порождения всех остовов графа, когда список остовов строится без повторений и построенные остовы записываются во вспомогательную память, но в процессе работы алгоритма из этой памяти ничего не берется.

В следующем разделе будет описан один такой алгоритм, основанный на поиске, использующем дерево решений. В работах [10, 9, 43] даются другие алгоритмы, базирующиеся на порождении всех главных квадратных подматриц приведенной матрицы инциденций о которой упоминалось в теореме 1.

2.2.1. Основной метод. Мы приводим описание алгоритма для случая неориентированного графа, но его распространение на ориентированные графы — для порождения всех остовных древовидностей ориентированного графа — совершенно очевидно.

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

Для облегчения манипуляций с поддеревьями в каждом поддереве выделяют произвольным образом корень (некоторую вершину поддерева) и затем рассматривают поддерево уже как

Рис. 7.6. (см. скан) Замена корня из (а) на из (б).

древовидность. Для организации проверки на возможность образования цикла (при добавлении ребра) каждую вершину помечают парой Процедуры выявления циклов, использующие пометки вершин, встречаются у Джонсона [32], Шринивасана и Томпсона [52], Гловера и Клингмана [25]. Первая пометка указывает «корень» поддерева, содержащего вершину Первоначально для всех вершин На некотором шаге два поддерева сращиваются посредством добавления ребра с вершиной из и вершиной из Если на этом шаге «корневая» пометка вершин в «корневая» пометка вершин в (например), то все вершины в должны

«сменить» свои корневые пометки на и два поддерева «сольются» в единственное новое дерево

Вторая пометка приписанная вершине указывает вершину, предшествующую вершине т. е. если дуга рассматриваемого поддерева, то Для корневой вершины дерева такая пометка полагается равной нулю. Для дерева, изображенного на рис.

A. Замена корня дерева

Если корнем дерева является вершина и нужно в качестве корня выбрать новую вершину то такую «замену» на можно осуществить простым обращением ориентации дуг, принадлежащих цепи, идущей от не меняя при этом ориентацию других дуг (см. рис. 7.6). Соответствующие изменения пометок будут таковы.

Изменение пометок «предшествования»

1. Пусть

2. Положить

3. Шаг обновления:

4. Если то перейти к шагу 5, в противном случае положить и перейти к шагу 2.

5. Положить стоп.

Изменение корневых пометок

1. У всех вершин, имеющих корневую пометку заменить ее на пометку

Б. Сращивание двух поддеревьев

Если осуществлено сращивание двух поддеревьев (путем добавления ребра как было описано ранее), то в пометки необходимо внести следующие изменения:

(i) У вершин с корневой пометкой заменить эту пометку на

(ii) Заменить в дереве корень на (так, как было описано выше в пункте А), после чего изменить пометку «предшествования» у вершины

Расщепление дерева на две части

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

в первоначальном дереве ориентировано от пометки в дереве можно оставить прежними, а пометки в дереве должны быть изменены. Если же ребро ориентировано от то можно не менять пометки в дереве но нужно изменить пометки в Предполагая, что пометки меняются в дереве покажем, как надо «восстанавливать» корень в этом дереве.

1. Положить будет корнем дерева

2. Найти все вершины и изменить их корневые пометки на Если таких вершин нет, остановиться.

3. Шаг обновления: вернуться к шагу 2.

Следует отметить, что ни у одной вершины, кроме нового корня пометки предшествования менять не нужно. Заметим также, что число описанных выше шагов 2 и 3, которое необходимо для восстановления корня, равно длине самой длинной цепи в исходящей из вершины

2.2.2. Описание алгоритма. Возьмем произвольную вершину х графа Пусть ее степень равна Перенумеруем ребра, инцидентные этой вершине: Затем перенумеруем остальные ребра графа При порождении деревьев ребра будут перебираться в соответствии с введенной нумерацией.

Шаг 1. Приписать вершинам пометки: где Положить

Шаг 2. Выбрать для исследования некоторое ребро. Например, Если к где число ребер графа, то перейти к При т. е. если «неисследованных» ребер нет, перейти к шагу 5.

(i) Если то это означает, что вершины принадлежат одному и тому же поддереву и добавление ребра приведет к появлению цикла. Отбросить ребро т. е. положить и вернуться к шагу 2.

(ii) Если то ребро можно добавить к ребрам построенных поддеревьев. Перейти к шагу 3.

Шаг 3. Срастить два поддерева, у которых вершины имеют корневые пометки применив для этого метод, описанный выше в пункте

Шаг 4. Отобрав ребер, мы получаем некоторое дерево. Запомнить это дерево и перейти к шагу 5. Если отобрано меньше чем ребер, то положить и вернуться к шагу 2.

Шаг 5. (Возвращение.) Удалить ребро, добавленное последним. Предположим, что таким ребром является Если

Рис. 7.7. Граф из примера 2.3.

единственное оставшееся для добавления ребро, то остановиться. Все остовные деревья, таким образом, построены. (При любом дальнейшем ветвлении дерева решений вершина х останется изолированной.)

В противном случае надо обновить пометки, действуя так, как указано в пункте В, положить и возвратиться к шагу 2.