Дискретная математика. Громов Ю.Ю - 59 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

59
хорды рёбра остова
c d m a b e f g h
1 0 0 0 1 0 0 1 1 B
1
B(G) = 0 1 0 1 0 1 1 1 1 B
2
0 0 1 1 0 0 1 1 0 B
3
Заметим, что эта матрица задаёт простые циклы (b, c, h, g), (a, f, e, d,
h, g) и (a, f, m, g) графа G (см. рис. 23, а).
Для исследования циклов в графе используют прямоугольную цик-
ломатическую матрицу C(G), в которой каждому из (
1
2
)(
−
Gv
) циклов
графа G сопоставляется отдельная строка, а каждому из рёбер − отдель-
ный столбец. Некоторый элемент c
ij
цикломатической матрицы C(G) оп-
ределяется следующим образом:
=
случае.противномв0
;цикл й в входит ребро еесли,1 i-j-
c
ji
Включив в цикломатическую матрицу ν(G) базисных циклов, а так-
же (
1)(2
)(
−− Gv
Gv
) их различных линейных комбинаций, можно полу-
чить всё множество циклов графа G.
В нашем примере матрица C(G) будет содержать семь строк, кото-
рые представляют три базисных цикла и четыре возможные линейные
комбинации этих базисных циклов, полученные в результате поразрядно-
го сложения по модулю два:
хорды рёбра остова
c d m a b e f g h
1 0 0 0 1 0 0 1 1 B
1
0 1 0 1 0 1 1 1 1 B
2
C(G) =
0 0 1 1 0 0 1 1 0 B
3
1 1 0 1 1 1 1 0 0
B
1
⊕
B
2
1 0 1 1 1 0 1 0 1
B
1
⊕
B
3
0 1 1 0 0 1 0 0 1
B
2
⊕
B
3
1 1 1 0 1 1 0 1 0
B
1
⊕
B
2
⊕
B
3
После сортировки столбцов этой матрицы в алфавитном порядке,
она примет свой окончательный вид:
a b c d e f g h m
0 1 1 0 0 0 1 1 0 C
1
1 0 0 1 1 1 1 1 0 C
2
C(G) =
1 0 0 0 0 1 1 0 1 C
3
1 1 1 1 1 1 0 0 0 C
4
1 1 1 0 0 1 0 1 1 C
5
0 0 0 1 1 0 0 1 1 C
6
0 1 1 1 1 0 1 0 1 C
7

Страницы