4.6. Ортогональность подпространств циклов и разрезов

Согласно теореме 4.1, каждое -мерное векторное пространство над полем F изоморфно векторному пространству всех -векторов над тем же полем. Следовательно, векторное пространство WG графа G изоморфно векторному пространству всех -векторов над полем , где m — число ребер графа

Пусть — ребра графа G. Предположим, что мы сопоставили каждому реберно-порожденному подграфу графа G такой -вектор что элемент равен 1 тогда и только тогда, когда ребро принадлежит подграфу Тогда кольцевая сумма двух подграфов G, и будет соответствовать -вектору являющемуся суммой по mod 2 векторов Легко видеть, что описанное соответствие действительно определяет изоморфизм между и векторным пространством всех -векторов над полем . В самом деле, если мы выберем в качестве базисных векторов для пространства то элементами будут координаты связанные с этим базисом.

При определении этого изоморфизма мы опять использовали символ для обозначения векторного пространства всех -векторов, сопоставленных подграфам графа G. Пусть обозначает подпространство -векторов, представляющих подграфы в подпространстве циклов графа — подпространство, представляющее подграфы в подпространстве разрезов графа

Рассмотрим два таких вектора что вектор находится в пространстве а вектор — в пространстве . Из того, что любой подграф в пространстве имеет четное число общих ребер с произвольным подграфом в пространстве следует, что скалярное

произведение векторов равно сумме по mod 2 четного числа единиц. Это означает, что Иначе говоря, -векторы в пространстве ортогональны подобным векторам в пространстве Таким образом, имеет место следующая теорема:

Теорема 4.9. Подпространства циклов и разрезов графа ортогональны, рассмотрим теперь прямую сумму . Мы знаем, что Поскольку , получаем . Теперь ортогональные подпространства и будут также и ортогональными дополнениями тогда и только тогда, когда Иными словами, будут ортогональными дополнениями в том и только в том случае, если нулевой вектор (все элементы которого равны нулю). Поэтому мы получаем следующую теорему:

Теорема 4.10. Подпространства циклов и разрезов графа являются ортогональными дополнениями тогда и только тогда, когда — нулевой вектор.

Пусть — ортогональные дополнения. Это означает, что каждый вектор в пространстве можно представить кольцевой суммой где вектор W; принадлежит пространству а вектор — пространству

Рис. 4.4. а - граф ; б - граф

Другими словами, каждый подграф графа G можно представить кольцевой суммой двух подграфов, один из которых принадлежит подпространству циклов, а другой — подпространству разрезов. В частности, сам граф G можно представить таким же образом.

Предположим, что не являются ортогональными дополнениями. Тогда, очевидно, существует такой подграф, который нельзя представить как кольцевую сумму подграфов в пространствах . Возникает вопрос: можно ли в этом случае представить граф G кольцевой суммой подграфов, принадлежащих пространствам Ответом является следующая теорема:

Теорема 4.11. Любой граф G можно представить в виде кольцевой суммы Двух подграфов, один из которых принадлежит подпространству циклов, а другой — подпространству разрезов графа G. Доказательство этой теоремы можно найти в работах [44, 45].

Завершим этот раздел разбором примера.

Рассмотрим граф представленный на рис. 4.4, а. Нетрудно убедиться, что ни один непустой подграф этого графа не принадлежит пересечению подпространств

циклов и разрезов. Следовательно, эти подпространства графа являются ортогональными дополнениями. Поэтому множество базисных циклов и базисных разрезающих множеств по отношению к некоторому остову графа образует базис векторного пространства того же графа. Ниже приводится одно из множеств по отношению к остову, образованному ребрами векторы базисных разрезающих множеств

базисные циклические векторы

Легко видеть, что каждый вектор можно представить в виде кольцевой суммы циклического вектора и вектора разрезающего множества. В частности, иектор (111111), представляющий граф сам может записываться в виде где (l 101001) представляет собой разрез, цикл в графе Далее, рассмотрим граф представленный на рис. 4.4, б. В этом графе ребра образуют разрез и цикл. Следовательно, подпространства циклов разрезов этого графа не являются ортогональными дополнениям. Это означает, что существует некоторый подграф в графе который нельзя представить суммой подграфов из подпространства циклов и разрезающего подпространства графа Однако по теореме 4.11 возможно такое разложение для графа Это справедливо, поскольку где — разрез, а — цикл в графе