Матричная теорема о деревьях

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Следствием этой теоремы является Теорема Кэли о числе помеченных \,n-вершинных деревьев (равном \,n^{n-2}).

Литература

  • Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.