6.4. Соотношение ортогональности

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

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

Рис. 6.5.

Доказательство. Рассмотрим разрез и цикл С ориентированного графа. Предположим, что мы обходим С, начиная с вершины, находящейся в . Тогда для всякой дуги которая приводит нас из в , существует дуга , которая приводит нас из в . Заметим, что если имеет одинаковую относительную ориентацию в разрезе и в цикле, то имеет в разрезе и цикле противоположные ориентации (рис. 6.5).

Докажем сейчас основной результат этого раздела.

Теорема 6.6. (Соотношение ортогональности.) Если столбцы цикломатической матрицы и матрицы разрезов расположить в одном порядке, то

Доказательство. Рассмотрим цикл и разрез, имеющие общих дуг. Произведение соответствующих циклического вектора и вектора разреза равно нулю, поскольку по теореме 6.5 оно равно сумме k «1» и k «-1». Поскольку каждый элемент матрицы равен произведению циклического вектора на вектор разреза, то теорема доказана.

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

в ч. II книги) электрических цепей. Сейчас мы используем это соотношение для определения ранга цикломатической матрицы

Рассмотрим связный граф G на вершинах и дугах. Пусть — базисные цикломатическая матрица и матрица разрезающих множеств по отношению к остову Т. Если столбцы матрицы В, и расположены в одинаковом порядке, мы можем представить их в виде Согласно соотношению ортогональности, т. е.

Пусть где Р — ранг графа G — является циклическим вектором, элементы которого расположены в том же порядке, что и столбцы матриц Тогда, согласно соотношению ортогональности,

Поэтому

Используя это равенство, можно записать вектор в следующем виде:

Таким образом, любой циклический вектор можно выразить в виде линейной комбинации базисных циклических векторов. Поэтому Объединяя это неравенство с выражением (6.12), получаем следующую теорему и следствие из нее:

Теорема 6.7. Ранг цикломатической матрицы связного графа G, имеющего вершин и дуг, равен т. е. цикломатическому числу графа

Следствие 6.7.1. Ранг цикломатической матрицы графа G на вершинах и дугах с компонентами равен , т. е. цикломатическому числу графа

Пусть — вектор разреза, элементы которого расположены в том же порядке, что и столбцы матриц тогда можно, исходя из соотношения доказать, что

с помощью процедуры, аналогичной той, что использовалась для установления соотношения (6.14). Следовательно, всякий вектор разреза можно выразить в виде линейной комбинации базисных векторов разрезающих множеств. Так как то

. Это является альтернативным доказательством теоремы 6.4.

Заметим, что кольцевая сумма двух подграфов соответствует сумме по mod 2 соответствующих векторов. Поэтому для случая неориентированных графов равенства (6.14) и (6.15) просто повторяют утверждения, уже доказанные нами по ходу рассуждений, приведших к теореме 6.4, а именно: цикл (разрез) можно выразить в виде суммы по mod 2 базисных циклов (базисных разрезающих множеств).