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

Матричная теорема о деревьях (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]).

Литература

[Харари-Палмер]