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) в таком виде: