6.7. Число остовов

В этом разделе мы выведем формулу для определения числа остовов связного графа. Эта формула основана на теореме 6.9 утверждением теории матриц, известно под названием «теорема Бине — Коши».

Главным определителем матрицы называется определитель максимального порядка. Пусть Р — матрица порядка — матрица порядка . Главные определители матриц Р и Q имеют порядок . Если главный определитель матрицы Р состоит из столбцов матрицы Р, то соответствующий главный определитель матрицы Q — из строк матрицы матрицы Q. Например, если

то для главного определителя

матрицы Р определитель

является соответствующим главным определителем матрицы

Теорема 6.16 (Бине—Коши). Если Р — матрица порядка — мат рица порядка , то . (Произведение соответствующих главных определителей ).

Доказательство этой теоремы можно найти в работе [6.1].

Если в качестве иллюстрации к теореме Бине—Коши, как и ранее, взять матрицы Р и Q, то получим

Теорема 6. 17. Пусть G — связный неориентированный граф, А — усеченная матрица инциденций ориентированного графа, полученного присвоением ребрам графа G произвольной ориентации. Тогда , где — число остовов графа

Доказательство. По теореме Бине—Коши

Заметим, что соответствующие главные определители А и А имеют одинаковое значение, равное 1, —1 или 0 (теорема 6.13). Поэтому каждое ненулевое слагаемое в правой части суммы (6.20) имеет значение 1. Кроме того, главный определитель А не равен нулю тогда и только тогда, когда дуги, соответствующие его столбцам, образуют остов.

Таким образом, между ненулевыми элементами правой части суммы (6.20) и остовами графа G существует взаимно-однозначное соответствие, что доказывает теорему.

Рассмотрим в качестве примера граф G, представленный на рис. 6.8, а. Ориентированный граф, полученный в результате присвоения произвольной ориентации ребрам графа G, представлен на рис. 6.8, б. Его матрица инциденций, усеченная по строке, которая соответствует вершине имеет вид

Следовательно,

Граф G имеет восемь остовных деревьев:

Пусть — вершины неориентированного графа G без петель.

Рис. 6.8.

Матрицей степеней графа G называется матрица порядка элементы которой определяются следующим образом:

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

Из определения матрицы степеней К ясно, что сумма всех элементов в ее любой строке равна нулю. Аналогично равна нулю сумма всех элементов в ее любом столбце. Квадратная матрица, обладающая такими свойствами, называется матрицей с равными алгебраическими дополнениями [6.2]. Таким образом, из теоремы 6.17 мы получаем следующий результат, принадлежащий Кирхгофу [6.3]:

Теорема 6.18. Все алгебраические дополнения матрицы степеней связного неориентированного графа имеют одинаковое значение, равное числу остовов графа

Теперь получим формулу определения числа различных деревьев, которые можно построить на помеченных вершинах. Очевидно, это число равно числу остовных деревьев полного графа на помеченных вершинах.

Теорема 6.19 (Кэли). Существует помеченных деревьев на 2 вершинах.

Доказательство. Матрица в случае полного графа имеет вид

По теореме 6.17 определитель этой матрицы дает число остовов графа являющееся числом помеченных деревьев на вершинах.

Для вычисления вычтем первый столбец матрицы из всех других столбцов той же матрицы. Тогда мы получим

Теперь прибавим первую строку получившейся матрицы к каждой оставшейся строке и получим

Определитель этой матрицы равен Это доказывает теорему, поскольку сложение строк и столбцов не меняет значения определителя.

Известно несколько доказательств теоремы Кэли