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

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

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

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

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

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

видность. Для организации проверки на возможность образования цикла (при добавлении ребра) каждую вершину Xj помечают парой {Vj, pj). Процедуры выявления циклов, использующие пометки вершин, встречаются у Джонсона [32], Шринивасана и Томпсона [52], Гловера и Клингмана [25]. Первая пометка rj указывает корень поддерева, содержащего вершину xj. Первоначально rj - Xj для всех вершин Xj. На некотором шаге два поддерева Г, и сращиваются посредством добавления ребра а; = {ха, Xq) с вершиной Ха из Ti и вершиной Xg из Tg- Если на этом шаге - корневая пометка вершин в Ti, а .- корневая пометка вершин в Гз и <;г2 (например), то все вершины в должны сме-

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

Вторая пометка pj, приписанная вершине Xj, указывает вершину, предшествующую вершине Xj, т. е. если {х^, xj) - дуга рассматриваемого поддерева, то pj = х^. Для корневой вершины дерева такая пометка полагается равной нулю. Для дерева, изображенного на рис. 7.6 (а), р^ = х^, р^ = Хд и = 0.

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

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

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

1. Пусть Xj = Xj и Z = Pj.

2. Положить xi = Z, а Z = pi.

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

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

5. Положить ps = О, стоп.

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

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

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

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

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

(ii) Заменить в дереве корень на Xg (так, как было описано выше в пункте А), после чего изменить пометку предшествования у вершины Xfcpg = Onapg = х^.

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

Поскольку метод порождения деревьев, рассматриваемый ниже, является поиском, использующим дерево решений, то возникает необходимость удаления некоторых ребер (на шагах возвращения), чтобы испытать затем другие ребра. В такой ситуации удаление ребра приводит к расщеплению некоторого дерева на две части, например на и Tg, и в пометки одного из этих поддеревьев должны быть внесены изменения. Пусть удаляется ребро (ха, Xg), где Ха 6 Tl и Xg 6 Т'а- Тогда при pg = х^ (т. е. если ребро