Матричная теорема о деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Матричная теорема о деревьях''' (''Matrix-tree theorem'') - теорема, доказанная Кирхго...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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>). | ||
==Литература== | ==Литература== | ||
* Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977. | |||
Текущая версия от 10:29, 10 мая 2011
Матричная теорема о деревьях (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.