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

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

Теорема Кирхгофа основывается на понятии лапласиана матрицы графа , которая равна разнице между графа в степени матрицы (диагональная матрица с вершинными градусов по диагонали) и его матрицы смежности (A (0,1) -матрицы с 1 - х в местах, соответствующих элементам, где вершины смежны, и нули в противном случае).

Для данного связного графа G с n помеченными вершинами пусть λ ₁ , λ ₂ , ..., λ _n₋₁ ненулевые собственные значения его матрицы Лапласа. Тогда количество остовных деревьев группы G равно

{\ displaystyle t (G) = {\ frac {1} {n}} \ lambda _ {1} \ lambda _ {2} \ cdots \ lambda _ {n-1} \ ,.}

Эквивалентное число остовных дерев равно любого кофактор лапласовской матрицы G .

Пример использования теоремы о матричном дереве [ править ]

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

Сначала построим матрицу лапласа Q для примера ромбовидного графа G (см. Изображение справа):

{\ displaystyle Q = \ left [{\ begin {array} {rrrr} 2 & -1 & -1 & 0 \\ - 1 & 3 & -1 & -1 \\ - 1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \ end {array} }\верно].}

Далее, построить матрицу Q ^* , удалив все строки и любой столбец из Q . Например, удаление строки 1 и столбца 1 дает

{\ displaystyle Q ^ {\ ast} = \ left [{\ begin {array} {rrr} 3 & -1 & -1 \\ - 1 & 3 & -1 \\ - 1 & -1 & 2 \ end {array}} \ right].}

И, наконец, взять на себя определитель из Q ^* , чтобы получить т ( G ), который является 8 для алмаза графа. (Обратите внимание, что t ( G ) является (1,1) -кофактором Q в этом примере.)

Схема доказательства [ править ]

(Доказательство, приведенное ниже, основано на формуле Коши-Бине . Элементарные индукционные аргументы в пользу теоремы Кирхгофа можно найти на странице 654 Moore (2011). ^[1] )

Сначала обратите внимание, что матрица Лапласа обладает тем свойством, что сумма ее записей в любой строке и любом столбце равна 0. Таким образом, мы можем преобразовать любой второстепенный в любой другой второстепенный, добавляя строки и столбцы, переключая их и умножая строку или столбец на −1. Таким образом, сомножители одинаковы до знака, и можно проверить, что на самом деле они имеют один и тот же знак.

Продолжим показать, что определитель минора M ₁₁ считает количество остовных деревьев. Пусть n - количество вершин графа, а m - количество его ребер. Матрица инцидентности E представляет собой матрицу размером n на m , которую можно определить следующим образом: предположим, что ( i , j ) - k- е ребро графа, и что i < j . Тогда E _ik = 1, E _jk = −1, а все остальные элементы в столбце k равны 0 (см. Ориентированную матрицу инцидентностидля понимания этой модифицированной матрицы инцидентности E ). Для предыдущего примера (с n = 4 и m = 5):

{\ displaystyle E = {\ begin {bmatrix} 1 & 1 & 0 & 0 & 0 \\ - 1 & 0 & 1 & 1 & 0 \\ 0 & -1 & -1 & 0 & 1 \\ 0 & 0 & 0 & -1 & -1 \\\ end {bmatrix}}.}

Напомним , что лапласиан L можно разложить в произведение матрицы инцидентности и ее транспонированной, то есть L = ЕЕ ^Т . Кроме того, пусть F - матрица E с удаленной первой строкой, так что FF ^T = M ₁₁ .

Теперь формула Коши-Бине позволяет записать

\det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{\mathrm {T} }\right)=\sum _{S}\det \left(F_{S}\right)^{2}

где S диапазоны по подмножеств [ м ] размера п - 1, а F _S обозначает ( п - 1) матрицу с размерностью ( п матрицу, столбцы которой являются те - 1) F с индексом в S . Тогда каждое S определяет n - 1 ребро исходного графа, и можно показать, что эти ребра индуцируют остовное дерево тогда и только тогда, когда определитель F _S равен +1 или -1, и что они не индуцируют остовное дерево тогда и только тогда, когда определитель равен 0. Это завершает доказательство.

Частные случаи и обобщения [ править ]

Формула Кэли [ править ]

Формула Кэли следует из теоремы Кирхгофа как частный случай, поскольку каждый вектор с 1 в одном месте, −1 в другом месте и 0 в другом месте является собственным вектором матрицы Лапласа полного графа с соответствующим собственным значением n . Эти векторы вместе охватывают пространство размерности n - 1, поэтому других ненулевых собственных значений нет.

В качестве альтернативы обратите внимание, что поскольку формула Кэли подсчитывает количество различных помеченных деревьев полного графа K _n, нам нужно вычислить любой кофактор лапласианской матрицы K _n . Матрица Лапласа в этом случае имеет вид

{\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.

Любой кофактор указанной выше матрицы равен n ⁿ⁻² , что является формулой Кэли.

Теорема Кирхгофа для мультиграфов [ править ]

Теорема Кирхгофа верна и для мультиграфов ; матрица Q модифицируется следующим образом:

Запись q _{i, j} равна - m , где m - количество ребер между i и j ;
при подсчете степени вершины исключаются все петли .

Формула Кэли для полного мультиграфа: m ^{n -1} ( n ^{n -1} - ( n -1) n ^{n -2} ) теми же методами, что и выше, поскольку простой граф - это мультиграф с m = 1.

Явное перечисление покрывающих деревьев [ править ]

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

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

Матроиды [ править ]

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

Теорема Кирхгофа для направленных мультиграфов [ править ]

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

Запись q _{i, j} для различных i и j равна - m , где m - количество ребер от i до j ;
Запись q _{i, i} равна степени i за вычетом количества петель в i .

Количество ориентированных остовных деревьев укорененных в вершине я определитель матрицы получали путем удаления я ю строку и столбец Q .

Подсчет охватывающих k- компонентных лесов [ править ]

Теорема Кирхгофа может быть обобщена для подсчета $k-$ компонентных остовных лесов в невзвешенном графе. ^[2] $к$ -компоненту охватывающие лес подграфа с $K$ связных компонентами , который содержит все вершины и является циклом свободного, т.е. существует не более одного путь между каждой парой вершин. Для такого леса F со связными компонентами определите его вес как произведение количества вершин в каждой компоненте. потом ${\textstyle F_{1},\dots ,F_{k}}$ ${\textstyle w(F)=|V(F_{1})|\cdot \dots \cdot |V(F_{k})|}$

\sum _{F}w(F)=q_{k},

где сумма берется по всем $k$ -компонентным остовным лесам и является коэффициентом полинома ${\textstyle q_{k}}$ ${\textstyle x^{k}}$

(x+\lambda _{1})\dots (x+\lambda _{n-1})x.

Последний множитель в полиноме связан с нулевым собственным значением . Более точно, это число может быть вычислено как ${\textstyle \lambda _{n}=0}$ ${\textstyle q_{k}}$

q_{k}=\sum _{\{i_{1},\dots ,i_{n-k}\}\subset \{1\dots n-1\}}\lambda _{i_{1}}\dots \lambda _{i_{n-k}}.

где сумма берется по всем n - k -элементным подмножествам . Например ${\textstyle \{1,\dots ,n\}}$

${\begin{aligned}q_{n-1}&=\lambda _{1}+\dots +\lambda _{n-1}=\mathrm {tr} Q=2|E|\\q_{n-2}&=\lambda _{1}\lambda _{2}+\lambda _{1}\lambda _{3}+\dots +\lambda _{n-2}\lambda _{n-1}\\q_{2}&=\lambda _{1}\dots \lambda _{n-2}+\lambda _{1}\dots \lambda _{n-3}\lambda _{n-1}+\dots +\lambda _{2}\dots \lambda _{n-1}\\q_{1}&=\lambda _{1}\dots \lambda _{n-1}\\\end{aligned}}$

Поскольку остовный лес с n –1 компонентами соответствует одному ребру, случай k = n - 1 утверждает, что сумма собственных значений Q в два раза больше числа ребер. В к = 1 случай соответствует исходной Кирхгофа теоремы , так как вес каждого связующего дерева является п .

Доказательство проводится аналогично доказательству теоремы Кирхгофа. Обратимая подматрица матрицы инцидентности биективно соответствует k- компонентному остовному лесу с выбором вершины для каждой компоненты. ${\textstyle (n-k)\times (n-k)}$

Коэффициенты являются до знака коэффициентов характеристического полинома из Q . ${\textstyle q_{k}}$

См. Также [ править ]

Последовательность Прюфера
Минимальное остовное дерево
Список тем, связанных с деревьями

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

^ Мур, Кристофер (2011). Природа вычислений . Оксфорд, Англия, Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-923321-2. OCLC 180753706 .
^ Биггс, Н. (1993). Алгебраическая теория графов . Издательство Кембриджского университета.

Харрис, Джон М .; Херст, Джеффри Л .; Моссингхофф, Майкл Дж. (2008), Комбинаторика и теория графов , Тексты для студентов по математике (2-е изд.), Springer.
Maurer, Стивен Б. (1976), "Матричные обобщения некоторых теорем о деревьях, циклов и коциклов в графах", SIAM журнал по прикладной математике , 30 (1): 143-148, DOI : 10,1137 / 0130017 , MR 0392635.
Тутте, В.Т. (2001), Теория графов , Издательство Кембриджского университета, стр. 138, ISBN 978-0-521-79489-3.
Chaiken, S .; Клайтман, D. (1978), "Матрица дерева теоремы", Журнал комбинаторной теории, Серия А , 24 (3): 377-381, DOI : 10,1016 / 0097-3165 (78) 90067-5 , ISSN 0097-3165

Внешние ссылки [ править ]

Доказательство теоремы Кирхгофа

[Moore_2011_p._654-1] Мур, Кристофер (2011). Природа вычислений . Оксфорд, Англия, Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-923321-2. OCLC 180753706 .

[2] Биггс, Н. (1993). Алгебраическая теория графов . Издательство Кембриджского университета.

[1]