Матричная теорема о деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Матричная теорема о деревьях''' (''Matrix-tree theorem'') - теорема, доказанная Кирхго...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Матричная теорема о деревьях''' (''Matrix-tree theorem'') - | '''Матричная теорема о деревьях''' (''[[Matrix-tree theorem]]'') - | ||
теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде | теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде | ||
число каркасов в связном графе: | число [[каркас|каркасов]] в [[связный граф|связном графе]]: | ||
''Число каркасов в связном графе <math>G</math> ''порядка'' <math>n \geq 2</math> равно алгебраическому дополнению любого элемента матрицы Кирхгофа <math>B(G)</math>.'' | ''Число каркасов в связном графе <math>G</math> ''[[порядок графа|порядка]]'' <math>n \geq 2</math> равно алгебраическому дополнению любого элемента [[матрица Кирхгофа|матрицы Кирхгофа]] <math>B(G)</math>.'' | ||
Следствием этой теоремы является ''Теорема Кэли'' о числе помеченных | Следствием этой теоремы является ''[[Теорема Кэли]]'' о числе [[помеченный граф|помеченных]] | ||
<math>n</math>-вершинных деревьев (равном <math>n^{n-2}</math>). | <math>n</math>-[[вершина|вершинных]] [[дерево|деревьев]] (равном <math>n^{n-2}</math>). | ||
==Литература== | ==Литература== | ||
[Харари-Палмер] | [Харари-Палмер] | ||
Версия от 13:22, 23 ноября 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]).
Литература
[Харари-Палмер]