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

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

Версия от 20: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]).

Литература

[Харари-Палмер]