10.1.2. Независимые множества циклов и коциклов

Рассмотрим операцию 0 сложения по модулю 2 или симметрической разности над множествами ребер:

m! еМ₂: = {е (е &М_г&е<£ M₂)V(e ф Mi&e б М₂)}.

Множество М называется зависимым или линейной комбинацией множеств {Мг}?₌₁, если

Множество разрезов {5^}"₌₁ называется независимым, если ни один из разрезов Si не является линейной комбинацией остальных.

Множество разрезов {5^}"₌₁ называется независимым, если ни один из разрезов Si не является линейной комбинацией остальных.

ЗАМЕЧАНИЕ-

Множество подмножеств ребер данного графа образует векторное пространство над дво­ичной арифметикой. Действительно, ф — ассоциативная и коммутативная операция. Да­лее Мф0=0фМ=Ми каждый элемент является своим обратным: М ф М = 0. Та­ким образом, подмножества ребер образуют абелеву группу относительно симметричной разности. Далее определим операцию умножения вектора на скаляр: ОМ : = 0, 1М : = М. Легко видеть, что аксиомы векторного пространства выполнены. Введенные здесь поня­тия линейной комбинации, зависимости и независимости являются частными случаями одноименных понятий из разделов 2.5 и 2.7.