Глава 5. МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ

5.1. Введение

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

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

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

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

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

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

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

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

Отметим, что с понятием матриц тесно связано понятие векторного линейного пространства, базиса и линейной комбинации векторов.

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

Для существования векторного пространства, для любых векторов из этого пространства и при любых числах должны выполняться следующие аксиомы.

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

3. для всех х, где обозначает нулевой вектор.

4. Каждый вектор х имеет противоположный вектор у такой, что

Должны выполняться следующие аксиомы умножения на число.

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

Два векторных пространства называются изоморфными, если между их элементами можно установить взаимно однозначное соответствие, которое сохраняет операцию сложения и умножения на число, т. е. если элементы V, а соответствующие элементы то соответствует аналогично, соответствует если соответствует произвольное число.

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

0 или 1 в зависимости от четности или нечетности числа общих дуг в подмножествах, соответствующих этим векторам.

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

Аналогичное утверждение справедливо и для векторов, соответствующих разрезам.

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

На этой проблеме мы остановимся очень кратко, так как для глубокого ее рассмотрения необходим материал, выходящий за рамки этой книги.