Лекция 10.

Сечения графа

Строки матрицы А₀ содержат информацию о ветвях, инцидентных соответствующим вершинам. Образуем вектор токов ветвей

В соответствии с первым законом Кирхгофа алгебраическая сумма токов ветвей, инцидентных данной вершине равна нулю. Следовательно, произведение вектора-строки матрицы А₀ на вектор токов ветвей I_в также равен нулю. Отсюда получаем

(1.91)

— обобщенное выражение первого закона Кирхгофа для υ — 1 вершин графа схемы. Дальнейшее обобщение

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

Полноту и независимость уравнений по первому закону Кирхгофа обеспечивает надлежащий выбор совокупности независимых сечений. Они могут быть образованы с помощью фундаментального дерева, т. е. связного подграфа, не содержащего контуров и включающего в себя все v вершин данного графа схемы. Очевидно, такое дерево состоит из ν=υ—1 ветвей. Варианты фундаментальных деревьев для графа рис. 1.29,а (υ = 7) приведены на рис. 1.32 (ветви деревьев показаны жирными линиями). Они иллюстрируют два различных подхода к образованию фундаментального дерева.

При первом подходе фундаментальное дерево строят на множестве v вершин графа схемы без учета структуры последнего. В этом случае дерево представляет собой самостоятельный граф, совмещаемый с графом схемы в его вершинах (рис. 1.32,а). Можно показать [77, 108, 181], что общее число различных деревьев (без учета направлений их ветвей) на множестве v вершин выражается формулой

(1.92)

Величина ξ — это большое число даже для сравнительно малых значений v. Так, для графа с четырьмя узлами имеется 16 вариантов фундаментальных деревьев, а с семью узлами — уже 16807. Число всевозможных фундаментальных деревьев еще больше возрастает, если учитывать и различия в направлении ветвей. Поскольку для каждой υ—1 ветви дерева имеется два различных направления, то

(1.93)

При υ = 4 таких деревьев 128, а при υ = 7 их число уже превышает миллион. Таким образом, имеется огромное число различных вариантов выбора фундаментального дерева.

При втором подходе к выбору фундаментального дерева в качестве его ветвей выбирают ветви данного графа, т. е. фундаментальное дерево является деревом графа (рис. 1.32,б). Ветви графа, не вошедшие в дерево, называются хордами, совокупность которых образует дополнение дерева.

Число всевозможных деревьев графа определяется значением определителя квадратной матрицы Т ν-ro порядка, диагональными элементами которой являются степени v вершин t_ii графа, а недиагональными элементами — взаимные степени t_ij тех же v вершин со знаком минус [244]:

(1.94)

Если различать деревья и по направлениям их ветвей, то число различных деревьев графа

(1.95)

Например, для графа на рис. 1.29,а

Как видим в рассматриваемом примере графа с семью вершинами число деревьев графа оказалось меньше числа фундаментальных деревьев примерно в 50 раз. Однако такое соотношение получается не всегда. Число деревьев графа зависит от степени его заполнения, т. е. от отношения числа ветвей к числу вершин. Если граф представляет полный многоугольник, в котором каждая пара вершин связана одной ветвью, то ξ = ξ₀, т. е. число фундаментальных деревьев равно числу деревьев графа. При наличии параллельных ветвей число деревьев графа может быть даже больше, чем число деревьев, построенных на множестве всех его вершин.

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

(1.96)

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

(1.97)

Совокупность фундаментальных деревьев частей несвязного графа образует его фундаментальный лес.

Матрица сечений

Матрицу сечений П получают по правилу, аналогичному для структурной матрицы. Ее строки соответствуют сечениям, а столбцы — ветвям графа, так что размер матрицы (vxl). Элемент π_ij матрицы П равен +1 (—1), если j-я ветвь инцидентна i-му сечению и направлена с ним согласно (противоположно), и 0, если /-я ветвь не инцидентна i-му сечению. Так, для сечений, определяемых фундаментальным деревом, по рис. 1.32,а получаем

Если какая-либо ветвь графа пересекается сечением четное число раз, то она не является инцидентной этому сечению (например, ветвь графа 8 пересекается сечением 3 дважды, поэтому π₃₈=0). Инцидентная данному сечению ветвь может пересекаться им нечетное число раз.

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

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

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

(1.98)

где 1 — единичная матрица ν-ro порядка, а π — матрица главных сечений для хорд. Для графа рис. 1.32,б

Матрица я полностью определяет матрицу главных сечений П, причем ее размер [νX(l—ν)].

Дерево графа и матрицу главных сечений можно получить на основе структурной матрицы А₀ по формальному алгоритму, который поясним на примере графа рис. 1.29,а. Выбираем в первом столбце матрицы А₀ первый ненулевой элемент и соответствующую этому элементу строку прибавим или вычтем из строк, соответствующих ненулевым элементам этого же столбца так, чтобы образовался столбец с единственным ненулевым элементом. Если этот элемент равен —1, меняем знаки в соответствующей ему строке на обратные и переставляем эту строку на первое место. После выполнения этих операций над записанной ранее матрицей А₀ получаем

Наличие единственного ненулевого элемента ( + 1) в первом столбце указывает на то, что первая ветвь включена в дерево графа. Далее, выбираем ненулевой элемент во втором столбце ниже первой строки и выполняем аналогичные операции. После того, как во втором столбце все элементы, кроме выбранного, обращены в нулевые, переставляем строку, соответствующую ненулевому элементу во втором столбце, на второе место (в дерево графа включается вторая ветвь):

Продолжая аналогичные операции над третьим, четвертым и пятым столбцами, получаем

Дальнейший процесс должен был бы относиться к шестому столбцу. Но в этом столбце ниже сформированных ранее пяти строк отсутствуют ненулевые элементы, что указывает на недопустимость включений ветви 6 в дерево совместно с ветвями 1—5 (действительно, как видно из рис. 1.29,а, ветвь 6 образует контур с ветвями 2 и 3). При такой ситуации перестанавливаем соседние столбцы 6 и 7 и соответствующие операции выполняем над столбцом 7, после чего приходим к матрице главных сечений (процесс заканчивается, так как в левой части матрицы образовалась единичная субматрица v-ro порядка):

Таким образом, дерево образовано из ветвей 1, 2, 3, 4, 5 и 7, а ветви 6, 8, 9, 10 и 12 являются хордами. Соответствующие сечения для рассмотренного графа показаны на рис. 1.32,в.