4194
правки
Матричная теорема о деревьях: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
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>). | ||
==Литература== | ==Литература== | ||
* Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977. | |||
