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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

48
v
1
v
2
v
3
v
4
v
5
v
6
v
7
0 0 1 1 0 0 0 v
1
0 0 1 0 1 0 0 v
2
1 1 0 1 1 0 0 v
3
S(G) =
1 0 1 0 0 1 0 v
4
.
0 1 1 0 0 1 0 v
5
0 0 0 1 1 0 1 v
6
0 0 0 0 0 1 0 v
7
Большие неориентированные графы, матрицы смежности которых
слабо заполнены единицами, можно задавать более эффективно с точки
зрения затрачиваемого объёма информации.
Неориентированный граф G = 〈V, U〉 без петель представим матри-
цей Q
0
(G), полученной из матрицы смежности S(G) путём заполнения
главной диагонали единицами:
v
1
v
2
v
3
v
4
v
5
v
6
v
7
1 0 1 1 0 0 0 v
1
0 1 1 0 1 0 0 v
2
1 1 1 1 1 0 0 v
3
Q
0
(G) =
1 0 1 1 0 1 0 v
4
.
0 1 1 0 1 1 0 v
5
0 0 0 1 1 1 1 v
6
0 0 0 0 0 1 1 v
7
Минимизация затрачиваемого объёма информации при задании не-
ориентированного графа G сводится к поиску минимальных покрытий.
При этом находят минимальное покрытие столбцов строками матрицы
Q
0
(G) и удаляют недиагональные единичные элементы в строках и
столбцах, соответствующих элементам этого покрытия. Затем находят
минимальное покрытие полученной матрицы Q
1
(G) и удаляют соответст-
вующие недиагональные элементы и т.д. до тех пор, пока все недиаго-
нальные элементы не будут равны нулю.
Для уменьшения трудоёмкости поиска минимального покрытия
матрицы Q
i
(G) из неё исключают сначала поглощаемые столбцы, а затем
поглощаемые строки. При этом столбец α поглощает столбец β, если
множество строк M
β
, покрывающих столбец β, содержит в себе множест-
во строк M
α
, покрывающих столбец α, т.е. M
α
⊂ M
β
. Строка α поглощает
строку β, если множество столбцов M
α
, покрываемых строкой α, содер-
жит в себе множество столбцов M
β
, покрываемых строкой β (M
β
⊂ M
α
).
Применительно к нашему примеру в матрице Q
0
(G) столбец v
1
по-
глощает столбцы v
3
и v
4
, столбцы v
2
и v
7
поглощают столбцы v
5
и v
6
соот-
ветственно. С учётом поглощённых столбцов, строка v
3
поглощает строки
v
1
, v
2
, v
4
и v
5
, а каждая из строк v
6
и v
7
может поглотить другую строку −

Страницы