Нахождение минимального дизъюнктивного базиса, страница 4

Нахождение мажорирующих элементов в матрице У не представляет трудностей: элемент у^j_i мажорирует элемент y^l_k, если столбец у^j поглощается столбцом у^l, а строка у_i поглощается строкой у_k. Это утверждение легко доказывается от противного. Отношение мажорирования транзитивно: если y^j_i мажорирует y^l_k, а y^l_k мажорирует y^t_s, то y^j_i мажорирует y^t_s.

Таким образом, поиск находящихся в отношении поглощения столбцов в матрице L полностью сводится к поиску находящихся в том же отношении строк и столбцов матрицы Y. Эта представляет несомненный практический интерес, поскольку размеры матрицы Y, как правило, значительно меньше размеров матрицы L.

Правило редуцирования матрицы Y. Если строка у_i поглощает строку у_k, то приписывается значение «—» всем ее единичным элементам, соответствующие которым элементы строки y_k также имеют значение 1.

Аналогичное правило устанавливается для столбцов.

Например, в уже знакомой нам матрице

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

Допустим теперь, что рассматриваемая нами задача нахождения кратчайшего минорного покрытия булевой матрицы У решается некоторым многошаговым процессом, в котором текущая ситуация характеризуется двумя переменными величинами: растущим набором максимальных единичных миноров, уже включенных в конструируемое решение, и троичной матрицей Y*, получаемой из Y заменой значений 1 уже покрытых элементов на значение «—». Элементы со значением «—» в дальнейшем можно покрывать, но не обязательно.

Имея теперь дело уже не с булевой матрицей У, а с троичной матрицей Y*, уточним некоторые старые понятия и введем новые.

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

Если некоторый единичный элемент матрицы У* принадлежит лишь одному максимальному множеству совместимых элементов, он называется определяющим, а соответствующее максимальное множество — определяемым множеством для этого элемента.

Сформулируем правило редуцирования текущей ситуации при поиске кратчайшего минорного покрытия булевой матрицы У.

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

Например, анализируя полученную в рассматриваемом примере матрицу У*, мы находим, что единичный элемент y¹₃ является определяющим, поскольку он принадлежит единственному максимальному множеству совместимых элементов {у¹₃,y³₃}- Содержащий это множество максимальный единичный минор матрицы У (показываемый на ее фоне)