Сколько деревьев в графе
Рассмотрим план шести ежедневных рейсов некоторой авиакомпании между некоторыми парами из аэропортов 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.
Источник