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

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

Текущая версия от 17: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.