3.05.7. Линейное пространство графа

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

Нетрудно убедиться, что эти операции удовлетворяют всем аксиомам линейного пространства:

1. ;

2. ;

3. существует нулевой элемент — Æ: ;

4. для каждого существует обратный элемент : ;

5. ;

6. ;

7. ;

8. .

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

Выделим следующие два подпространства этого графа.

A) Подпространство циклов: множество всех циклов графа , включая и совокупности непересекающихся циклов (как одно целое — один элемент линейного пространства), а также — пустое множество (в качестве нулевого элемента).

B) Подпространство разрезов: множество разделяющих множеств графа , включая Æ.

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

< Предыдущая		Следующая >