Матрицы, ассоциированные с графом

В этом параграфе вводятся три матрицы, связанные с произвольным графом, и еще одна матрица, связанная с двудольным графом.

На всем протяжении этой книги элемент матрицы M, занимающий позицию (i, j), обозначается символом M_ij. Матрица, каждый элемент которой равен 0 или 1, называется бинарной.

Пусть G — помеченный граф порядка n, VG ={1, 2,..., n }. Определим бинарную n*n -матрицу A=A (G), положив

A (G)называется матрицей смежности графа G. Это симметрическая матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.

Очевидно, что соответствие G ® A (G)определяет биекцию множества помеченных графов порядка n на множество бинарных симметрических n * n -матриц с нулевой диагональю.

Аналогично определяются матрицы смежности А мульти- и псевдографов: A_ij равно числу ребер, соединяющих вершины i и j (при этом петля означает два ребра).

Так же определяется матрица смежности A (G)ориентированного графа G:

Здесь AG — множество дуг орграфа G.

Очевидно, что любая квадратная бинарная матрица является матрицей смежности некоторого ориентированного графа. На рис. 6.1 изображен ориентированный граф с матрицей смежности.

Абстрактный граф приводит к различным матрицам смежности в зависимости от нумерации вершин. Посмотрим, как связаны между собой эти матрицы. Пусть G и H — помеченные графы порядка n и G H. Это означает, что G и H различаются только нумерацией вершин, т. е. существует подстановка s на множестве вершин, сохраняющая смежность: вершины u и v тогда и только тогда смежны в G, когда их образы s (u)и s (v)смежны в Н. Положив A (G) = A, B (G) = B, получаем

B_{s (i) s (j)} =A_ij, i = , j = . (1)

Тем самым доказано

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

Это утверждение верно также для мультиграфов, псевдографов и ориентированных графов.

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

Пусть s — произвольная подстановка, действующая на множестве {1, 2,..., n }. Определим бинарную n ´ n- матрицу S, положив

Очевидно, что в каждой строке и в каждом столбце матрицы S содержится ровно по одной единице и det S = ±1. С помощью прямых вычислений проверяется, что

(SAS^-1) _ij =

для любой n ´ n -матрицы А. Равенства (1) теперь можно переписать в виде одного матричного равенства В = SAS ^-1.

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

Как известно из линейной алгебры, вещественная симметрическая матрица (а матрицы смежности графов являются таковыми) определяется своим спектром с точностью до подобия. Тем не менее из совпадения характеристических полиномов графов отнюдь не следует изоморфизм этих графов. Неизоморфные графы с равными характеристическими полиномами называются коспектральными. Например, два графа, изображенные на рис. 6.2, коспектральны, их характеристический полином равен x³ (x² — 4).

Глубокие свойства и применения спектра графа рассмотрены в книге [31].

С двудольным графом удобно связать еще одну матрицу. Разбиение множества вершин двудольного графа на доли определяется этим графом неоднозначно. Часто такие графы рассматривают вместе с фиксированными разбиениями на доли. Если G — двудольный граф с долями X и Y и множеством ребер E, то пишут G = (X, Y, E). Итак, пусть G = (X, Y, E), |X| = m, | Y |= n. Занумеруем вершины доли X числами 1, 2,..., т, а доли Y —символами y ₁, y ₂,..., y _n. Определим бинарную m ´ n -матрицу M = M (X, Y, E), положив

Матрицу M назовем приведенной матрицей смежности двудольного графа.

Возвратимся к произвольным графам. Вторая из матриц, вводимых в общей ситуации, — матрица Кирхгофа. Пусть G — помеченный граф порядка n, VG = {1, 2,..., n }. Определим n ´ n -матрицу B = B (G), положив

Матрица B (G)называется матрицей Кирхгофа графа G. Сумма элементов в каждой строке и в каждом столбце этой матрицы равна нулю.

Утверждение 6.1 останется верным, если вместо матриц смежности рассматривать матрицы Кирхгофа. Сохраняется и прежнее доказательство.

Во второй главе этой книги используется следующее

Утверждение 6.2. Пусть B — произвольная числовая n ´ n-матрица,
в каждой строке которой и в каждом столбце сумма элементов равна нулю:

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

> Очевидно, что rank B < п. Если rank B< n — 1, то алгебраические дополнения всех элементов этой матрицы равны 0. Пусть rank В — n — 1 и С — присоединенная матрица для матрицы B, т. е. элемент C _ijравен алгебраическому дополнению A_ij элемента B_ij в матрице B, i = , j = . Известно, что BC = (det B) E, где E — единичная матрица. В наших условиях det B = 0, BC = 0 — нулевая матрица. Следовательно, для столбца матрицы C с номером j, j = , верны равенства

B_{i 1} C _{1 j} + B_{i 2} C _{2 j} +... + B_inC_ni = 0, i = ,

т.е.

B_{i 1} A_{j 1}+ B_{i 2} A_{j 2}+... + B_inA_jn = 0, i = .

Эти равенства можно рассматривать как систему линейных однородных уравнений с матрицей B относительно неизвестных A_{j 1}, A_{j 2},..., A_jn. Так как rank B = п- 1, то все решения системы пропорциональны. Но вектор (1,..., 1) удовлетворяет системе, поэтому

A _j1 =A _j2 =...= A _jn, j= .

Учитывая, что CB =0, аналогично получаем

A _{1 i} = A _{2 i} =... = A_ni, i = .

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

A_ij = А_kl i, j, k, l = . <

Наконец, определим матрицу инцидентности графа. Пусть G- (n, m)-граф, VG = {1, 2,..., n }, EG = { e ₁, e ₂,..., e _m}. Определим бинарную n ´ m -матрицу I = I (G)условиями:

Матрица I называется матрицей инцидентности графа G. В каждом ее столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G ® I (G)является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество n ´ m -матриц, удовлетворяющих описанным условиям.

Для ориентированных графов определение матрицы инцидентности I видоизменяется:

Аналогично утверждению 6.1 получается

Утверждение 6.3. Графы (орграфы) изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.

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

Утверждение 6.4. Если B — матрица Кирхгофа графа G, a I — матрица инцидентности какой-либо его ориентации H (нумерация вершин в H та же, что и в G), то B = II^T (здесь T — операция транспонирования матрицы).