Парадигма развития науки. Методологическое обеспечение (стр. 97 )

I1 I8 = {А, C, D}, J1 J8 = {b}.

Отсюда получаем новую подматрицу

I2 I5 = {А, B, C}, J2 J5 = ,

I2 I6 = {А, B, D}, J2 J6 = ,

I2 I7 = {B, D}, J2 J7 = {c}, дает [M7];

I2 I8= {B, C,D}, J2 J8 = ,

I4 I5 = {A, C, D}, J4 J5 = {b}. Дает [M9];

I4 I6 = {A, D}, J4 J6 = {b, f}, дает [M6];

I4 I7 = {B, D}, J4 J7 = {c}, дает [М7];

I4 I8 = {C, D}, J4 J8 = {b}, содержится в [М9];

I5 I6 = {А, C, D}, J5 J6 = {b}, дает [М9];

I5 I7 = {A, B, C, D}, J5 J7 = .

I5 I8 = {A, C, D}, J5 J8 = {b}, дает [М9];

I6 I7 = {A, B, D}, J6 J7 = ,

I6 I8 = {A, C, D}, J6 J8 = {b}, дает [M9];

I7 I8 = {B, C, D}, J7 J8 = ,

I1 I5 = {A}, J1 J5 = {b, d, e, f}, дает [M1];

I1 I6 = {A}, J1 J6 = {b, d, e, f }, дает [M1];

I1 I7= , J1 J8= ,

I 2 I5= , I2 I6= ,

I 2 I7 = {B}, J2 J7 = {а, с}, дает [М21;

I2 I8= , I4 I5=

I 4 I6 = {D}, J4 J6 = {b, c, f}, дает [М4];

I 4 I7 = {D}, J4 J7 = {b, c, f}, дает [М4];

I 4 I8 = {D}, J4 J8 = {b, c, f}, дает [M4];

I5 I6 = {A}, J5 J6 = {b, d, e, f}, дает [М4];

I5 I7= .

I5 I8 = {C}, J5 J8 = {b, d, e}, содержится в [М5];

I6 I7 = {D}, J6 J7 = {b, d, f}, дает [M4];

I6 I8 = {D}. J6 J8 = {b, f}, содержится в [M4];

I7 I8 = {D}, J7 J8 = {b, c}, содержится в [M4].

Этап 5 (первая итерация). Выпишем новое покрытие

С" = {[M1], [M2], [M4], [M5], [M6], [M7], [M9]},

матрица [М8] исключена, так как она содержится в [М9].

Этап 6 (вторая итерация).

Из проведенных расчетов пересечений и объединений видно, что невозможно найти полную подматрицу, которая не совпадает с какой-нибудь матрицей из предыдущего покрытия или не содержится в ней. Таким образом, мы получили следующее множество основных подматриц покрытия:

Поиски максимального подотношения подобия. Перейдем к

приложению алгоритма Мальгранжа для поисков максимальных подотношений подобия.

В качестве примера рассмотрим обычный симметричный и рефлексивный граф, который изображен на рис. 2, а; мы хотим найти в соответствующей булевой матрице (рис. 2, б) основные подматрицы, которые составят ее покрытие. Те из основных подматриц, которые имеют квадратную форму, и дадут искомые подотношения.

Рис. 2.

Чтобы начать с полных подматриц, которые априори можно рассматривать как довольно близкие к искомым («близкие» с эвристических, не требующего строгого обоснования, соображений), сначала представим строки и столбцы матрицы так, чтобы строки — сверху вниз, а столбцы — справа налево были упорядочены по числу единиц, которые содержатся в них. Это даст матрицу на рис. 2, в.

Этап 1. Выделим следующее покрытие:

Этап 2 (вторая итерация)

I1 I2= {a, d, f, b, c}, J1 J2 = {a, d),

откуда получаем новую подматрицу