Матричная теорема о деревьях: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Матричная теорема о деревьях''' (''Matrix-tree theorem'') - теорема, доказанная Кирхго...)
(нет различий)

Версия от 15:53, 19 ноября 2009

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

Литература

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