Теорема Кирхгофа
В математической области теории графов теорема Кирхгофа или теорема Кирхгофа о матричном дереве, названная в честь Густава Кирхгофа , представляет собой теорему о количестве остовных деревьев в графе , показывающую, что это число может быть вычислено за полиномиальное время из определителя подматрицы матрицы . лапласова матрица графа; в частности, это число равно любому кофактору матрицы Лапласа. Теорема Кирхгофа является обобщением формулы Кэликоторый обеспечивает количество остовных деревьев в полном графе .
Теорема Кирхгофа основана на понятии матрицы Лапласа графа, которая равна разности между матрицей степеней графа ( диагональная матрица со степенями вершин на диагоналях) и его матрицей смежности ((0,1)-матрица с единицами в местах, соответствующих записям, где вершины являются смежными, и 0 в противном случае).
Для данного связного графа G с n помеченными вершинами пусть λ 1 , λ 2 , ..., λ n −1 будут ненулевыми собственными значениями его матрицы Лапласа. Тогда количество остовных деревьев графа G равно
Затем постройте матрицу Q * , удалив любую строку и любой столбец из Q . Например, удаление строки 1 и столбца 1 дает
Наконец, возьмите определитель Q * , чтобы получить t ( G ), который равен 8 для ромбовидного графа. (Обратите внимание , что t ( G ) является (1,1) -кофактором Q в этом примере.)
(Приведенное ниже доказательство основано на формуле Коши-Бине . Элементарный аргумент индукции для теоремы Кирхгофа можно найти на странице 654 Мура (2011). [1] )
