Как найти все остовные деревья графа

If you use terms from paper you mentioned and you define spanning tree of directed graph as tree rooted in vertex r, having unique path from r to any other vertex then:

It’s obvious that worst case when directed graph has the greatest number of the spanning trees is complete graph (there are a->b and b->a edges for any pair).
If we “forget” about directions we will get n^{n-2} spanning trees as in case of undirected graphs. For any of this spanning trees we have n options to choose a root, and this choice define uniquely define directions of edges we need to use. Not hard to see, that all trees we get are spanning, unique and there are no nother options. So we get n^{n-1} spanning trees. Strict proof will take time, I hope that simple explanation is enough.

So this task will take exponential time depend from vertex count in worst case. Considering the size of output (all spanning trees), I conclude that for arbitrary graph, algorithm can not be significantly faster and better. I think you need to somehow reformulate your original problem to not deal with all spanning trees, and may be search only needed by some criteria.

I.                 
Деревья. Остовы

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

Рассмотрим неориентированный
граф G=(X,U) с n вершинами. Следующие определения дерева,
как легко показать, эквивалентны друг другу:

        
i.     
связный
граф, не имеющий циклов;

       ii.      связный граф, содержащий n вершин и n-1 ребер;

      iii.      граф, в котором каждая пара вершин соединена
одной единственной простой цепью.

Граф
G¹=(X¹,U¹) называется подграфом
(или частью)
графа G=(X,U), если , . Подграф G¹
называется остовным подграфом, если .

Остовным
деревом (или остовом) графа G называется всякий остовный подграф
графа G, являющийся деревом.
Например, если G – граф, показанный
на рис. 1.а, то граф, на рис. 1.б является остовом графа G, как и граф, изображенный на рис. 1.в.

рис.
1.а                                                          рис.
1.б                                              рис.
1.в

Очевидно,
что в каждом графе существует остов: разрушая в каждой компоненте связности
циклы, т.е. удаляя лишние ребра, придем к остову. В общем случае остов
определен неоднозначно. Естественно возникает вопрос: как много остовов в
графе?

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

Теорема 2. При n>1 число остовов в полном графе  равно .

II.              
Практический пример.

4.)       • Дан граф :     

         •  Задача :

Найти все остовные деревья в графе.

         •  Решение :

1.)   Т.к.
нам дан полный граф с числом вершин n=4 , то используя Теорему 1 сможем найти
количество всех остовов:

K_n = n^n-2 =
4² = 16

2.)   Находим
все остовные деревья графа:

 1. – 16.

III.          
Алгоритм Прима.

Кратчайший остов графа (остов минимального веса).

Рассмотрим взвешенный связный неориентированный граф G=(X,U); вес ребра (x_i, x_j)
обозначим c_ij. Из большого
числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая.
Такая задача возникает, например, в том случае, когда вершины являются клеммами
электрической цепи которые должны быть соединены друг с другом с помощью
проводов наименьшей общей длины (для уменьшения уровня наводок).

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

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

Воспользуемся алгоритмом Р. Прима (1957 г.), применимый к
произвольному связному графу

Шаг 1. Выбираем ребро  минимального веса и
строим дерево .

Шаг 2. Если дерево  порядка  уже построено и , то среди ребер, соединяющих вершины этого дерева с
вершинами графа G=(X,U),
не входящими в , выбираем ребро  минимального веса.
Строим дерево , присоединяя к  ребро  вместе с его не
входящим в  концом.

IV.           
Текст программы.

V.              
Вывод.

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

Макеты страниц

Антон Петрунин
«Квант» №9, 2018

Графы и их остовные деревья

Рассмотрим план шести ежедневных рейсов некоторой авиакомпании между некоторыми парами из аэропортов a, b, c и d, показанный на рисунке 1. Для формализации такой и многих других ситуаций в математике используется понятие граф.

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

Иначе говоря, с математической точки зрения, на рисунке 1 мы видим граф с четырьмя вершинами a, b, c и d, шестью ребрами, из них одно ребро — петля при вершине c и пара ребер соединяет b с d. Число ребер, исходящих из данной вершины, называется ее степенью, при этом петли считаются дважды; степени вершин a, b, c и d — 1, 4, 4 и 3 соответственно.

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

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

Цикл — это маршрут, составленный из различных ребер, обходящий несколько вершин без повторений и возвращающийся в исходную вершину. Число ребер в цикле называется длиной цикла. Например, в нашем графе есть два цикла длины три с вершинами b, c и d, один цикл длины два с вершинами b и d, а также петля при вершине c образует цикл длины один.

Действительно, если из любого цикла связного графа выбросить любое ребро, то граф останется связным. Более того, если после удаления некоторого ребра граф остался связным, то это ребро принадлежало некоторому циклу — этот цикл образован самим ребром и кратчайшим путем между его концами в оставшемся графе.

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

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

На рисунке 2 вы видите все пять различных остовных деревьев нашего исходного графа.

Число остовных деревьев в данном графе Γ мы будем обозначать τ(Γ). Например, если Γ — это граф, рассмотренный выше, то τ(Γ) = 5.

Чтобы проверить понимание данных определений, мы советуем решить следующие два стандартных упражнения про деревья.

В частности, из упражнения 2 следует, что независимо от выбора ребер число удаленных ребер в процедуре получения остовного дерева из графа, описанной выше, — одно и то же. (Для связного графа Γ это число называют его первым числом Бэтти; оно обычно обозначается β₁(Γ).)

Ребро связного графа называется мостом, если удаление этого ребра из графа делает граф несвязным; такой граф разбивается на два связных графа, называемые его островами (рис. 3).

Удаление-плюс-стягивание

Пусть ρ есть ребро в графе Γ. Обозначим через Γρ граф, полученный из Γ удалением ребра ρ, и через Γ/ρ — граф, полученный из Γ стягиванием ребра ρ в точку (рис. 4).

Если ребро ρ не является петлей, тогда выполняется следующее соотношение:

τ(Γ) = τ(Γρ) + τ(Γ/ρ), (*)

которое мы будем называть удаление-плюс-стягивание.

Действительно, остовные деревья в Γ можно разделить на две категории — те, что содержат ребро ρ, и те, что его не содержат. Для деревьев из первой категории стягивание ребра ρ в точку дает остовное дерево в Γ/ρ, а деревья второй категории являются также остовными деревьями в графе Γρ. Более того, оба этих соответствия взаимно однозначны. Отсюда вытекает формула (*).

Например, если Γ — это первый пример и ρ есть ребро между вершинами b и c, тогда первые два остовных дерева на рисунке 2 соответствуют дереву в Γρ, а последние два соответствуют дереву в Γ/ρ.

Формулу (*) удобно записывать схематически, как показано на рисунке 4. На графе Γ ребро ρ, для которого применяется формула, перечеркнуто.

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

τ(Γ) = τ(Γρ).

Из формулы удаление-плюс-стягивание можно вывести несколько других полезных соотношений. Например, если в графе Γ есть концевая вершина w (т.е. вершина степени 1), то w и единственное ребро при w можно удалить и в полученном графе Γw число его остовных графов не изменится, т.е.

τ(Γ) = τ(Γw).

Действительно, обозначим через ρ единственное ребро при w. Заметим, что граф Γρ несвязен, поскольку вершина w не имеет ребер, и, значит, τ(Γρ) = 0. С другой стороны, Γ/ρ = Γw, откуда и получаем наше равенство.

На схемах двусторонняя стрелка «↔» будет означать, что соответствующие графы имеют то же число остовных деревьев; например, из выведенных соотношений можно получить следующую диаграмму (рис. 5), означающую, в частности, что τ(Γ) = 2 · τ(Δ).

Равенства, описанные выше, дают алгоритм вычисления τ(Γ). Действительно, для любого ребра ρ оба графа Γρ и Γ/ρ имеют меньшее число ребер. Таким образом, удаление-плюс-стягивание сводит нахождение числа остовных деревьев Γ к нахождению числа остовных деревьев более простых графов.

Деревья в веерах

Графы следующего вида (рис. 6) называются веерами; веер с n + 1 вершиной будет обозначаться Θ_n.

Применив соотношения, полученные в предыдущем разделе, мы можем составить бесконечную схему, показанную на рисунке 7. В дополнение к веерам ( Θ_n ) в схеме участвуют их вариации ( Θ^′_n ), отличающиеся от ( Θ_n ) дополнительным ребром. При возникновении петель или концевых вершин мы их тут же удаляем.

Введем обозначения ( a_n = τ(Θ_n) ) и ( a^′_n = τ(Θ^′_n) ). Из схемы легко вывести два рекуррентных соотношения:

( a_{n+1} = a^′_n + a_n, )
( a^′_n = a_n + a^′_{n−1} )

Таким образом, в последовательности чисел ( a_1, a^′_1, a_2, a^′_2, a_3,… ) каждое следующее является суммой двух предыдущих.

Напомним, что последовательность чисел Фибоначчи F_n задается тем же соотношением F_n+1 = F_n + F_n−1 с F₁ = F₂ = 1. Она начинается так:

1, 1, 2, 3, 5, 8, 13, …

Далее заметим, что ( Θ_1 ) — это две вершины, соединенные единственным ребром, а ( Θ^′_1 ) — это две вершины, соединенные двойным ребром. Отсюда ( a_1 = 1 = F_2 ) и ( a^′_1 = 2 = F_3 ), а значит,

a_n = F_2n

для любого n.

Можно также вывести рекуррентное соотношение на ( a_n ) без использования ( a^′_n ):

( a_{n+1} = a^′_n + a_n = 2a_n + a^′_{n−1} = 3a_n − a_{n−1}.)

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

( a_n = frac{1}{sqrt{5}}left(left(frac{3 + sqrt{5}}{2}right)^n − left(frac{3 − sqrt{5}}{2}right)^nright). )

Этот процесс подробно описан в книжке [4], которую мы рекомендуем читателю. Поскольку ( 0 < frac{1}{sqrt{5}} left(frac{3 − sqrt{5}}{2}right)^n < 1 ) для всех n, эту формулу можно записать короче:

( a_n = left[frac{1}{sqrt{5}} left(frac{3 + sqrt{5}}{2}right)^nright],)

где [x] обозначает целую часть числа x.

Для закрепления материала советуем разобрать следующие упражнения.

Заключительные замечания

Подсчет числа остовных деревьев связан с расчетом электрических цепей. Предположим, граф Γ описывает электрическую цепь, в которой каждое ребро — это сопротивление в один ом, источник питания подключен к вершинам a и b и I есть общий ток в цепи, измеренный в амперах. Нам надо посчитать ток через одно из сопротивлений.

Пусть ρ есть ребро Γ с выбранным направлением. Заметим, что все остовные деревья Γ можно разделить на три типа: (1) те, в которых на пути из a в b ребро ρ появляется с положительной ориентацией; (2) те, в которых на пути из a в b ребро ρ появляется с отрицательной ориентацией; (3) те, в которых на пути из a в b ребро ρ не появляется. Обозначим через τ₊, τ₋ и τ₀ число деревьев в этих трех категориях. Очевидно, что τ(Γ) = τ₊ + τ₋ + τ₀.

Силу тока I_ρ вдоль ρ можно вычислить по следующей формуле:

( I_ρ = frac{τ_+:−:τ_−}{τ(Γ)} · I)

Доказательство получается прямой проверкой правил Кирхгофа для значений токов, полученных по этой формуле, для всех ребер в Γ.

Есть множество других примеров использования правил Кирхгофа в теории графов. Например, в [7] они используются в физическом доказательстве формулы Эйлера

B − Р + Г = 2,

где В, Р и Г обозначают число вершин, ребер и граней многогранника соответственно.

Формула удаление-плюс-стягивание применялась при решении так называемой задачи о квадрировании квадрата. История этой задачи и ее замечательное решение обсуждаются в книжках [6] и [2]; идея этого решения также основана на оригинальном использовании электрических цепей.

Приведенный нами вывод рекуррентных формул для чисел остовных деревьев в веерах, лестницах и колесах дается в [8]; эта задача также обсуждается в классической книжке [3].

Существенно более сложной задачей является нахождение числа остовных деревьев в полных графах, т.е. таких, в которых любая пара различных вершин соединена единственным ребром. Если n обозначает число вершин полного графа, то число его остовных деревьев равно nⁿ⁻². Иными словами,

τ(Π_n) = nⁿ⁻², (**)

где Π_n обозначает полный граф с n вершинами (рис. 12).

Равенство (**) называется формулой Кэли. Наиболее известным доказательством является так называемый код Прюфера — способ однозначного кодирования дерева упорядоченной последовательностью из его вершин; нескольким другим доказательствам посвящена глава 30 в [1]. В расширенной версии настоящей статьи [5] приводится доказательство, основанное на формуле удаление-плюс-стягивание.

Для числа раскрасок вершин графа выполняется аналогичная формула: удаление-минус-стягивание. А именно, пусть χ(Γ, k) обозначает число раскрасок графа Γ в k цветов, при которых концы каждого ребра покрашены в разные цвета. Тогда выполняется соотношение

χ(Γ, k) = χ(Γρ, k) − χ(Γ/ρ, k).

Действительно, допустимые раскраски графа Γρ можно разбить на две категории: (1) те, в которых концы ребра ρ покрашены в разные цвета, такие остаются допустимыми в графе Γ; (2) те, в которых концы ребра ρ покрашены в один цвет, каждой такой раскраске соответствует единственная раскраска Γ/ρ. Отсюда — формула.

Литература
1. М. Айгнер, Г. Циглер. Доказательства из Книги. М.: Бином. Лаборатория знаний, 2015.
2. М. Гарднер. Математические головоломки и развлечения. М.: Оникс, 1994.
3. Д. Кнут, Р. Грэхем, О. Паташник. Конкретная математика. Математические основы информатики. М.: Вильямс, 2009.
4. А. И. Маркушевич. Возвратные последовательности. М.: Гостехиздат, 1950. (Популярные лекции по математике, выпуск 1.)
5. А. М. Петрунин. Сколько деревьев в графе // arXiv:1803.03749 [math.HO].
6. И. М. Яглом. Как разрезать квадрат? М.: Наука, 1968.
7. M. Levi. An Electrician’s (or a Plumber’s) Proof of Euler’s Polyhedral Formula // SIAM News, vol. 50, no. 4, 2017.
8. M. H. Shirdareh Haghighi, Kh. Bibak. Recursive relations for the number of spanning trees // Applied Mathematical Sciences, vol. 3, no. 46, pp. 2263–2269, 2009.

В работе, из которой Вы привели пример, далее рассматривается построение частичных неориентированных деревьев. Это не что иное, как остовные деревья. Поэтому первая мысль которая приходит в голову, это построить все остовные деревья, а после проверить их на «проходимость» в исходном графе.

Есть алгоритмы поиска остовных деревьев, в том числе в оптимизационных задачах. Например, MST (поиск минимального остовного дерева), и его модификации для поиска n минимальных остовных деревьев. Полагая, что веса ребер единичны, можно применить эти алгоритмы.

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

Но одна из моих попыток, как мне кажется. заслуживает внимания.
Имеем граф из Вашего примера:

Я разделил дуги на группы (раскрасил в разные цвета) по признаку вхождения в вершину. Главная особенность этих групп в том, что только одно ребро из группы может оказаться в прадереве. Таким образом, если мы сочетаем все группы между собой, то получим множество комбинаций дуг, подмножеством которого будут и искомые нами прадеревья. Если мы имеем m групп с количеством элементов ni в каждом, то перемножив все ni получим количество возможных комбинаций.
Для нашего графа будет три группы:

const graphGroups = [
    ['AB', 'CB'],
    ['DC', 'BC'],
    ['AD', 'BD', 'CD'],
];

Получить их очень просто из матрицы смежности, где каждый столбец и представляет собой эту группу, минуя первый, т.к. вершина A – это корень.
Сочетая эти группы получим 12 комбинаций:

Шесть из них, как видно, и есть то, что нам надо. В набор попали варианты с кратными рёбрами (6, 7, 8, 9, 12) и такие, которые не проходят через все вершины (11), а прадерево должно затронуть все N вершин графа и иметь N – 1 ребро. Их нужно исключить.

Т.е. следующая задача – это сделать тест «связности» и отфильтровать лишнее, тогда получим то, что заслуживаем:

Проверим для такого графа:

Отфильтровав 16 вариантов, получим результат:

Код на JS:

const adjMatrix = [
  [0, 1, 0, 0, 1, 0],
  [0, 0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0, 1],
  [0, 0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0]
];

let graphGroups = [];
let N = adjMatrix.length;

const getLetter = i => String.fromCharCode(65 + i);

// Группируем рёбра
for (let j = 1; j < N; j++) {
  let group = [];

  for (let i = 0; i < N; i++)
    if (adjMatrix[i][j] > 0) group.push(getLetter(i) + getLetter(j));

  if (group.length > 0) graphGroups.push(group);
}

const reverseStr = (s) => s.split('').reverse().join('');

// Тест дерева
const testTree = (edges, size) => {
  let testTable = {};

  let checkPointsCount = [...new Set(edges.join(''))].join('').length == size;
  let checkDoubleEdges = edges.every((v) => {
    return testTable.hasOwnProperty(reverseStr(v)) ?
      false :
      testTable[v] = true;
  });

  return checkPointsCount && checkDoubleEdges;
}

// Формируем деревья

let queue = [graphGroups[0]];
let row = Array(graphGroups.length).fill('');
let i = 0;
let size = graphGroups.length;
let out = [];

while (i >= 0) {
  if (queue[i].length == 0) {
    i--;
    queue.pop();
  } else {

    row[i] = queue[i].shift();

    if (i < size - 1)
      queue.push(graphGroups[++i].slice());
    else if (testTree(row, N))
      out.push(row.slice());
  }
};


// Вывод
graphPoints = {
  A: [0, 40],
  B: [40, 0],
  C: [40, -40],
  D: [-40, -40],
  E: [-40, 0],
  F: [0, -20],
};

out.every((v, i) => makeGraphTree(graphPoints, v, '' + (i + 1)));
console.log(out);



// Вспомогалки-рисовалки
function makeGraphTree(points, edges, text = '5') {
  var canvas = document.createElement("canvas");
  var ctx = canvas.getContext("2d");

  canvas.width = 100;
  canvas.height = 100;

  ctx.translate(50, 50);
  if (text.length > 0) ctx.fillText(text, -45, -37);
  ctx.scale(1, -1);
  ctx.lineWidth = 0.5;

  ctx.fillStyle = 'red';

  Object.entries(points).map(p => drawDot(ctx, p[1]));

  ctx.beginPath();
  edges.map((e) => drawArrow(ctx, points[e[0]], points[e[1]]));
  ctx.stroke();

  document.body.appendChild(canvas);
  return true;
}

function drawDot(ctx, p) {
  ctx.beginPath();
  ctx.arc(p[0], p[1], 3, 0, 2 * Math.PI, false);
  ctx.fill();
}

function drawArrow(ctx, p1, p2) {
  var headSize = 10;
  var dx = p2[0] - p1[0];
  var dy = p2[1] - p1[1];
  var angle = Math.atan2(dy, dx);
  ctx.moveTo(p1[0], p1[1]);
  ctx.lineTo(p2[0], p2[1]);
  ctx.lineTo(p2[0] - headSize * Math.cos(angle - Math.PI / 8), p2[1] - headSize * Math.sin(angle - Math.PI / 8));
  ctx.moveTo(p2[0], p2[1]);
  ctx.lineTo(p2[0] - headSize * Math.cos(angle + Math.PI / 8), p2[1] - headSize * Math.sin(angle + Math.PI / 8));
}

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