Введение
О числе остовных деревьев в графе
В математической области теории графов теорема Кирхгофа, или теорема Кирхгофа о матричном дереве, названная в честь Густава Кирхгофа, является теоремой о числе остовных деревьев в графе, показывающей, что это число может быть вычислено за полиномиальное время из определителя подматрицы матрицы Лапласа графа; в частности, число равно любому минору матрицы Лапласа. Теорема Кирхгофа является обобщением формулы Кэли, которая дает число остовных деревьев в полном графе. Теорема Кирхгофа опирается на понятие матрицы Лапласа графа, которая равна разности между матрицей степеней графа (диагональной матрицей со степенями вершин на диагонали) и его матрицей смежности (матрицей (0,1) с единицами в позициях, соответствующих записям, где вершины смежны, и нулями в противном случае). Для данного связного графа G с n помеченными вершинами пусть λ1, λ2, ..., λn−1 будут ненулевыми собственными значениями его матрицы Лапласа. Тогда число остовных деревьев графа G равно.
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1) matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise). For a given connected graph G with n labeled vertices, let λ1, λ2, , λn−1 be the non zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
Английский перевод оригинальной статьи Кирхгофа 1847 года был сделан Дж. Б. О’Тулом и опубликован в 1958 году.
Формула Кейли
Формула Кейли вытекает из теоремы Кирхгофа как частный случай, поскольку каждый вектор, имеющий 1 в одной позиции, -1 в другой и 0 в остальных позициях, является собственным вектором матрицы Лапласа полного графа, с соответствующим собственным значением, равным n. Вместе эти векторы образуют пространство размерности n − 1, поэтому других ненулевых собственных значений нет. В качестве альтернативы, заметим, что поскольку формула Кейли подсчитывает количество различных помеченных деревьев полного графа Kn, необходимо вычислить любой минор (кофактор) матрицы Лапласа Kn. Матрица Лапласа в данном случае имеет вид… Любой минор (кофактор) указанной выше матрицы равен n^(n−2), что и является формулой Кейли.
Any cofactor of the above matrix is nn−2, which is Cayley's formula.
Явное перечисление пересекающих деревьев
Теорема Кирхгофа может быть усилена путем изменения определения матрицы Лапласа. Вместо простого подсчета ребер, исходящих из каждой вершины или соединяющих пару вершин, присвойте каждому ребру неопределенное и пусть (i, j)-й элемент модифицированной матрицы Лапласа будет суммой неопределенных, соответствующих ребрам между i-й и j-й вершинами, когда i не равно j, и отрицательной суммой всех неопределенных, соответствующих ребрам, исходящим из i-й вершины, когда i равно j. Детерминант модифицированной матрицы Лапласа, полученный удалением любой строки и столбца (аналогично нахождению числа остовных деревьев из исходной матрицы Лапласа), является однородным полиномом (полиномом Кирхгофа) относительно неопределенных, соответствующих ребрам графа. После приведения подобных членов и выполнения всех возможных сокращений, каждый член в полученном выражении представляет собой остовное дерево, состоящее из ребер, соответствующих неопределенным, входящим в этот член. Таким образом, можно получить явное перечисление всех остовных деревьев графа, просто вычислив детерминант. Доказательство этой версии теоремы можно найти в работе Bollobás (1998).
Матроиды
Распределительные деревья графа образуют базисы графического матроида, поэтому теорема Кирхгофа предоставляет формулу для подсчета числа базисов в графическом матроиде. Тот же метод может быть также использован для подсчета числа базисов в регулярных матроидах, являющихся обобщением графических матроидов.