6.8 Число остовных 2-деревьев

В этом разделе мы связываем алгебраические дополнения матрицы графа G с числом остовных -деревьев соответствующего типа. Для этой цели нам необходимы обозначения -деревьев, идентифицирующие вершины, которые находятся в разных компонентах. Будем обозначать через остовные -деревья, в которых вершины должны быть в одной компоненте, а вершины — в другой. Число таких остовных 2-деревьев графа G будем обозначать через Например, ребра и ей образуют в графе на рис. 6.8, а остовное 2-дерево типа

Далее через А будем обозначать усеченную матрицу инциденций ориентированного графа, полученного присвоением произвольной

ориентации ребрам графа G, называя ее тем не менее усеченной матрицей инциденций G. Не нарушая общности, мы допускаем, что соответствует усекаемой строке А, а строка той же матрицы — вершине Символ будет обозначать алгебраическое дополнение элемента матрицы

Пусть — матрица, полученная удалением строки из первоначальной матрицы А. Если граф, полученный замыканием вершин графа G, то, как легко убедиться, справедливы следующие утверждения:

1) — матрица инциденций графа G, усеченная по строке, соответствующей вершине

2) Множество ребер порождает остов графа G тогда и только тогда, когда эти ребра образуют остовное -дерево в графе

Таким образом, между ненулевыми главными определителями и остовными -деревьями типа существует взаимно-однозначное соответствие.

Теорема 6.20. Для связного графа .

Доказательство.

Очевидно, что Это доказывает теорему, поскольку ненулевые главные определители соответствуют остовным -деревьям в графе G и наоборот.

Рассмотрим алгебраическое дополнение элемента матрицы имеющее вид

По теореме Бине-Коши

Всякий главный определитель отличный от нуля, соответствует остовному -дереву типа а всякий ненулевой главный определитель остовному -дереву типа Поэтому ненулевые элементы суммы, стоящей в правой части выражения (6.22), соответствуют остовным -деревьям типа Любое из этих ненулевых слагаемых равно определителю типа где F — усеченная матрица инциденций -дерева типа

Теорема 6.21. Пусть F — матрица инциденций -дерева усеченная по строке, которая соответствует вершине . Если ее строка соответствует вершине

Доказательство. Пусть — компоненты -дерева Допустим, что вершина входит в Переставляя некоторые строки и соответствующие столбцы, можно записать матрицу в виде

где 1) С — матрица степеней компоненты ; 2) D получается из матрицы степеней компоненты удалением строки и столбца, соответствующих вершине . Пусть строка k матрицы S соответствует вершине

Перестановка некоторых строк и соответствующих столбцов матрицы не меняет значений ее алгебраических дополнений. Поэтому

По теореме 6.18 все алгебраические дополнения матрицы С имеют одинаковое значение, равное числу остовов компоненты Поэтому алгебраическое дополнение элемента матрицы Более того, Поэтому

Теперь из выражений (6.23), (6.24) получаем

Доказательство этой теоремы приведено в работе [6.7]. Следующий результат получен Майедой:

Теорема 6.22. Для связного графа G справедливо равенство

Доказательство. Поскольку каждый ненулевой член суммы в правой части выражения (6.22) равен определителю типа описанного в теореме 6.21, получаем . Следовательно,

Для иллюстрации теорем 6.20 и 6.22 снова рассмотрим граф на рис. 6.8, а. Если А — матрица инциденций, усеченная по строке, соответствующей вершине то

Поэтому

Остовные -деревья типа образованы следующими множествами ребер: , а остовные деревья типа — множествами