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

В этой части лекции мы рассмотрим так
называемые остовные деревья и их
применение для решения некоторого
класса прикладных задач. Сначала дадим
определение остовного дерева.

Определение 8.3.ДеревоTназываетсяостовным деревомграфаG,
еслиT– подграф графаGи каждая вершинаGявляется вершиной вT.

Теперь сформулируем теорему, которую
примем без доказательства.

Теорема 8.5.У
каждого связного графа существует
подграф, который является остовным
деревом.

Для построения остовных деревьев
существуют разные методы. Самыми
распространенными являются два метода:
метод поиска в ширину и метод поиска в
глубину.

Согласно методу поиска остовного дерева
в ширину произвольную вершину v₀графаG выбираем
в качестве корня дереваT.
Для каждой вершиныvграфаG, смежной с
вершинойv₀, в
деревоTдобавляется
вершинаvи ребро (v₀,v). Это вершины уровня
1. Затем берем каждую вершинуv_iуровня 1 и для каждой вершиныv_jграфаG, смежной с
вершинойv_iиз тех, что еще не выбраны, добавляем в
деревоTвершинуv_jи ребро (v_i,v_j).
Вершины, добавленные на этом этапе, –
это вершины уровня 2. Продолжаем процесс,
пока в графеGне
останется вершин, которые можно было
бы добавить в дерево. По построениюTявляется деревом. Если расстояние отv₀до вершиныvграфаGравноn,
то эта вершина будет добавлена в дерево
на уровнеn. Следовательно,Tнесомненно, является
остовным деревом.

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

При поиске в глубину усилия направлены
на построение для дерева как можно более
длинного пути.

Метод поиска в глубину начинается с
задания вершины графа, которую будем
считать корнем. Выбираем вершину v_i,
смежную с корнем, и формируем ребро
дерева. Затем выбираем вершинуv_j,
смежную с ранее выбранной вершинойv_i,
и формируем новое ребро. По ходу необходимо
помечать использованные вершины, с тем,
чтобы каждая вершина использовалась
один раз. Если, находясь в вершинеv,
мы выбираем другую вершинуwи обнаруживаем, что вершинаwуже была добавлена в дерево, то ребро
(v,w)
между этими вершинами не может быть
добавлено в дерево.

Когда имеем исходный граф, то само собой
возникает вопрос: сколько можно построить
остовных деревьев для помеченного графа
с nвершинами? Ответ
на этот вопрос дает теорема Кэли, которая
рассматривает число остовных деревьев
дляK_n.

Теорема 8.6.(Теорема Кэли)Число остовных деревьев дляK_n,
у которого вершины помечены, равно.

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

Определение 8.4.Матрицей Кирхгофасвязного графаGс
помеченными вершинами называется
матрицаK_vv=K(G),,
которую можно определить следующим
образом:

.

Теорема 8.7.(Теорема Кирхгофа)Число остовных деревьев в связном графеGпорядкаn2
равно алгебраическому дополнению любого
элемента матрицы КирхгофаK(G).

Пример 8.2.Найти число остовных деревьев данного
графа.

Решение.Сначала составляем для
данного графа матрицу Кирхгофа.

.

Теперь находим алгебраическое дополнение,
например, для элемента k₁₁матрицы Кирхгофа.

.

Проверим, например, для элемента k₂₃.

.

Итак, получаем, что данный граф имеет 8
остовных деревьев.



Соседние файлы в папке дискретка

• #
• #
• #
• #
• #
• #
• #

Антон Петрунин
«Квант» №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.

Лемма:

Пусть — обыкновенный — граф, , — матрица инцидентности некоторой его ориентации, — произвольный минор порядка матрицы . Тогда если не является деревом, то ; если — дерево, то .

Доказательство:

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

Определение:

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

Теорема (Формула Бине-Коши[1]):

Определитель матрицы равен сумме всевозможных попарных произведений миноров порядка матрицы на соответствующие миноры матрицы .

Следствие
При определитель произведения двух квадратных матриц порядка равен произведению определителей этих матриц

Теорема (Кирхгоф, 1847):

Число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента матрицы Кирхгофа .

Доказательство:

Пусть — произвольный связный обыкновенный — граф, и — матрица инцидентности какой-либо ориентации графа . Заметим, что в силу связности графа . По лемме выполняется . Пусть — подматрица матрицы , полученная удалением последней строки. Тогда имеем , где — это — матрица. Очевидно, есть алгебраическое дополнение элемента в матрице Кирхгофа . В силу формулы Бине-Коши равно сумме квадратов всех миноров порядка матрицы . Согласно лемме, доказанной выше, каждый такой минор равен , если остовный подграф графа , ребра которого соответствуют столбцам, вошедшим в матрицу минора , является деревом, и равен в другом случае. Следовательно, равно числу остовов графа . Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

См. также

• Связь матрицы Кирхгофа и матрицы инцидентности
• Матрица Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Примечания

Источники информации

• Асанов М., Баранский В., Расин В. – Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ “Регулярная и хаотическая динамика”, 2001, 288 стр.

Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.

Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.^{[1][нет в источнике]}

Формулировка[править | править код]

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

Пример[править | править код]

граф	3 его остовных дерева

Для графа G с матрицей смежности
 
получаем:
.

Алгебраическое дополнение, например, элемента M_{1, 2} есть , что совпадает с количеством остовых деревьев.

Следствия[править | править код]

Из матричной теоремы выводится

• Формула Кэли — число остовных деревьев полного графа равно .
• Число остовных деревьев полного двудольнoгo графа равно .

Обобщения[править | править код]

Теорема обобщается на случай мультиграфов и взвешенных графов.
Для взвешенного графа алгебраические дополнения элементов матрицы Кирхгофа равны сумме по всем остовным деревьям произведений весов всех их рёбер.
Частный случай получается, если взять веса равными 1: сумма произведений весов остовов будет равна количеству остовов.

Примечания[править | править код]

Ссылки[править | править код]

• Теорема Кирхгофа

Литература[править | править код]

Это статья-заготовка по математике. Помогите Википедии, дополнив эту статью, как и любую другую.

Public user contributions licensed under
cc-wiki license with attribution required