Аноним

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

Материал из WikiGrapp
нет описания правки
(Создана новая страница размером '''Матричная теорема о деревьях''' (''Matrix-tree theorem'') - теорема, доказанная Кирхго...)
 
Нет описания правки
Строка 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>).
==Литература==
==Литература==
[Харари-Палмер]
[Харари-Палмер]