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

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

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

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

Для данного связного графа G с n помеченными вершинами пусть λ ₁ ,  λ ₂ , ...,  λ _{n −1} — ненулевые собственные значения его матрицы Лапласа. Тогда число остовных деревьев группы G равно

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

Английский перевод оригинальной статьи Кирхгофа 1847 года был сделан Дж. Б. О'Тулом и опубликован в 1958 году. ^[1]

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

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

Сначала постройте матрицу Лапласа 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}}\right].}$

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

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

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

Схема доказательства

(Приведенное ниже доказательство основано на формуле Коши – Бине . Элементарное индукционное обоснование теоремы Кирхгофа можно найти на странице 654 книги Мура (2011). ^[2] ).

Прежде всего обратите внимание, что матрица Лапласа обладает свойством: сумма ее элементов в любой строке и любом столбце равна 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 = EE ^T . Кроме того, пусть F — матрица E с удаленной первой строкой, так что FF ^T = M ₁₁ .

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

${\displaystyle \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 пробегает подмножества [ m ] размера n - 1, а FS обозначает матрицу ( n - 1) на ( n - 1) _, столбцы которой являются столбцами F с индексом в S . Тогда каждое S определяет n - 1 ребро исходного графа, и можно показать, что эти ребра порождают остовное дерево тогда и только тогда, когда определитель FS равен +1 или -1, и что они не индуцируют остовное дерево _. тогда и только тогда, когда определитель равен 0. Это завершает доказательство.

Частные случаи и обобщения

Формула Кэли

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

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

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

Любой сомножитель приведенной выше матрицы равен n ^{n −2} , что соответствует формуле Кэли.

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

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

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

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

Явное перечисление связующих деревьев

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

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

Доказательство этой версии теоремы см. в Bollobás (1998). ^[3]

Матроиды

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

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

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

• Запись q _i,j для различных i и j равна − m , где m — количество ребер от i до j ;
• Запись q _i,i равна входной степени i минус количество петель в i .

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

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

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

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

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

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

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

${\displaystyle 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\}}$

${\displaystyle {\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 в два раза превышает количество ребер. Случай k = 1 соответствует исходной теореме Кирхгофа , поскольку вес каждого остовного дерева равен n .

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

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

Смотрите также

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

Рекомендации

1. О'Тул, Дж. Б. «О решении уравнений, полученных в результате исследования линейного распределения гальванических токов». IRE Транзакции по теории цепей . 5 (1): 4–7. дои : 10.1109/TCT.1958.1086426.
2. Мур, Кристофер (2011). Характер вычислений . Оксфорд, Англия, Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-923321-2. ОСЛК  180753706.
3. Боллобас, Бела (1998). Современная теория графов . Нью-Йорк: Спрингер. дои : 10.1007/978-1-4612-0619-4. ISBN 978-0-387-98488-9.
4. Биггс, Н. (1993). Алгебраическая теория графов . Издательство Кембриджского университета.

• Харрис, Джон М.; Херст, Джеффри Л.; Моссингхофф, Майкл Дж. (2008), Комбинаторика и теория графов , Тексты для студентов по математике (2-е изд.), Springer.
• Маурер, Стивен Б. (1976), «Матричные обобщения некоторых теорем о деревьях, циклах и коциклах в графах», SIAM Journal on Applied Mathematics , 30 (1): 143–148, doi : 10.1137/0130017, MR  0392635.
• Тутт, WT (2001), Теория графов , издательство Кембриджского университета, стр. 138, ISBN 978-0-521-79489-3.
• Чайкен, С.; Клейтман, Д. (1978), «Теоремы о матричном дереве», Журнал комбинаторной теории, серия A , 24 (3): 377–381, doi : 10.1016/0097-3165(78)90067-5 , ISSN  0097-3165

Внешние ссылки

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