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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

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

Страницы