Составители:
Рубрика:
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-е сечение в
1
2
4
5
6
7
8
A
B
CD
3
4
5
2
1
6
8
7
а)
б)
Рис. 5
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
