2. Построение всех остовных деревьев графа

В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа G. Например, в том случае, когда надо отобрать наилучшее дерево, а критерий, позволяюгций осугцествить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующ,ее перечисление всех остовных деревьев) оказывается невыполнимым. В других ситуациях, например при нахождении передаточной функции системы [42,6] пли при вычислении определителей некоторых матриц в макроэкономической теории [2], с помогцью порождения всех остовов соответствуюгцих графов можно добиться упрощения вычислительных процедур.

Число различных остовов полного связного неориентированного помеченного графа с п вершинами было найдено впервые Кэли [4]. Оно равно ?г ~. У Муна [45] приводится список из более чем 25 работ, содержащих разнообразные доказательства этой формулы. (См. также задачу 6.) Формулы для числа остовов в более общих графах можно найти у Риордана [49]. Хотя эти формулы, как правило, очень сложные и их вывод для наших целей не нужен, но стоит, пожалуй, привести следующий результат.

Теорема 1. Пусть G - п-вершинный граф без петель и - его матрица инциденций с одной удаленной строкой [т. е. с п - 1 независимыми строками). Пусть В\ - транспонированная матрица к В^. Тогда определитель \ В^ BI \ равен числу различных остовных деревьев графа G.

Доказательство этой теоремы можно найти в [53] и в [1] (см. также задачу 5).

Рис. 7.4. Граф G.

2.1. Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева Г] = {X, Ai) и = (X, А2) графа G = {X, А). Расстояние между двумя деревьями обозначается через d (Т^, Т^) и определяется как число дуг из Т^, которых нет в (или, что эквивалентно, как число дуг из Т^, которых нет в Tj, поскольку оба дерева и имеют {п - 1) дуг). Если d (Tj, Tj) = 1 т. е. если

(Л,иЛ)-(ПЛ) = {а1, аа},

где fli 6 1 и 2 € 2 то дерево Г2 можно получить из дерева Гх, удалив из Ti дугу и добавив дугу Cj. Такое преобразование дерева в дерево называется элементарным преобразованием дерева.

Теорема 2. Если и Ти - остовные деревья графа и d {Т^, Тц) = к, то дерево Ти может быть получено из Т^ с помощью серий из к элементарных преобразований.

Доказательство. Пусть al, al, . . ., До- Дуг из Т„, которых нет в Ти, и аи, al, ... а\ - к дуг из Ти, которых нет в То-Если в дерево Т^ добавить дугу al, то в получившемся графе, согласно определению дерева, найдется цикл. (На рис. 7.5(a) жирными линиями показано неориентированное дерево Т^, а пунктирной линией - дуга al = (5, х^) дерева Г4, приведенного на рис. 7.5(д).) В полученном цикле содержится по крайней мере одна дуга, не принадлежаш;ая дереву Ти. Следовательно, ее можно удалить, разорвав тем самым цикл, и это даст новое дерево Tj. Поскольку в Ti число дуг, обш;их с дугами из Ти, на единицу больше (чем в Тд), то d {Ti, Ти) = к - 1. Применяя элементарные преобразования дальше, получим последовательность деревьев Г2, Гд, . . ., Ти-г, Ти, в которой d {Тi, Ti+j) = 1 для каждого i = 2, . . ., к - 1. На рис. 7.5(6) -(д) показано, как с помощью 4 элементарных преобразований из дерева Т^ получается дерево Ti.

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

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

а^(дойавить)

Рис. 7.5. Порождение из Го посредством элементарных преобразований деревьев, (а) Остов Го графа с рис. 7.4. (б) Остов Т^. (в) Остов Т^. (г) Остов Г (д) Остов Tk (А: = 4).