Пространство остовных подграфов

Зафиксируем некоторое множество и рассмотрим множество всех графов с множеством вершин . Буквой будем обозначать пустой граф из этого множества: .

Для графов и из определим их сумму по модулю 2 как граф , где обозначает симметрическую разность множеств и . Иначе говоря, ребро принадлежит графу тогда и только тогда, когда оно принадлежит одному из графов и . Пример показан на рис. 1.

=

Рис. 1.

Введенная операция обладает следующими свойствами:

1°. Коммутативность: .

2°. Ассоциативность: .

3°. .

4°. .

Отсюда следует, что множество относительно операции образует абелеву группу. Нейтральным элементом («нулем») этой группы служит граф , а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным и заданными графами и имеет единственное решение . Благодаря свойству ассоциативности в выражении вида можно не использовать скобки для указания порядка действий. Очевидно, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству графов .

Рассмотрим множество из двух элементов {0, 1}. Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы:

.

Множество с введенными операциями сложения графов и умножения на элементы поля является линейным векторным пространством.

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

Остовному подграфу можно поставить в соответствие двоичное слово , в котором нули указывают, какие ребра удалены, а единицы – какие оставлены: