4.2. Пространство циклов графа Теорема 4.2. Число базисных циклов графа постоянно и равно
цикломатичеcкому числу.
Базис пространства циклов определяется базисной системой циклов. Базисной системой циклов для данного остовного леса D графа G называется множество всех циклов графа G , каждый из которых содержит только одну хорду D .
Базисная система циклов записывается в виде базисной циклома-тической матрицы Cδ (G).
Выполняя 2ν -ν - 1 раз операцию сложения по модулю два над исными циклами, получим все множество циклов этого пространства. Пространство циклов записывают в виде цикломатической матрицы Cδ (G).
Пример 5. Найти базис пространства циклов и пространство циклов графа G, изображенного на рис.4.4.
Определяем базис пространства циклов графа G . Для этого, согласно т.4.2, находим цикломатическое число ν(G) графа G, Так как граф G- связный, то
ν(G) = т - п + 1 = 9 - 7 + 1 = 3, т.е. базис состоит из трех циклов.
Рис.4.3
Рис.4.4
С другой стороны ν(G) равно числу хорд любого остова графа G . Это означает, что нужно в графе удалить три ребра такие, чтобы получился остов графа G . Тогда эти три ребра будут его хордами. Один из возможных остовов графа G показан на рис. 4.5а.
Хордами этого остова являются ребра а, d , h ,
Строим теперь базисную систему циклов. Так как заданный граф связный, то остовный лес D состоит из одного остова. Но (для лучшего понимания решения задачи) его можно изобразить в виде леса (рис.4.5б). Объединение этих трех остовных деревьев дает остов графа G . Теперь хорошо видно, что базисная система циклов состоит из трех циклов, каждый из которых содержит только одну хорду D . Изобразим базисную систему циклов в виде базисной дипломатической матрицы:
Хорды остов
C1, C2, C3, -базис пространства циклов графа G- . Теперь, выполняя 2ν -ν - 1 = 23 -3 - 1 = 4 раза операцию
сложения по модулю два над базисными циклами; получим пространство циклов:
C4 = C1 C2 , C5 = C1 C3 , C6 = C2 C3 C7 = C1 C3 Пространство циклов запишем в виде цикломатической матрицы
хорды остов
Значит, пространство циклов заданного графа G состоит из семи циклов, включая и базисные циклы, т.е. |С(G)| =7 мощность пространства циклов графа G. ■
При нахождении пространства коциклов (разрезов) графа сначала определяют базис пространства коциклов. Базис пространства коцик-лов определяется базисной системой коциклов. Эта система строится следующим образом.
Строится остов D (или остовный лес) графа G . Для этого вычис-ляется коциклический ранг χ (G) графа, значение которого указывает на число ребер в остове D (в остовном лесе) графа G и на число базисных коциклов. Удаляется ребро остова D . Множество вершин при этом распадается на два непересекающихся подмножества
V1 и V2 . Множество всех ребер в G , каждое из которых соединяет вершину из V1 с вершиной из V2 , является разрезом (коциклом) графа G . Множество всех разрезов для каждого ребра остова D является базисной системой разрезов для данного остова D . Эта система может быть записана в виде соответствующей базисной матрицы разрезов или базисной коцикломатической матрицы.
Выполняя 2 χ - χ - I раз операцию сложения по модулю два над базисными коциклами, определяем все множество коциклов (разрезов) графа. Пространство коциклов можно записать в виде матрицы разрезов или коцикломатической матрицы.
Пример б. Найти базис пространства коциклов и пространство коциклов графа G , изображенного рис.4.6.
□ Определяем базис пространства коциклов графа G. Для этого вычислим коциклический ранг χ (G) графа G . Так как граф связный, то К =1:
χ (G)= n - К = 4 - 1=3,
т.е. базис пространства разрезов будет состоять из трех базисных коциклов и в остове D должно быть три ребра, а удаленные два ребра будут хордами остова D. Остов D изображен на рис. 4.7а. Ребра d, c являются хордами остова D .
Рис.4.7
Удаляем
из остова D
ребро
а
(рис.4.7б). Множество вершин разбилось на
два подмножества V1=
{
}
и V2={
}.
В
графе G
вершина
из
V1
соединяется с вершинами
и
из V2
ребрами
а
и d
, т.е. K1
= {а
,d}
является базисным коциклом (разрезом).
У
даляем
из остова D
ребро в (рис.4.7в):
V1=
{
},
V2={
},
K2
= {b
,c}
Удаляем
из остова D
ребро е
(рис.4.7г):
V1=
{
},
V2={
},
K3
= {c,
d,
e}
Строим базисную матрицу разрезов
остов хорды К1,. К2, К3 - базис пространства коциклов графа G.
Теперь, выполняя 2 χ - χ - I = 23 – 3 – 1 = 4 раза операцию сложения по модулю два над базисными коциклами, получим пространство коциклов (разрезов):
K
4 =
K
1
K2
, K
5
=
K1
K
3 ,
K
6
=
K
2
K
3 K
7 =
K
1
K
2
K
3.
Пространство коциклов запишем в виде
коцикломатичесхой матрицы K(G)
Значит, пространство коциклов заданного графа G состоит из семи коциклов, включая и базисные коциклы, т.е. |K(G)| =7. Отметим, что Кч= {a, b, c, d} является объединением разрезов {a, d} и {b, c} ■
Задачи для самостоятельного решения
Построить все остовы неориентированного графа G = < V, U>, у которого
Определить базис пространства циклов и пространство циклов графа G = < V, U> , у которого
.Является ли граф G = < V, U> заданный в задаче 2, двудольным? (при решении использовать т.4.1).
Определить базис пространства циклов и пространство циклов графа G = < V, U> , У которого
Определить базис пространства коциклов и пространство коциклов графа G = < V, U> , у которого
СПИСОК ЛИТЕРАТУРЫ
Горбатов В.А. Основы дискретной математики. — М.: Высшая школа, 1986. – З11с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1986. - 480с.
Коршунов Ю.М. Математические основы кибернетики. - М.: Энергоатомиздат, 1987. — 496с.
Сигирский В.П. Математический аппарат инженера. -Киев: Техника, 1975. - 768с.
СОДЕРЖАНИЕ