Матричная теорема о деревьях

Матричная теорема о деревьях (Matrix-tree theorem) — теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде число каркасов в связном графе:

Число каркасов в связном графе [math]\displaystyle{ \,G }[/math] порядка [math]\displaystyle{ n \geq 2 }[/math] равно алгебраическому дополнению любого элемента матрицы Кирхгофа [math]\displaystyle{ \,B(G) }[/math].

Следствием этой теоремы является Теорема Кэли о числе помеченных [math]\displaystyle{ \,n }[/math]-вершинных деревьев (равном [math]\displaystyle{ \,n^{n-2} }[/math]).

Литература

• Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.