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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

v
1
v
2
v
4
v
5
v
7
1 1 1 1 0 v
3
0 0 1 1 1 v
6
.
)(
~
ψQ
=
0 0 1 0 0 v
1
0 0 0 1 0 v
2
Для задания этой матрицы необходимо 20 бит вместо 49 бит при задании
этого графа матрицей инцидентности Q(ψ). Мограф ))(
~
( ψQG
М
изображен на рис. 18. Вершинам мографа
сопоставлены элементы объединения окрестностей. Одна из вершин имеет двойное обозначение v
1
, v
2
,
поскольку столбцы v
1
и v
2
матрицы )(
~
ψQ идентичны.
Уплотнение задания ориентированных графов с петлями аналогично опи-
санному способу. При этом отдельно задаются начала дуг графа в виде мографа (G
М
)
+
и концы дуг в ви-
де (G
М
)
−
.
Задачи и упражнения
1 Получить матрицу инцидентности )(
~
ψQ модели ψ, минимизирующую затрачиваемое количество
информации при задании неориентированного графа:
7 СВЯЗНОСТЬ И СИЛЬНАЯ СВЯЗНОСТЬ ГРАФА
Распределение цепей и циклов в неориентированном графе, а также путей и
контуров в ориентированном графе определяет многие свойства графа, в том числе его связность и
сильную связность.
Цепью в неориентированном графе называется последовательность ребер
(ρ
1
, ρ
2
, ..., ρ
n
) вида ρ
i
= {v
i
, v
i+1
}, i = 1, 2, ..., n. Вершины цепи могут иметь степень, равную 1. Вершина со
степенью, равной 1, называется концевой вершиной. Число ребер цепи, соединяющей вершины v
i
и v
j
,
называется длиной цепи и обозначается l(v
i
, v
j
). Цепь называется составной, если в ней повторяется хотя
бы одно ребро, сложной, если – хотя бы одна вершина, и простой – в противном случае.
Циклом называется цепь, концевые вершины которой совпадают. Любая
вершина v
i
цикла имеет степень s(v
i
) ≥ 2.
Граф G = 〈V, U〉 называется связным, если любая пара его вершин соединена
цепью.
Максимальный по включению вершин связный подграф графа называется
его компонентой связности. Граф называется несвязным, если он имеет число компонент связности
больше одной. Например, граф, состоящий из двух несмежных вершин, имеет две компоненты связно-
сти и является несвязным.
Рассмотрим задачу определения числа компонент связности неориентиро-
ванного графа.
Пусть S = [s
ij
] – матрица смежности графа G = 〈V, U〉, элемент s
ij
которой оп-
ределяется следующим образом:
=
смежны.не,вершиныесли0,
;,вершиныгосоединяющеребра,торидентифика
ji
ji
ij
vv
vv
s
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
а)
б)
в)
г)
; ; ; .

Страницы