6.9 Число ориентированных остовов в ориентированном графе

В этом разделе мы обсуждаем предложенный в работе Татта [6.8] метод определения числа ориентированных остовных деревьев, имеющих определенную вершину в качестве корневой. Этот метод является, по существу, обобщением метода нахождения остовов данного ориентированного графа, предложенного в теореме 6.17, и описывается исходя из определяемой ниже матрицы полустепеней захода.

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

Обозначим через матрицу, полученную удалением строки I и столбца из первоначальной матрицы К. Метод Татта основан на следующей теореме:

Теорема 6.23. Ориентированный без петель с является ориентированным деревом с корневой вершиной тогда и только тогда, когда его матрица полустепеней захода обладает следующими свойствами:

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

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

Поэтому

Матрицу К можно получить перестановкой некоторых строк и соответствующих столбцов первоначальной матрицы К. Такая перестановка не меняет значения определителя любой подматрицы матрицы К. Следовательно,

Достаточность. Пусть матрица полустепеней захода К графа G удовлетворяет обоим условиям теоремы. Если граф G не является ориентированным деревом, то по условию 1 и п. 5 теоремы 5.4 он содержит цикл С. Корневая вершина не может входить в цикл С, поскольку это означало бы или для некоторой другой вершины что противоречит условию 1. Аналогичным образом можно показать, что 1) цикл С должен быть контуром; 2) никакая дуга, не принадлежащая циклу С, не инцидентна никакой вершине того же цикла.

Рассмотрим теперь подматрицу матрицы К, состоящей из столбцов, которые соответствуют вершинам цикла С. Вследствие выполнения указанных свойств каждая строка матрицы соответствующая вершине цикла С, имеет точно одну ±1. Все другие строки — нулевые. Таким образом, сумма столбцов матрицы равна нулю. Другими словами, сумма соответствующих вершинам цикла С столбцов матрицы К равна нулю. Поскольку вершина не входит в цикл С, это справедливо также и для матрицы что противоречит условию 2. Это доказывает достаточность.

Применим метод Татта для нахождения числа ориентированных остовов ориентированного графа G с корневой вершиной . Допустим, что граф G не имеет петель.

Через для любого графам будем обозначать его матрицу полустепеней захода, а через К—матрицу, полученную из матрицы/С

заменой столбца на нулевой столбец. Набор подграфов G, в каждом из которых при , будем обозначать через . Очевидно, что Кроме того, матрица полустепеней захода любого удовлетворяет условию 1 теоремы 6.23.

Хорошо известно, что определитель квадратной матрицы является линейной функцией ее столбцов. Например, если — квадратная матрица со столбцами то

Используя линейность функции определителя и свойство равенства нулю суммы элементов любого столбца матрицы , запишем в виде суммы определителей, каждый из которых удовлетворяет условию 1 теоремы 6.23. Легко видеть, что между этими определителями и матрицами полустепеней захода подграфов из набора 5 существует взаимно-однозначное соответствие. Таким образом, Поэтому

Однако поскольку для всех , то . Из теоремы 6.23 следует, что каждый определитель в правой части суммы — ненулевой и равен 1 тогда и только тогда, когда соответствующий подграф из набора 5 является ориентированным деревом. Таким образом, мы доказали следующую теорему:

Теорема 6.24. Пусть К — матрица полустепеней захода ориентированного графа G без петель. Пусть строка этой матрицы соответствует вершине -графа G. Тогда число ориентированных остовов графа G, вершина которого является корневой, определяется следующим образом: , где — матрица, полученная первоначальной матрицы удалением строки и столбца.

Рис. 6.9.

Проиллюстрируем эту теорему, а также рассуждения, которые приводят к ее доказательству.

Рассмотрим ориентированный граф G, приведенный на рис. 6.9. Определим число ориентированных остовов с корневой вершиной

Матрица полустепеней захода К графа G имеет вид

Запишем в виде

Шесть определителей в правой части этого равенства соответствуют подграфам, порожденным следующими множествами дуг: Удаляя из этих определителей первые строки и столбцы, получим

Граф G имеет ориентированных остовов с корневой вершиной порождающихся следующими множествами дуг: