Просмотр кода страницы Матричная теорема о деревьях

'''Матричная теорема о деревьях''' (''[[Matrix-tree theorem]]'') — 
теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде
число [[каркас|каркасов]] в [[связный граф|связном графе]]:

''Число каркасов в связном графе <math>\,G</math> ''[[порядок графа|порядка]]'' <math>n \geq 2</math> равно алгебраическому дополнению любого элемента [[матрица Кирхгофа|матрицы Кирхгофа]] <math>\,B(G)</math>.''

Следствием этой теоремы является ''[[Теорема Кэли]]'' о числе [[помеченный граф|помеченных]]
<math>\,n</math>-[[вершина|вершинных]] [[дерево|деревьев]] (равном <math>\,n^{n-2}</math>).
==Литература==
* Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.