6.10. Матрица смежности

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

Например, граф, изображенный на рис. 6.10, имеет следующую матрицу смежности:

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

Теорема элемент матрицы равен числу ориентированных маршрутов длины из вершины в вершину

Доказательство. Доказательство проводим индукцией по . Очевидно, что результат справедлив при

Рис. 6.10.

В качестве индуктивного предположения допустим, что теорема верна для Тогда

любого k соответствующий член суммы определяет число ориентированных маршрутов длины из вершины - в вершину последней дугой которых является . Однако число ориентированных маршрутов длины - в (число ориентированных маршрутов длины из - в последняя дуга которых идет из что доказывает теорему для

Рассмотрим, например, третью степень матрицы М графа, изображенного на рис. 6.10:

Элемент (1,4) этой матрицы определяет число ориентированных маршрутов длины три из вершины в вершину Этими маршрутами являются

Рассмотрим теперь важный результат, полученный в работе [6.9], который служит основой подхода сигнальных графов к решению линейных алгебраических уравнений. Для этого нам необходимо ввести несколько новых определений.

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

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

начальной подстановке требуется четное число перестановок (обмена местами) ее элементов. Аналогично определяется нечетная подстановка. подстановку 1 3 4 2. К виду

Рис. 6.11. Два -фактора графа рис. 6.10.

Рассмотрим, например, приводит следующая последовательность перестановок: 1) поменять местами 3 и 2; 2) поменять местами 3 и 4. Следовательно, эта подстановка является четной.

Теорема 6.26. Пусть — 1-факторы ориентированного графа О на вершинах. Пусть — число контуров матрица смежности графа G, Тогда

Доказательство. По определению

где

1. — подстановка целых чисел

2. если — четная подстановка, в противном случае

3. Сумма берется по всем подстановкам целых чисел

Ненулевой элемент ,-соответствует множеству дуг (и, ), Каждая вершина появляется в этом множестве дважды: один раз как первый элемент, в другой — как второй элемент в некоторых упорядоченных парах. Это означает, что полустепени захода и исхода любой вершины подграфа, порожденного дугами равны 1. Таким образом, всякий ненулевой элемент суммы выражения (6.25) соответствует -фактору графа G. Обратно: всякий -фактор соответствует ненулевому элементу

Например, -фактор, приведенный на рис. 6.11, б, соответствует элементу

Теперь необходимо зафиксировать знак Пусть С — контур в -факторе, соответствующем Пусть контур состоит из со дуг

Начальные вершины этих дуг образуют последовательность а их конечные вершины —

Легко видеть, что для приведения последовательности к последовательности достаточно совершить перестановку.

Пусть в -факторе, соответствующем имеется L контуров, а их длины равны Тогда для приведения последовательности

к виду необходимо совершить перестановок. Поэтому

Подводя итоги, заключаем:

1) Каждый ненулевой элемент соответствует -фактору - графа G (заметим, что значение этого элемента равно 1);

2) где L; — число контуров в 1-факторах

Таким образом, выражение (6.25) сводится к следующему

Рассмотрим, например, -факторы, приведенные на рис. 6.11. Им соответствуют следующие значения Следовательно, определитель матрицы смежности графа на рис. 6.10 равен . В этом легко убедиться путем непосредственного разложения определителя.

Пусть каждой дуге ориентированного графа G присвоен вес Определим матрицу смежности графа G следующим образом:

Определим весовое произведение подграфа Н графа G как произведение весов всех дуг подграфа . Если последний не имеет дуг, т. е. подграф является пустым, то пусть Теперь легко получить следующее обобщение теоремы 6.26:

Теорема 6.27. Определитель матрицы взвешенного графа G на вершинах определяется следующим выражением:

где -фактор графа G, a — число контуров в подграфе