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

Вводные замечания

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ

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

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

Матрицы перемножаются и складываются как обычно, однако результат всегда записывается по модулю 2.

При описании ориентированных графов элементов 0 и 1 оказывается недостаточно, так как дуга может быть инцидентна данной вершине и направлена к ней, инцидентна и направлена от нее, или не инцидентна вершине. Поэтому для обозначения ориентированной инцидентности или ее отсутствия воспользуемся символами 1,-1, 0. Здесь мы уже не можем пользоваться приведением по модулю 2 и должны рассматривать матрицы с целочисленными элементами.

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

Пусть G -граф, имеющий n вершин и m ребер. Графу G можно сопоставить матрицу инциденций размером n ´ m, строки и столбцы которой соответствуют вершинам и ребрам графа соответственно. Элемент матрицы a _ij принимает значение 1 или 0 в зависимости от того, инцидентно j -е ребро i -й вершине или нет. Для петли все элементы столбца считаются равными 0. Например, двухкомпонентный граф, показанный на рис. 7.1, имеет следующую матрицу инциденций:

Рис. 7.1.

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

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

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

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

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

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

Рис. 7.2.

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

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