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

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

Рис. 5.1.

Элемент мат рицы принимает значение 1 или в зависимости от того, инцидентно ребро вершине или нет. Для петли все элементы столбца считаются равными 0.

Например, двухкомпонентный граф, показанный на рис. 5.1, имеет следующую матрицу инцидеиций:

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

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

При соответствующей нумерации ребер и вершин графа каждая его компонента соответствует подматрице матрицы инцидеиций, которая в этом случае имеет блочную структуру следующего вида:

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

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

(см. скан)

Теорема 5.1. Ранг матрицы инцидеиций -компонентного графа с вершинами равен (подразумевается, что арифметические операции производятся по модулю 2).

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

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

Существует другой метод, с помощью которого можно показать, что ранг точно равен —1. Начнем с

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

Рис. 5.2.

Как указывалось выше, элементы матрицы инцидеиций ориентированного графа принимают значения 0, 1, —1. Элемент равен нулю, если вершина не инцидентна дуге, если дуга ориентирована от вершины, и —1 в противном случае. Таким образом, граф, показанный на рис. 5.2, имеет следующую матрицу инцидеиций:

Матрица ориентированного графа с вершинами и компонентами также имеет ранг Термин ранг относится к графу, независимо от того, ориентирован он или нет, и характеризует ранг матрицы инцидеиций.

(см. скан)