Приложение Б. Разложение на максимальные подотношения подобия

Проблема разложения отношения сходства на максимальные подотношения подобия, когда отношения сходства (или соответствующее понятие расстояния) не позволяют получить классы подобия для расстояний, меньших или равных заданному, связана с проблемой получения обычных максимальных плоских подграфов соответствующего обычного графа. Для этого в нашем распоряжении имеется несколько алгоритмов, приведем два из них. Первый принадлежит инженеру Мальгранжу.

Сначала рассмотрим этот алгоритм для более общего случая, а затем вернемся к частному случаю, который нас особенно интересует.

Алгоритм Мальгранжа. Получение максимальных полных подматриц или главных подматриц. Описание этого алгоритма требует введения некоторых предварительных определений.

В матрице с бинарными элементами (0 или 1), т.е. в булевой матрице, задающей граф (а точнее, граф Бержа), полной подматрицей называется подматрица, все без исключения элементы которой равны 1.

Основной подматрицей (говорят также «максимальной полной подматрицей») называется полная подматрица, не содержащая никакой другой полной подматрицы. Например, на рис. Б.1 представлены семь основных подматриц матрицы . Покрытием булевой матрицы называется множество полных подматриц, покрывающих все единичные значения этой матрицы.

Рис. Б.1.

Пусть - множество строк и - множество столбцов булевой матрицы. Каждая полная подматрица определяется упорядоченной парой обычных подмножеств , где , . Можно показать, что операции и , которые двум полным подматрицам булевой матрицы , скажем,

, определенной посредством , (Б.1)

, определенной посредством , (Б.2)

ставят в соответствие две подматрицы:

, определенную упорядоченной парой , (Б.3)

, определенную упорядоченной парой , (Б.4)

есть внутренние операции на множестве полных подматриц матрицы .

Поочередное применение описанных ниже правил до тех пор, пока не сформируются все полные матрицы покрытия

, (Б.5)

позволит получить основные подматрицы матрицы за конечное число итераций.

Первое правило. Вычеркиваем все матрицы , содержащиеся в других подматрицах покрытия .

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

Пример. Найдем основные подматрицы булевой матрицы на рис. Б.1.

Этап 1. Выберем покрытие

(Б.6)

Этап 2 (второе правило).

Подсчитаем объединения и пересечения:

, , (Б.7)

, , (Б.8)

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

(Б.9)

, (Б.10)

и новую матрицу

(Б.11)

, , (Б.12)

, , (Б.13)

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

(Б.14)

, , (Б.15)

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

(Б.16)

Так как все пересечения , , пустые, то бесполезно подсчитывать .

Этап 3 (первое правило).

Выпишем новое покрытие

. (Б.17)

Матрица содержится в и потому не включена в покрытие .

Этап 4 (второе правило).

С дидактической целью приводим все детали расчетов, не исключая вычислений даже тех матриц, которые уже были получены или оказываются пустыми:

, , дает , (Б.18)

, , дает , (Б.19)

, , (Б.20)

, . (Б.21)

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

(Б.22)

, , (Б.23)

, , (Б.24)

, , дает ; (Б.25)

, , (Б.26)

, , дает ; (Б.27)

, , дает ; (Б.28)

, , дает ; (Б.29)

, , содержится в ; (Б.30)

, , дает ; (Б.31)

, , (Б.32)

, , дает ; (Б.33)

, , (Б.34)

, , дает ; (Б.35)

, , (Б.36)

, , дает ; (Б.37)

, , дает ; (Б.38)

, , (Б.39)

, , (Б.40)

, , дает ; (Б.41)

, , (Б.42)

, , дает ; (Б.43)

, , дает ; (Б.44)

, , дает ; (Б.45)

, , дает ; (Б.46)

, (Б.47)

, , содержится в ; (Б.48)

, , дает ; (Б.49)

, , содержится в ; (Б.50)

, , содержится в . (Б.51)

Этап 5 (первое правило).

Выпишем новое покрытие

, (Б.52)

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

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

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

(Б.53)

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

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

Рис. Б.2.

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

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

(Б.54)

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

, , (Б.55)

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

(Б.56)

, (Б.57)

, , (Б.58)

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

(Б.59)

(Б.60)

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

(Б.61)

(Б.62)

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

(Б.63)

(Б.64)

Этап 3 (второе правило). Выпишем новое покрытие

. (Б.65)

Этап 4 (первое правило).

(Б.66)

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

(Б.67)

(Б.68)

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

(Б.69)

(Б.70)

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

. (Б.71)

Мы исключили подматрицы , , , как содержащиеся в других подматрицах покрытия (Б.71).

Этап 6 (первое правило). Читатель может удостовериться в том, что новых матриц получить больше нельзя. Итак, покрытие (Б.71) состоит из следующих основных матриц:

(Б.72)

В этом покрытии содержатся три квадратные подматрицы , и ; они дают три непересекающихся подотношения. На рис. Б.3 представлены эти три подотношения, ни одно из которых не содержится в другом.

Рис. Б.3.

Заметим, что выявление матриц и небесполезно, ими обеспечивается «стыковка» между подотношениями.

Другой, более быстрый метод. Алгоритм Пиша. Этот метод пригоден исключительно для симметрических квадратных матриц, которые представляют для нас особый интерес.

Рассмотрим верхнюю треугольную матрицу, такую, например, как на рис. Б.4.

Рис. Б.4.

Поочередно в каждой строке матрицы выделим нули. Рассматривая элементы матрицы как булевы переменные, свяжем булевым знаком суммирования индекс строки и индексы столбцов, в которых находятся нулевые элементы этой строки, и полученные суммы объединим знаком булева произведения , причем, если в строке нет нулей, будем считать, что сумма равна 1.

Упростим получившееся в результате произведение, приведя его к максимальной форме. Для каждого слагаемого в этой форме возьмем его дополнение. Таким образом, получим максимальные подотношения, устанавливающие покрытие.

Рассмотрим пример на рис. Б.2, для которого верхнетреугольная матрица представлена на рис. Б.4.

Для строки

(Б.73)

Теперь имеем

(Б.74)

Подсчитаем сумму , в которой слагаемыми будут дополнения соответствующих слагаемых суммы . Получим

. (Б.75)

Это дает нам три подмножества

, (Б.76)

которые определяют основные подматрицы, составляющие покрытие (см. , и в (Б.72)).

Замечание. Если нас интересуют элементы, общие для попарно не содержащихся друг в друге отношений, то их можно получить непосредственно, подсчитав пересечения

(Б.77)

Поиск максимальных подотношений подобия в нечетком предпорядке . Любой из двух предыдущих алгоритмов можно использовать для определения этих подотношений. Достаточно рассмотреть соответствующую булеву матрицу , такую, что

(Б.78)

и . (Б.79)

Пример. Рассмотрим еще раз пример, приведенный на рис. 21.3, который мы повторили на рис. Б.5. Здесь выписаны булева матрица, соответствующая отношению , и полученная в соответствии с (Б.78) и (Б.79) матрица .

Рис. Б.5.

Используем второй метод. Имеем

, (Б.80)

. (Б.81)

Таким образом, в этом предпорядке имеется три максимальных подотношения подобия, определенных на обычных подмножествах:

, и . (Б.82)

Эти подотношения приведены на рис. 21.3.