Дискретная математика. Кулаков Ю.В - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

2 Установить, какие из цепей из предыдущей задачи являются:
а) простой цепью; в) составной цепью;
б) сложной цепью; г) циклом.
3 Определить диаметр d(G), матрицу достижимости D(G) и число k(G) компонент связности не-
ориентированного графа G:
4 Определить, является ли простым путем, сложным путем, составным путем, контуром путь:
а) ((5, 4), (4, 3), (3, 2), (2, 1));
б) ((3, 1), (1, 5), (5, 4), (4, 1), (1, 2));
в) ((4, 2), (2, 1), (1, 5), (5, 2), (2, 1), (1, 3));
г) ((1, 3), (3, 5), (5, 4), (4, 2), (2, 1)).
5 Определить диаметр d(G), матрицу достижимости D(G) и число k(G) компонент сильной связно-
сти ориентированного графа G:
8 цикломатика
Для исследования циклов в графе используют цикломатическую матрицу
C(G) = [c
ij
]. Каждому циклу графа взаимно однозначно сопоставляется вектор-строка матрицы C(G).
Каждый элемент этой строки определяется следующим образом:
1
2
3
4 5
a
b
c
d
6
а)
1
2
3
4 5
a
b
c
d
6
б)
1
2
3
4 5
a
b
c
6
в)
1
2
3
4 5
a
b
c
d
6
г)
e
1
2
3
4 5
a
b
c
d
6
д)
e
1
2
3
4 5
a
b
c
6
е)
; ; ;
; ; .
a
b
c
d
e
k
1
2
4 5
6
а)
3
1
2
4 5
6
б)
3
a
b
c
d
e
g
f
l
f
g
k
l
m
1
2
4 5
6
в)
3
1
2
4 5
6
г)
3
a
b
c
d
e
a
b
c
d
e
f
g
k
l
m
f
g
k
l
; ;
. ;

Страницы