§ 2.11.2. Количество остовных деревьев графа.
В некоторых ситуациях возникает необходимость в построении полного списка деревьев графа G.
Рассмотрим два (ориентированных или неориентированных) остовных дерева T1=(X,A1) и T2=(X,A2) графа G=(X,A).
«Расстояние» между деревьями обозначается через d(T1,T2) и определяется как число дуг из T1, которых нет в T2 (или, что эквивалентно, как число дуг из T2, которых нет в T1, поскольку оба дерева T1 и T2 имеют n-1 дуг).
§ 2.11.3. Кратчайший остов графа (sst)
Рассмотрим взвешенный связный неориентированный граф G=(X,A). Вес ребра (хi,xj) обозначим сij. Из большого числа остовов графа нужно найти один, у которого сумма весов рёбер наименьшая.
Кратчайшее остовное дерево находит применение тогда, когда необходимо связать n точек некоторой сетью коммуникаций так, чтобы общая длина линий связи была минимальной.
Задача построения кратчайшего остова графа является одной из немногих задач из теории графов, которые можно считать полностью решёнными. Существует несколько алгоритмов построения SST.
Итак, пусть Ti и Tj – два произвольных поддерева, полученных путём добавки рёбер при построении SST. Если символ Ti использовать также для обозначения множества вершин данного поддерева, то величина ∆ij может быть определена как кратчайшее из расстояний между вершинами из Ti и вершинами из Tj, т.е.
Введём операцию J, многократное применение которой приводит к построению SST-графа.
Для поддерева Ts найти такое поддерево Tj, чтобы ∆sj*= [∆sj]. Пусть ) будет тем ребром, вес которого соответствует величине ∆sj* в выражении (1). Тогда ребро ) принадлежит SST и может быть добавлено к другим рёбрам частично сформированного SST.
Алгоритм Краскала.
Шаг 1. Начать с вполне несвязного графа T, содержащего n вершин.
Шаг 2. Упорядочить рёбра графа G в порядке неубывания их весов.
Шаг 3. Начав с первого ребра в этом списке, добавлять рёбра в графе T, соблюдая условие: такое добавление не должно приводить к появлению цикла в Т.
Шаг 4 . Повторить шаг 3 до тех пор, пока число рёбер в Т не станет равным n-1. Получившееся дерево является кратчайшим остовом (SST) исходного графа G.
§ 2.13. Сети. Потоки в сетях.
Если в орграфе G=(X,A),полустепень захода некоторой вершины s равно нулю (t(s)=0), то такая вершина называется источником. Если в орграфе G=(X,A) полустепень исхода некоторой вершины t равно нулю (O(s)=0), то такая вершина называется стоком.
Опр. Орграф с одним источником и с одним стоком называется сетью.
В теории графов встречается задача определения максимального потока, протекающего в орграфе G =(X,A), являющемся сетью, от источника s к стоку t. При этом каждой дуге (хi,хj) графа G приписана некоторая пропускная способность qij, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача может возникнуть, например, при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. Решение этой задачи также укажет ту часть сети дорог, которое образует «узкое место» в отношении потока между двумя концевыми пунктами.
Постановка задачи о максимальном потоке от s к t.
Рассмотрим сеть G =(X,A) с пропускными способностями дуг qij, источником s и стоком t, s,tX. Множество чисел ij, определённых на дугах (хi,хj)A , называют потоками в дугах, если выполняется следующие условия:
Уравнение (1) является уравнением сохранения потока. Оно утверждает, что поток, втекающий в вершину, равен потоку, вытекающему из вершины, за исключением источника s и стока t, для которых существуют вытекание и приток величины v соответственно. Соотношение (2) указывает на то, что потоки ограничены пропускными способностями для каждой дуги графа G.
Задача состоит в том, чтобы величина
Источник
Сколько деревьев в графе
Рассмотрим план шести ежедневных рейсов некоторой авиакомпании между некоторыми парами из аэропортов 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.
Чтобы проверить понимание данных определений, мы советуем решить следующие два стандартных упражнения про деревья.
Упражнения
1. Докажите, что если дерево имеет хотя бы две вершины, то в нем найдется вершина степени 1.
2. Докажите, что число ребер в любом дереве на единицу меньше числа его вершин. Воспользуйтесь индукцией по числу вершин и предыдущим упражнением.
В частности, из упражнения 2 следует, что независимо от выбора ребер число удаленных ребер в процедуре получения остовного дерева из графа, описанной выше, — одно и то же. (Для связного графа Γ это число называют его первым числом Бэтти; оно обычно обозначается β1(Γ).)
Ребро связного графа называется мостом, если удаление этого ребра из графа делает граф несвязным; такой граф разбивается на два связных графа, называемые его островами (рис. 3).
Упражнение 3. Пусть граф Γ содержит мост между островами Δ1 и Δ2. Докажите, что τ(Γ) = τ(Δ1) · τ(Δ2).
Удаление-плюс-стягивание
Пусть ρ есть ребро в графе Γ. Обозначим через Γ\ρ граф, полученный из Γ удалением ребра ρ, и через Γ/ρ — граф, полученный из Γ стягиванием ребра ρ в точку (рис. 4).
Если ребро ρ не является петлей, тогда выполняется следующее соотношение:
которое мы будем называть удаление-плюс-стягивание.
Действительно, остовные деревья в Γ можно разделить на две категории — те, что содержат ребро ρ, и те, что его не содержат. Для деревьев из первой категории стягивание ребра ρ в точку дает остовное дерево в Γ/ρ, а деревья второй категории являются также остовными деревьями в графе Γ\ρ. Более того, оба этих соответствия взаимно однозначны. Отсюда вытекает формула (*).
Например, если Γ — это первый пример и ρ есть ребро между вершинами b и c, тогда первые два остовных дерева на рисунке 2 соответствуют дереву в Γ\ρ, а последние два соответствуют дереву в Γ/ρ.
Формулу (*) удобно записывать схематически, как показано на рисунке 4. На графе Γ ребро ρ, для которого применяется формула, перечеркнуто.
Заметим, что никакое остовное дерево не содержит петель. Поэтому можно удалить все петли из графа, и число его остовных деревьев останется неизменным. Иначе говоря, для любой петли ρ выполняется равенство
Из формулы удаление-плюс-стягивание можно вывести несколько других полезных соотношений. Например, если в графе Γ есть концевая вершина w (т.е. вершина степени 1), то w и единственное ребро при w можно удалить и в полученном графе Γ\w число его остовных графов не изменится, т.е.
Действительно, обозначим через ρ единственное ребро при w. Заметим, что граф Γ\ρ несвязен, поскольку вершина w не имеет ребер, и, значит, τ(Γ\ρ) = 0. С другой стороны, Γ/ρ = Γ\w, откуда и получаем наше равенство.
На схемах двусторонняя стрелка «↔» будет означать, что соответствующие графы имеют то же число остовных деревьев; например, из выведенных соотношений можно получить следующую диаграмму (рис. 5), означающую, в частности, что τ(Γ) = 2 · τ(Δ).
Равенства, описанные выше, дают алгоритм вычисления τ(Γ). Действительно, для любого ребра ρ оба графа Γ\ρ и Γ/ρ имеют меньшее число ребер. Таким образом, удаление-плюс-стягивание сводит нахождение числа остовных деревьев Γ к нахождению числа остовных деревьев более простых графов.
Деревья в веерах
Графы следующего вида (рис. 6) называются веерами; веер с n + 1 вершиной будет обозначаться Θn.
Применив соотношения, полученные в предыдущем разделе, мы можем составить бесконечную схему, показанную на рисунке 7. В дополнение к веерам \( Θ_n \) в схеме участвуют их вариации \( Θ^′_n \), отличающиеся от \( Θ_n \) дополнительным ребром. При возникновении петель или концевых вершин мы их тут же удаляем.
Введем обозначения \( a_n = τ(Θ_n) \) и \( a^′_n = τ(Θ^′_n) \). Из схемы легко вывести два рекуррентных соотношения:
Таким образом, в последовательности чисел \( a_1, a^′_1, a_2, a^′_2, a_3. \) каждое следующее является суммой двух предыдущих.
Напомним, что последовательность чисел Фибоначчи Fn задается тем же соотношением Fn+1 = Fn + Fn−1 с F1 = F2 = 1. Она начинается так:
Далее заметим, что \( Θ_1 \) — это две вершины, соединенные единственным ребром, а \( Θ^′_1 \) — это две вершины, соединенные двойным ребром. Отсюда \( a_1 = 1 = F_2 \) и \( a^′_1 = 2 = F_3 \), а значит,
Можно также вывести рекуррентное соотношение на \( a_n \) без использования \( a^′_n \):
Последовательности, для которых выполняется подобное соотношение, называются линейными рекуррентными последовательностями. Для такой последовательности можно найти формулу для ее общего члена. В нашем случае
Этот процесс подробно описан в книжке [4], которую мы рекомендуем читателю. Поскольку \( 0 n −2 . Иными словами,
где Πn обозначает полный граф с n вершинами (рис. 12).
Равенство (**) называется формулой Кэли. Наиболее известным доказательством является так называемый код Прюфера — способ однозначного кодирования дерева упорядоченной последовательностью из его вершин; нескольким другим доказательствам посвящена глава 30 в [1]. В расширенной версии настоящей статьи [5] приводится доказательство, основанное на формуле удаление-плюс-стягивание.
Для числа раскрасок вершин графа выполняется аналогичная формула: удаление-минус-стягивание. А именно, пусть χ(Γ, k) обозначает число раскрасок графа Γ в k цветов, при которых концы каждого ребра покрашены в разные цвета. Тогда выполняется соотношение
χ(Γ, k) = χ(Γ\ρ, k) − χ(Γ/ρ, k).
Действительно, допустимые раскраски графа Γ\ρ можно разбить на две категории: (1) те, в которых концы ребра ρ покрашены в разные цвета, такие остаются допустимыми в графе Γ; (2) те, в которых концы ребра ρ покрашены в один цвет, каждой такой раскраске соответствует единственная раскраска Γ/ρ. Отсюда — формула.
Упражнение 7. Докажите что для любого графа Γ функция χ(Γ, k) является многочленом с целыми коэффициентами от k; он называется хроматическим многочленом графа Γ.
Подсказка. Воспользуйтесь индукцией по общему числу ребер и вершин графа и формулой удаление-минус-стягивание.
Литература
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.
Источник