Матричная теорема о деревьях
Материал из Википедии — свободной энциклопедии
Матричная теорема о деревьях (Matrix tree theorem)
[править] Теорема
Пусть G — связный помеченный граф с матрицей смежности A. M — матрица, полученная из матрицы -A заменой i-го элемента главной диагонали на degvi — степень вершины i. Тогда все алгебраические дополнения матрицы M равны между собой и их общее значение есть число остовов графа G.