Разряженные матрицы. Р. Тьюарсон, страница 12

яополнительные методы минимизации памяти диагональному блоку, н столбцов другого диагонального блока; аналогично вычисляются элементы нового столбца. Таким путем из матрицы Р получается квадратная матрица Р, порядок которой равен числу диагональных блоков. Помечейгтый направленный граф, соответствующий матрице Р, называется помеченнььм направленным графом сгущения 5ев матрицы В. Его вершинами являются диагональные блоки. Так как граф сгущения не меняется при перестановке номеров вершин, то матрица В имеет тот же граф сгущения. Вершина, из которой дуги только исходят, называется змигтером, а вершина, не связанная с какой-либо другой вершиной, называется изолированной.

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

д. Таким образом определяется порядок диагональных блоков матрицы В. Все эти перестановки регистрируются, н результирующая матрица перестановок обозначается через Р. Затем с помощью формулы (3.6.2) определяется верхняя тре-, угольная блочная матрица В. Второй метод преобразования путем перестановок матрицы В к форме ВТГ идентичен первому в том, что касается определения максимальной трансверсали, но отличается своей второй частью. Отличие обусловлено изложенными ниже соображениями. Можно избежать вычисления матрицы Р в соответствии с формулой (3.6.!О), если преобразовать матрицу В к треугольной блочной форме В следующим образом (Стьюард (1965)), З.б.

Треугояьмая бяочмая форма 79 Заметим, что диагональным блокам второго н более высокого порядка матрицы В отвечают циклы направленного графа, соответствующего матрице. С другой стороны, все столбцы матрицы В, в которых нет ненулевых элементов ниже диагонали и которые лежат перед первым диагональным блоком, могут быть легко найдены из матрицы В таким путем. Шаг ! Определяем столбец матрицы В, содержащий единственную единицу, перемещаем этот столбец и соответствующую строку 1в которой, возможно, имеется и несколько единиц) в северо-западный угол и маркируем этот столбец и соответствующую строку.

Процесс повторяется до тех пор, пока среди немаркированных столбцов матрицы В больше не будет столбцов с единственной единицей на немаркированной строке. Шаг 2 Определяем столбцы (и строки), которые лежат в том же диагональном блоке, что и первый немаркированный столбец матрицы В. Из шага 1 следует, что первый немаркированный столбец матрицы В имеет по меньшей мере одну недиагональную единицу в немаркированной строке. Столбец, соответствующий строке с первой такой единицей, тоже должен иметь единицу в немаркированной строке, и так далее.

В какой-то момент мы сталкиваемся со столбцом, который уже ранее встречался, и этим заканчивается направленный цикл. Заменяем все столбцы направленного цикла одним столбцом, представляющим собой булеву сумму таких столбцов без их диагональных элементов. Такой процесс называется стягиванием столбцов в направленном цикле. Булеза сумма гекторов — это обычное сложение векторов при условии, что 1 Я 1 = = 1. Аналогично заменяются все строки направленного цикла одной строкой, являющейся их булевой суммой. Когда маркируется столбец с единственной единицей, то все столбцы, стянутые в этот столбец, 80 Гл.

8. Доаолнительнеее метода минимизации памяти х ° х ° ° ° Х Х х ° 1. Столбец 3 имеет единственную единицу. ° х Маркируем столбец 3 и строку 3. Заносим 1 в третью строку колонки «порядок», в кото- последовательность исключения 5 ° х ° ° х 7 Х ° ° ° ° Рис. 3.6.3 рой регистрируется столбцов. 2. Столбец 7 имеет единственную единицу в немаркированных строках. Маркируем столбец 7 н строку 7 и заносим 2 в колонку «порядок». 3. Нет больше столбцов с единственной единицей в немаркированных строках. Начинаем построение направленного пути со столбца 1, выбирая всегда первую встреченную в столбце единицу. Это дает направленный путь 1, 2, 1, н, следовательно, 1 и 2 находятся в направленном цикле. Стягиваем столбец 2 в столбец 1, для чего дополняем столбец 1 знаком +, чтобы превратить его в булеву сумму прежнего столбца 1 с недиагональными элементами столбца 2.

Аналогичным образом стягиваем строку 2 в строку 1 и принадлежат одному и тому же блоку. Порядок, в котором столбцы с единственной единицей маркировались, определяет порядок, в котором расположены диагональные блоки. Процесс выполнения шагов 1 и 2 продолжается до тех пор, пока все столбцы и строки матрицы не будут маркированы. Поясним эти правила на примере матрицы, представленной на рис. 3.6,3, выполняя преобразования шаг за шагом до тех ! 1 3 1 5 5 1 пор, пока не придем к х х ° ° ° х ° матрице, представлен- ной на рис.

3,6.4. Позих х ° ° ° ° ° ции единиц указаны знаками умножения, 5 ° х нулей —.точками, едн° ° х ° ° ° ннц, порожденных стя- гиванием строк или 5 столбцов, — плюсами. 3.б. Треугольная блочная форма 81 маркируем столбец 2 и строку 2. Заносим 1 во втоую строку колонки «стягивание», чтобы указать на то, что столбец 2 был стянут в столбец 1.

4. Начиная со столбца 1, строим направленный путь 1, 6, 1 и стягиваем столбец 6 в столбец ! н стро„у 6 в строку 1. Маркируем столбец 6 и строку 6 и заносим 1 в шестую строку колонки «стягивание». У ! 3 4 3 6 7 ° ° Х ° Х ° Рис. З.алн 5. Столбец 1 имеет теперь единственную единицу в немаркнрованных строках. Позтому заносим 3 в первую строку колонки «порядок» и маркируем строку 1 н столбец 1. 6. Столбец 6 имеет единственную единицу в не- маркированных строках, и мы помешаем 4 в колонке «порядок» и маркируем строку 5 и столбец 5. 7. Столбец 4 имеет единственную единицу в немаркнрованных строках, заносим 5 в колонку «порядок» и маркируем столбец 4 и отроку 4. Теперь уже больше нет нем аркированных столбцов и строк н можно по колонкам «порядок» и «стягивание» 3 6 1 ! 2 1 3 3 4 4 1 В 2 7 Х Х ° ° ° Х ° Х Х ° ° ° ° ° ° ° ° Х ° ° ° ° ' ° ° х х ° ° + Х ° ° Х Х ° Х ° ° ° ° ° Х 82 Гл.

3. дополнительные методы минимизации памяти установить расположение диагональных блоков, Первый блок содержит элемент (3,3) матрицы В, второй — элемент (7,7). Третий блок содержит в качестве диагональных элементы матрицы В, стоящие в пози. пнях (1,1), (2,2) и (6,6). Четвертый и пятый блоки Пх х ° ° ° х ° ° Дх х ° ° ° ° ° ° х ° ° ° ° ° ° Пх х ° ° ° ° ° ° Дх Рис. 3.6.6. Рис. 3.6.6. состоят соответственно из элементов (5,5) и (4,4). Таким образом, матрица перестановок Р из уравнения (3.6.2) имеет вид (ез ет е! ез еб ез ел) а матрица В представлена на рис, 3.6.5.

Если матрица В небольших размеров, то ее направленный граф может быть непосредственно использован для получения В. Направленный граф, соответствующий матрице В (рис. 3.6.3), представлен па рис. 3.6.6. Ищем вершину, которая является эмиттером (в ней не заканчивается ни одна дуга). Эмиттером будет вершина 3, даем ей номер 1 и исключаем все дуги, выходящие из нее. Теперь эмиттером становится вершина 7, даем ей номер 2 и исключаем все дуги, выходящие из нее. Теперь уже нет других эмиттеров. Вершины 1,2 и 6 расположены в цикле, и мы перенумеровываем их соответственно в 3, 4, 5. Исключаем все дуги, которые выходят из каждой из этих 8.7.

Треугольная ленточная форма 88 ршин. Вершина 5 теперь является эмиттером, обоначаем ее через 6 и, наконец, вершние 4 даем номер 7 Таким образом, Р = (еьь е„е„еь ем еы е,), как и прежде. Имеются еще два метода для преобразования матрицы к форме ВТР пли к форме, подобной ей, Они рассматриваются в равд. 3.7. 3.7.

Треугольная ленточная форма Говорят, что матрица В имеет треугольную ленточную форму (ВьнТР), если существует такое (), О ( 5 ( ( п, что ЬО ='О, для всех ь' — у ) р, и значение () ие может быть уменьшено перестановками строк и столбцов матрицы В. Пусть первый ненулевой элемент Рй строки матрицы В находится в дпм столбце, тогда определяем (ь =' Чь Чг~~(, 5г = О, уг > Е.

Очевидно, что если матрица В имеет форму ВХТР, то тахт Оч = р. Заметим, что треугольная блочная форма (ВТР), описанная в предыдущем разделе, яв.чается специальным случаем формы Вг(ТР Я+ 1 является в этом случае размером наибольшего диагонального блока матрицы В). В этом разделе будем полагать, что, если это возможно, данная матрица уже преобразована к форме ВЭГ согласно методам, изложенным в равд. 3.5. Если такое преобразование сделано, мы рассмотрим каждый нз диагональных блоков в отдельности. Поэтому не будет потери в общности, если мы предположим, что граф матрицы В является связным. Первый метод преобразования матрица В п форме В)ч'ТР.