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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Минимизация затрачиваемого количества информации при задании графа
сводится к покрытию столбцов строками матрицы Q(ψ). Для уменьшения трудоемкости поиска мини-
мального покрытия необходимо вычеркнуть поглощаемые строки и столбцы. Строка α поглощает
строку β, если множество столбцов M
α
, покрываемых строкой α, содержит множество столбцов M
β
, по-
крываемых строкой β, M
β
⊂ M
α
. Столбец a поглощает столбец b, если множество строк M
b
, покры-
вающих столбец b, содержит множество строк M
a
, покрывающих столбец a, M
a
⊂ M
b
.
Строка v
3
матрицы Q(ψ) поглощает строки v
1
и v
2
, строка v
6
– строку v
7
.
Столбец v
7
поглощает столбцы v
4
, v
5
и v
6
, столбец v
1
– столбец v
3
. Вычеркнем из матрицы Q(ψ) строки
v
1
, v
2
, v
7
и столбцы v
3
, v
4
, v
5
, v
6
:
v
1
v
2
v
7
1 1 0 v
3
1 0 0 v
4
)(ψ
′
Q =
0 1 0 v
5
.
0 0 1 v
6
Найдем покрытия столбцов строками матрицы )(ψ
′
Q :
(v
3
∨ v
4
) (v
3
∨ v
5
) v
6
= (v
3
(v
3
∨ v
5
) ∨ v
4
(v
3
∨ v
5
)) v
6
=
= (v
3
∨ v
4
(v
3
∨ v
5
)) v
6
= (v
3
∨ v
4
v
3
∨ v
4
v
5
) v
6
= (v
3
∨ v
4
v
5
) v
6
=
= v
3
v
6
∨ v
4
v
5
v
6
.
Минимальным из двух полученных покрытий матрицы )(ψ
′
Q и матрицы
Q(ψ) является покрытие {v
3
, v
6
}. Это покрытие порождает две окрестности единичного радиуса: O(v
3
) =
{v
1
, v
2
, v
4
, v
5
} и O(v
6
) = {v
4
, v
5
, v
7
}.
Заменим в матрице Q(ψ) нулями недиагональные единичные элементы, во-
шедшие в покрытие, и исключим затем из нее строки и столбцы, не содержащие недиагональных еди-
ничных элементов:
v
1
v
2
v
4
v
5
1 0 1 0 v
1
0 1 0 1 v
2
)(" ψQ =
1 0 1 0 v
4
.
0 1 0 1 v
5
Найдем покрытия столбцов строками матрицы )(" ψQ :
(v
1
∨ v
4
) (v
2
∨ v
5
) (v
1
∨ v
4
) (v
2
∨ v
5
) = (v
1
∨ v
4
) (v
2
∨ v
5
) =
= v
1
(v
2
∨ v
5
) ∨ v
4
(v
2
∨ v
5
) = v
1
v
2
∨ v
1
v
5
∨ v
2
v
4
∨ v
4
v
5
.
Поскольку все четыре полученные покрытия имеют одинаковую сложность,
в качестве минимального покрытия можно выбрать любое из них.
Заменив в матрице )("
ψ
Q нулями недиагональные единичные элементы, во-
шедшие в покрытие, и исключив затем из нее строки и столбцы, не содержащие недиагональных еди-
ничных элементов, получим пустую матрицу, что свидетельствует об окончании процесса минимизации
затрачиваемого количества информации при задании графа.
Сформируем матрицу инцидентности )(
~
ψQ модели ψ, задающую рассматри-
ваемый граф. Строкам этой матрицы взаимно однозначно сопоставим элементы найденных покрытий, а
столбцам – элементы объединения окрестностей элементов первого покрытия:
v
1
, v
2
(v
3
)
v
7
(v
6
)
v
4
(v
3
, v
6
,
)
v
5
(v
3
, v
6
,
)
Рис. 18

Страницы