§ 4.13. Векторные пространства,
связанные с графами
Рассмотрим алгебраическую систему 2=с двухместными операциями кольцевого сложения⊕ и умножения ⊙, задаваемыми следующими правилами: 0⊕0=1⊕1=0, 1⊕0=0⊕1=1, 0⊙0=0⊙1=1⊙0=0, 1⊙1=1. Система 2 является булевым кольцом (см.§2.6) и, более того, образует поле.
Пусть G= связный неорграф, имеющий n вершин и m ребер . Произвольному множеству реберA R поставим в соответствие вектор =, положив
Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора нулей и единиц найдется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества реберR и множеством всех наборов длины m, состоящих из нулей и единиц: P (R)↔m. Пусть =и=()- наборы (векторы) изm. Определим сложение векторов с помощью соотношения ⊕=(⊕, … ,⊕)по правилам, определенным в поле 2. Кроме этого, определим произведение векторов на элементы , положив λ⊙ =(λ⊙, … ,λ⊙). Множество векторовm с операциями сложения ⊕ и умножения ⊙ на элементы поля 2 образует линейное пространство над полем 2. Это пространство обозначим через (2).
Отметим, что сложение ⊕ векторов исоответствует кольцевой сумме множеств реберA и B, представляемых этими векторами. Действительно, равенство выполняется тогда и только тогда, когда=1,(т.е.или,(т.е.. Следовательно, сумме⊕соответствует множество (A\B)(B\A)=A⊕B.
Внутреннее произведение векторов =и=(определяется соотношением (=Равенство (=0 означает, что четное число произведений⊙равно 1. Для таких произведений =1,и, следовательно, соответствующие векторамимножества реберA и B имеют четное число общих ребер.
Множество ребер A называется границей (кограницей), если A есть объединение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A1⊕ A2 также является границей (кограницей). Следовательно, множества VГ=соответствует некоторойиVK =векторсоответствует некоторойобразуют линейные подпространства пространстваVm 2).
Теорема 4.13.1. 1. Если фундаментальное множество циклов графа G, то множество 𝔅С = векторов, соответствующих фундаментальным циклам, образует базис подпространства границVГ.
2. Если фундаментальное множество коциклов графа G, то множество 𝔅K= векторов, соответствующих фундаментальным разрезам, образует базис подпространства кограницVK.
Следствие 4.13.2. 1. Размерность dim VГ подпространства границ VГ равна цикломатическому числу , а размерностьdim VK подпространства кограниц VK равна корангу .
2.Любой цикл ( коцикл ) в графе можно представить в виде кольцевой суммы некоторых фундаментальных циклов (разрезов).
Два подпространства V1 и V2 векторного пространства Vm (2) называются ортогональными (V1 V2), если для любых векторов V1 и V2 их внутреннее произведение (,) равно 0.
Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K имеет четное число общих ребер, т.е. для соответствующих векторов и их внутреннее произведение(,) равно нулю. В частности, для любых векторовC и K справедливо (,)=0. Так как множестваC и K образуют базисы подпространств VГ и VK, то VГ VK.
Отметим также, что при умножении матрицы фундаментальных циклов C на транспортированную матрицу фундаментальных разрезов KT в поле 2 строка умножается на столбецпо правилу произведения и (,)=0. Это означает чтоCKT=0, а также KCT=0.
У п р а ж н е н и е. Проверить, что для матриц C и K из примеров 4.11.1 и 4.12.1 справедливо CKT=0.