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

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

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

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

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

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

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

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

где то дерево можно получить из дерева удалив из дугу и добавив дугу Такое преобразование дерева в дерево называется элементарным преобразованием дерева.

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

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