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

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

Рассмотрим ориентированный граф . Если — непустое подмножество множества V, то напомним (глава 2), что множество дуг, соединяющих вершины является разрезом, обозначаемым Ориентацию можно принять как от вершины к вершине так и наоборот. Допустим, мы принимаем ориентацию от вершины к вершине . Тогда говорят, что ориентация дуги из соответствует ориентации разреза если дуга ориентирована от вершины из в вершину из V».

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

Строки матрицы называют векторами разрезов.

На рис. 6.2 представлены три разреза ориентированного графа из рис. 6.1, а. Штриховыми линиями в каждом случае показана ориентация разреза.

Рис. 6.2. Некоторые разрезы графа на рис. 6.1, а.

Соответствующая этим трем разрезам подматрица имеет вид

Соответствующую подматрицу в случае неориентированного графа можно получить, заменив в этой матрице «-1» на «+1».

Рассмотрим произвольную вершину и. Ненулевые элементы соответствующего вектора инциденций представляют инцидентные вершине v дуги. Эти дуги образуют разрез -Если принять ориентацию этого разреза от и к то из определений матриц разрезов и инциденций следует, что строка матрицы соответствующая разрезу совпадает со строкой матрицы соответствующей вершине и. Следовательно, — подматрица матрицы

Покажем, что ранги матриц одинаковы. Для этого докажем следующую теорему:

Теорема 6.3. Всякую строку матрицы разрезов можно выразить двумя способами в виде линейной комбинации строк матрицы . В обоих случаях ненулевые коэффициенты в линейной комбинации равны или —1.

Доказательство. Пусть разрез графа G на вершинах и дугах, а — соответствующий вектор разреза. Пусть Пусть, далее, вектор инциденций, соответствующий вершине

Не нарушая общности, допустим, что ориентация от вершины к вершине Для доказательства теоремы установим следующее равенство:

Пусть — вершины, инцидентные дуге, при этом она ориентирована от Поэтому

Сейчас возможны четыре случая:

Случай 1. поэтому

Случай 2. поэтому —1.

Случай 3. поэтому

Случай 4. поэтому

Используя выражение (6.6), легко показать, что в каждом из этих четырех случаев выполняется следующее равенство:

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

Для иллюстрации теоремы рассмотрим разрез 1 на рис. 6.2. Он разделяет вершины в и вершины в Ориентация разреза от к W Поэтому соответствующий вектор разреза можно выразить следующим образом: где — строки матрицы А (рис. 6.1, а).

Важным следствием из теоремы 6.3 является то, что Однако, поскольку — подматрица матрицы , то . Поэтому мы получаем, что

Теперь из теоремы 6.2 и следствия 6.2.1 вытекает следующая теорема:

Теорема 6.4. Ранг матрицы разрезов связного графа G на вершинах равен , т. е. рангу

Следствие 6.4.1. Ранг матрицы разрезов графа G на вершинах, имеющего компонент, равен , т. е. рангу этого графа.

Из этих выводов следует, что матрица инциденций является важной подматрицей матрицы разрезов Определим сейчас другую важную подматрицу матрицы

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

1) столбец соответствует ветви для ;

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

где U — единичная матрица порядка а столбцы ее соответствуют ветвям дерева Т.

Например, базисная матрица разрезающих множеств связного графа на рис. 6.1, а по отношению к остову имеет вид

    (6-9)

Из (6.8) следует, что ранг матрицы равен т. е. рангу матрицы Таким образом, всякий вектор разреза можно выразить в виде линейной комбинации базисных векторов разрезающих множеств.