6.3. Цикломатическая матрица

Цикл можно обойти в одном из двух направлений: по часовой или против часовой стрелки. Направление, выбираемое для обхода цикла, определяет его ориентацию. Ориентацию цикла можно указать стрелкой, как на рис. 6.3.

Рассмотрим дугу с концевыми вершинами Пусть дуга ориентирована от и входит в цикл С. Будем говорить, что ориентация дуги соответствует ориентации цикла, если вершина встречается при обходе цикла С в направлении, указанном его ориентацией, раньше вершины Например, ориентация дуги в цикле на рис. 6.3 соответствует ориентации цикла, а ориентация дуги — нет. Цикломатическая матрица графа ребрами имеет столбцов и столько строк, сколько циклов имеется в графе G. Элемент определяется следующим образом:

Рис. 6.3.

Строки матрицы называются циклическими векторами графа

В качестве примера снова рассмотрим граф на рис. 6.1, а. На рис. 6.4 представлены три цикла этого графа и их ориентация. Подматрица соответствующая этим циклам, имеет вид

Соответствующая подматрица для неориентированного графа рис. 6.1, б получается заменой в этой матрице «-1» на «+1».

Сейчас определим подматрицу играющую важную роль.

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

Рис. 6.4. Некоторые циклы графа на рис. 6.1, а.

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

Переставим столбцы и строки так, что

1) столбец соответствует хорде ;

2) строка соответствует базисному циклу, определяемому хордой

Выбирая ориентацию базисного цикла таким образом, чтобы ей соответствовала ориентация определяющей хорды, получим следующее представление матрицы

где U — единичная матрица размерности столбцы которой соответствуют хордам остова Т.

Например, базисная цикломатическая матрица графа на по отношению к остову имеет вид

Из (6.10) следует, что ранг матрицы равен Поскольку матрица подматрица получаем

В следующем разделе мы покажем, что ранг подматрицы в случае связного графа равен

Сейчас отметим, что используемый в предыдущем разделе подход к определению ранга матрицы не годится для случая подматрицы . (Почему?) Означает ли это, что отмеченная нами «двойственность» (гл. 4) между циклами и разрезающими множествами просто случайна? Нет, мы увидим, что аргументы, изложенные в следующем разделе, еще более подтвердят эту «двойственность».