Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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.