Дискретно-непрерывная математика (стр. 99 )

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

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

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

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

Рис. Б.1

Пусть L — множество строк и J — множество столбцов булевой матрицы. Каждая полная подматрица определяется упорядоченной парой обычных подмножеств (Ip, J q), где IpI, J q J. Можно пока­зать, что операциикоторые двум полным подматрицам буле­вой матрицы [М], скажем,

[M1], определенной посредством (Il, J1), (Б.1)

[М2], определенной посредством (I2, J2), (Б.2)

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

определенную упорядоченной парой

(Б.3)

определенную упорядоченной парой

(Б.4)

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

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

(Б.5)

позволит получить основные подматрицы матрицы [М] за конечное чис­ло итераций. (Символ С ранее использовался для обозначения категорий, но мы не думаем, что может возникнуть какая-нибудь путаница между этими двумя по­нятиями, хотя они и обозначены одной и той же буквой.)

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

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

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

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

(Б.6)

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

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

(Б.7) (Б.8)

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

(Б.9)

(Б.10)

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

(Б.11)

(Б.12) (Б.13)

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

(Б.14)

(Б.15)

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

(Б. 16)

Taк как все пересечения

пустые, то бесполезно подсчитывать

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

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

(Б.17)

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

Этап 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)

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

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

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

(Б.53)

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

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

Рис. Б.2

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

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