6. Матрицы графов

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

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

6.1. Матрица инциденций

Рассмотрим граф G без петель на вершинах и ребрах. Матрица инциденций графа G имеет строк (по одной на каждую вершину) и столбцов (по одному на каждую дугу). Элемент матрицы определяется следующим образом:

Строки матрицы называют векторами инциденций графа G. На рис. 6.1, а и б представлены два графа со своими матрицами инциденций.

Рис. 6.1. а — ориентированный граф Q и его матрица инциденций; б — неориентированный граф G и его матрица инциденций.

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

Подматрицу А матрицы на строке называют усеченной матрицей инциденций. Если вершина соответствует строке матрицы отсутствующей в подматрице А, то говорят, что А — матрица инциденций, усеченная по строке, — соответствует данной вершине. Заметим, что

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

Теорема 6.1. Определитель любой усеченной матрицы инциденций дерева равен ±1.

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

Любая усеченная матрица инциденций дерева на двух вершинах является матрицей размерности 1X1, единственный элемент которой равен ±1. Следовательно, теорема верна для Заметим, что для она уже не выполняется.

Пусть теорема выполняется для . Рассмотрим дерево Г на вершине. Пусть А — усеченная матрица инциденций дерева Т. По теореме 2.5 оно имеет по крайней мере 2 висячие вершины. Пусть вершина дерева Т является висячей, а матрица А усечена не по строке, соответствующей этой вершине. Если этой вершине инцидентна дуга, то

Разлагая определитель А по строке, получаем

где А получается из А удалением строки и столбца.

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

В совокупности с выражением (6.2) это доказывает теорему для

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

Так как получаем следующую теорему:

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

Непосредственным следствием данной теоремы является следующее утверждение:

Следствие 6.2.1. Если граф на вершинах имеет компонент, то ранг его матрицы инциденций равен т. е. рангу графа