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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

50
Исключив из матрицы
)(
1
GQ
′
поглощаемые столбцы и строки, по-
лучим матрицу
)(
1
GQ
′
′
:
v
1
v
2
)(
1
GQ
′
′
=
1
0
v
1
,
0
1
v
2
единственное покрытие {v
1
, v
2
} которой является минимальным покры-
тием матрицы Q
1
(G).
Заменив в матрице Q
1
(G) нулями недиагональные единичные эле-
менты в строках и столбцах, соответствующих элементам минимального
покрытия {v
1
, v
2
}, и исключив затем из неё строки и столбцы, не содер-
жащие недиагональных единичных элементов, получим пустую матрицу
Q
2
(G), что свидетельствует об окончании процесса минимизации.
Наконец, сформируем результирующую матрицу
)(
~
GQ
, которая за-
даёт рассматриваемый граф G с минимально затрачиваемым объёмом
информации. При этом строкам матрицы
)(
~
GQ
сопоставим элементы
минимальных покрытий {v
3
, v
6
} и {v
1
, v
2
}, а столбцам – элементы объе-
динения окрестностей O(v
3
) и O(v
6
) элементов первого покрытия:
v
1
v
2
v
4
v
5
v
7
1
1
1
1
0
v
3
)(
~
GQ
=
0
0
1
1
1
v
6
.
0
0
1
0
0
v
1
0
0
0
1
0
v
2
Заметим, что для задания рассматриваемого графа G матрицей
)(
~
GQ
необходимо 20 бит информации вместо 49 бит при задании этого
же графа матрицей смежности S(G).
Задачи и упражнения
1. Получить матрицу
)(
~
GQ
, которая минимизирует затрачиваемый
объём информации при задании неориентированного графа G:
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
а)
б)
в)
г)

Страницы