Составители:
Рубрика:
16
4.2. Матрица главных сечений графа
Сечением графа называется линия, делящая граф на две несвя
занные части. На рис. 5, а изображены произвольные сечения графа
(A, B, C, D). Линии сечения на этом рисунке пересекают произволь
ное число ребер и хорд.
Для получения главного сечения графа нужно линию сечения гра
фа провести таким образом, чтобы она пересекала только одну ветвь
при произвольном пересечении хорд. Так как главное сечение графа
пересекает только одну ветвь, то число главных сечений равно числу
ветвей дерева. На рис. 5, б сечения A, B, C, D — главные.
Построим матрицу главных сечений А
С
, строки которой соответ
ствуют главным сечениям, а столбцы — ребрам графа. Начальные
столбцы матрицы соответствуют ветвям в порядке возрастания но
меров ветвей графа, остальные — хордам в порядке возрастания хорд
графа.
РЕБРА
Ветви Хорды
1 0 0 0 1 0 0 0
0 1 0 0 1 1 0 1
0 0 1 0 0 1 1 1
0 0 0 1 0 0 1 1
C
−
−−
=
−
A
(1)
Каждый элемент а
ij
матрицы А
С
равен: а
ij
= +1, если j%е ребро пере
секает iе сечение в том же направлении, что и ветвь, определяющая
это сечение; а
ij
= –1, если jе ребро пересекает i%е сечение в направле
нии, противоположном направлению ветви, определяющей это сече
ние; a
ij
= 0, если jе ребро не пересекает iе сечение.
Рис. 5. Сечения графа: а — произвольные; б — главные
"
#
%
$
¹
º
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
