5.4. Матрица разрезов

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

При этом матрица разрезов имеет вид

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

Теорема 5.3. Матрица циклов С и матрица разрезов К любого графа удовлетворяют соотношению

Доказательство. Утверждение теоремы следует из того факта, что разрез всегда имеет четное число ребер (возможно 0), общих с каждым циклом.

Действительно, так как простой разрез разделяет граф на две части, он либо делит, либо не делит некоторый цикл. В последнем случае число общих ребер равно нулю, в предыдущем случае по теореме 1.8 разрез должен иметь четное число ребер, общих с данным циклом.

Упражнение 5.4. Показать, что если граф связен и не имеет точки сочленения, то его матрица разрезов содержит матрицу инцидеиций.

Замечание. Для плоских графов задача перечисления разрезов эквивалентна задаче перечисления циклов двойственного графа.

Рис. 5.5.

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

Воспользуемся следующей теоремой из теории матриц: ранг произведения двух матриц, первая из которых имеет размер (порядок) и ранг а вторая — размер и ранг удовлетворяет неравенству

Если эти матрицы ортогональны, то Возьмем в качестве первой матрицы матрицу инцидеиций, а в качестве второй — матрицу циклов. Так как ранг матрицы инцидеиций равен есть порядок матрицы циклов и матрицы инцидеиций, получаем, что ранг матрицы циклов удовлетворяет неравенству Однако ранее мы показали, что Следовательно, В результате мы доказали следующую теорему.

Теорема 5.4. Ранг матрицы циклов связного графа с ребрами и вершинами равен

Если граф содержит компонент, ранг матрицы циклов равен Это число известно также под названием цикломатического числа графа.

Упражнение 6.5. (см. скан)

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

Поясним первую часть замечания. Матрица инцидеиций покрывающего дерева является подматрицей матрицы инцидеиций всего графа. Она содержит все вершины (строки) и ребер (столбцов) дерева. Так как дерево является связным графом, его матрица имеет ранг Обратно, подматрица ранга соответствует строкам и столбцам. Так как столбцы линейно независимы, все вершины соединены и мы имеем дерево.

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

рис. 5.6. Жирными линиями показаны ребра выбранного дерева, хордами которого являются ребра и

Базисная матрица циклов, которая является подматрицей матрицы циклов, включает только циклы, определяемые хордами выбранного дерева. Ее можно записать в виде

или

где -единичная матрица, определяемая вхождением хорд в циклы, а соответствующая подматрица для ветвей.

Рис. 5.6.

Рис. 5.7.

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

Заметим, что —1 появляется там, где ориентация цикла противоположна ориентации дуги. Так как ранг матрицы инцидеиций А равен мы можем записать

где квадратная неособая подматрица размера Мы видели, что такие неособые матрицы

соответствуют деревьям. Следовательно, подматрица, соответствующая дереву, которое, например, может быть деревом, выбранным для построения С в рассмотренном примере.

Из теоремы 5.2 иуеем откуда следует, что где С — базисная матрица циклов. Последнее соотношение можно переписать в виде

где ребра А должны быть упорядочены так же, как в С. Перемножение дает

Учитывая, что неособая матрица, имеем

так по мод. 2. Таким образом, мы получили С из А.

Упражнение 5.6. Используя предложенный метод, получить С из А для графа, изображенного на рис. 5.6 Пусть первые два столбца соответствуют хордам. Заметим, что должна соответствовать дереву.

Базисная матрица для разрезов получается с помощью выделения дерева и поочередного рассмотрения каждой из его ветвей. Удаление некоторой ветви разбивает дерево на два поддерева. Соответственно разбиваются и вершины дерева. Удаленная ветвь и любые хорды, общие обеим поддеревьям, образуют базисный разрез. (В ориентированном графе —1 указывает ориентацию, противоположную ориентации ветви.)

(см. скан)

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

где подматрица, соответствующая хордам, а единичная подматрица, соответствующая ветвям. Из

соотношения ортогональности, которое существует между матрицей циклов и транспонированной матрицей разрезов, имеем Таким образом,

следовательно, Отсюда заключаем, что так как мод. 2.

Упражнения

(см. скан)