4.3. Векторное пространство графа

В этом разделе мы рассмотрим соответствие между графом и векторным пространством, а также определим два важных подпространства векторного пространства.

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

1) — замкнутое множество по отношению к операции 0;

2) — ассоциативная операция;

3) — коммутативная операция.

Далее, для любого элемента в наборе справедливы равенства

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

Пусть — операция умножения над элементами — определяется следующим образом:

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

[Отметим, что 1 — нулевой мультипликативный элемент поля GF (2).] Таким образом, — векторное пространство над полем . Если , то подмножества образуют базис для . Следовательно, размерность равна , т. е. числу ребер в графе G. Из того, что каждый реберно-порожденный подграф графа G соответствует единственному подмножеству множества Ем что кольцевой сумме любых -реберно-порожденных подграфов по определению (гл. 1) можно поставить в соответствие кольцевую сумму двух соответствующих множеств ребер, следует, что множество всех реберно-порожденных подграфов графа G является векторным пространством над GF (2), если операция умножения определена следующим образом: для любого реберно-порожденного подграфа G, графа — нуль-граф, не имеющий ни вершин, ни ребер. Это векторное пространство также обозначим символом Заметим, что включает в себя нуль-граф 0. Из приведенных рассуждений вытекает следующая теорема:

Теорема 4.2. Для графа G пространство является -мерным векторным пространсшом над полем GF (2).

Поскольку в этой главе мы рассматриваем только реберно-порожденные подграфы, то будем называть их просто подграфами, опуская слово «реберно-порожденные». Однако мы можем по-прежнему использовать это уточнение в некоторых местах, чтобы подчеркнуть реберно-порожденную природу рассматриваемых подграфов. Теперь покажем, что следующие подмножества являются подпространствами: — множество всех циклов (включая и нуль-граф 0) и объединений реберно-непересекающихся циклов графа — множество всех разрезающих множеств (включая и нуль-граф 0) и объединений реберно-непересекающихся разрезающих множеств графа.

Если мы покажем, что являются замкнутыми по отношению к операции сложения 0, то из этого и будет следовать, что — подпространства.

Теорема 4.3. Множество всех циклов и объединений реберно-непересекающихся циклов графа G является подпространством векторного пространства графа

Доказательство. По теореме 3.1 граф можно представить в виде объединения реберно-непересекающихся циклов тогда и только тогда, когда каждая вершина в графе имеет четную степень. Следовательно, можно рассматривать как множество всех реберно-порожденных подграфов графа G, все вершины которого имеют четную степень.

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

Рассмотрим любую вершину v, принадлежащую Очевидно, эта вершина должна присутствовать по крайней мере в одном из подграфов: или Обозначим через множество ребер, инцидентных вершине v в подграфе а через — число ребер в множестве Таким образом, — степень вершины v в подграфе . Заметим, что числа — четные и одно из них может равняться нулю. Следовательно, Поскольку получаем, что Поэтому Из этого равенства видно, что является четной степенью, потому что обе степени — четные, другими словами, вершина v в имеет четную степень. А так как вершину v мы выбрали произвольно, то принадлежит W с, и теорема доказана. Назовем W с подпространством циклов графа

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

Покажем теперь, что множество всех разрезающих множеств и объединений реберно-непересекающихся разрезающих множеств графа G является подпространством пространства По теореме 2.7 разрез является разрезающим множеством или объединением нескольких реберпо-непересекающихся разрезающих множеств. Таким образом, каждый разрез графа G принадлежит множеству Докажем, что каждый элемент последнего является разрезом. Одновременно покажем, что — подпространство пространства

Теорема 4.4. Сумма двух любых разрезов графа G также является разрезом графа G.

Доказательство. Рассмотрим два любых разреза: графа Е). Заметим, что . Пусть .

Рис. 4.1. а — граф 0; б — подграф С, графа G; в — подграф графа G: г — подграф графа

Нетрудно видеть, что множества А, В, С, D взаимно не пересекаются. Тогда

Следовательно, получим

Поскольку можно записать

Из того, что взаимно не пересекаются и вместе включают в себя все вершины V, следует, что является разрезом в графе G. Теорема доказана. Так как кольцевая сумма двух реберно-непересекающихся графов совпадает с их объединением, имеет место следующее следствие:

Следствие 4.4.1. Объединение любых двух реберно-непересекающихся разрезов графа G также является его разрезом. Поскольку разрезающее множество является разрезом, то из следствия 4.4.1 очевидно, что — множество всех разрезов графа G. Далее, по теореме 4.4 множество является замкнутым по отношению к операции кольцевой суммы. Таким образом, имеет место следующая теорема:

Теорема 4.5. Множество всех разрезающих множеств и объединений реберно-непересекающих множеств графа G является подпространством векторного пространства графа G. Назовем подпространством разрезов графа G. В качестве примера, иллюстрирующего теорему 4.5, рассмотрим разрезы графа G (рис. 4.2): , где

Тогда .

Рис. 4.2.

Если то множество можно записать (как было доказано в теореме 4.4) в таком виде: