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

Так как в графах й, йя, Йс н йо общее число вершин равно и, то и максимальное значение, которое о может иметь, равно и. Если множество вершин в графе Й(йо, Йя. Йс) может быть разбито на два или более подмножеств, таких, что только вершины внутри подмножества связаны, тогда говорят, что граф Й(йв, Йя, Йо) имеет два или более несвязных помеченных подграфа. Число ребер графа й(йп, йс, йв), на которых дан. ная вершина находится, называется степенью вершины. Так,'степень вершины с в наборе Л графа йз есть число единиц в с-й строке матрицы В. Степенью вершины с в графе й является число внедиагональных единиц с-й строки матрицы В Я В'.

Число дуг направленного графа йш начинающихся в данной вершине, есть степень исхода вершины. Так, степенью исхода с-й вершины является общее число единиц йй строки матрицы В. Степень захода вершины есть число дуг направленного графа Йо, оканчивающихся в данной вершине.

Так, степенью захода )чй вершины является общее З.4. Матрицы и графы ЯГ=ВЩВ'91, (3.4.5) 11 а+1 й,,а (3.4.6) где о = 1, 2, ..., и — 1. Равенство еД7'е~= 1 имеет место тогда и только тогда, когда 1-я и 1-я вершины помеченного графа, соотвеРствуюи(его В, связаны путем, длина которого меньше или равна о. Доказательство проводится методом индукции. Теорема несомненно справедлива для о = 1, так как е,'.(Р'е =во=1, если между 1-и и 1хй вершинами имеется ребро длиною в единицу.

Положим, что теорема верна для некоторого значения о, и покажем, что она верна также и для о+ 1. Из формулы (3.4.6) имеем и рва+! ~~~ а и, тр м' (3.4.7) Теперь тва+' = 1 тогда и только тогда, когда тва, = 1 и шрг — — 1 по крайней мере для одного,р. (3.4.8) Но тва =1, если 1-я и р-я вершины связаны путем, длина которого равна или меньше о, и торс = 1, если р-я и 1чя вершины связаны ребром, когда р чь1. При р =1 на основании формулы (3.4.5) будет ши = 1.

Поэтому в любом случае соотношения (3.4.8) имеют место, если бя и 1-я вершины связаны путем, длина которого равна или меньше о+ 1. Этим завершается доказательство теоремы. Так как максимальная длина пути равна и (поскольку имеется и вершин), то в последующих разделах матрица (р"" используется для определения всех путей н циклов. Для помеченных направленных графов 3 р. тьюарсов число недиагональных элементов 1-го столбца матрицы В. Приведем и докажем теперь некоторые теоремы, которые позднее нам потребуются.

Теорема 3.4.4. Пусть бб Гл. 3. Дополнительные методы минимизачии памяти теорема, подобная теореме 3.4.4, формулируется сле- дующим образом. Теорема (3.4.9). Пусть У=Вой), !те а~-1 (9'а 1е, где о=!, 2, ..., и. Равенство е,'.9е'е = !верно тогда и только тогда, когда в помеченном направленном графе, соответствующем В, имеется направленный путь от 1-й до )ьй вершины, длина которого меньше или равна а.

Доказательство такое же, как н для теоремы (3.4.4), только матрица йт заменяется матрицеи Ят, 3.5. -Диагональная блочная форма В этом разделе описываются некоторые методы преобразования данной матрицы в диагональную блочную форму (ВРЕ). Напомним, что матрица А, определенная формулой (3.3.1), имеет форму ВРГ, если для всех 1Ф 1' подматрицы Ап = О и все диагональные подматрицы Аи являются квадратными матрицами. Если матрица А имеет форму ВРЕ, то из формул (3.2.1) и (3.4.2) следует, что и В имеет форму ВРЕ. Это означает, что оба графа й„и йс, соответствующие В, состоят нз несвязных помеченных подграфов, и каждый помеченный подграф соответствует отдельному диагональному блоку. Так как матрицам В и В соответствуют строчные (и столбцовые) графы, которые отличаются только метками вершин, то графы йи и йс, соответствующие В, могут быть следующим образом использованы для определения матриц Р и й в формуле (3.2.1) (Харари (!962), Тьюарсон (!967 с)). Теорема 3.5.1.

Если В'=В*В' (3.5.2) и Ф" = %'е '* ЧГ' Ь = О, 1, 2, ..., (3.5.3) З.б. Диагональная блочная форма то существует таков Ьи ято чьтгь + ! 1агаь, Р (3.5.4) и е,'.Ре! — — 1 тогда и только тогда, когда 1-я и 1-я строки матрицы В принадлежат одному и тому же диагональному блоку матрицы В, Доказательство. Если в теореме 3.4.4 вместо матрицы В взять матрицу В а В', то вследствие того, что матрица В В' симметричная и все ее диагональные элементы ненулевые, уравнение '(3.4.5) примет вид УР= (В * В) 9 (В ь В)' В! = В ь В', что совпадает с формулой (3.5.2), Поэтому из определения строчного графа йн и теоремы 3,4,4 следует, что если е,'Я7гье! — — 1, то существует путь между вершинами 1 и 1. Если т есть размер наибольшего диагонального блока матрицы В, тогда все пути в графе ь)а меньше или равны т и т ( и.

Поэтому для всех и, таких, что 2" ) т, матрица Я7' остается той же и существует некоторое й!, для которого формула (3.5.4) верна и гг((га'е! 1 тогда и только тогда, когда 1-я и 1-я строки матрицы В принадлежат одному и тому же диагональному блоку матрицы В. Этим завершается доказательство теоремы. Чтобы использовать эту теорему, будем применять уравнение (3.5.3) до тех пор, пока не получим 2" ) и, так как обычно мы знаем о т только то, что т ( и, Пусть Р=((Г'~, Существуют различные практические методы, пригодные вместо формулы (3.5.3) для апре. деления Р (Бейкер (1962), Уошелл (1962), Ингермен (1962), Камсток (1964) ). Опишем вкратце метод, предложенный Камстоком (!964). Производится поиск в первой строке матрицы Ят, пока не встретится нуль, скажем в 1-м столбце.

Затем этот нуль заменяется выражением !Р Р! р 1 68 Гл. 3, дополнительные методы минимиаациа памяти где суммирование производится по правилу алгебры логики. Поиск продолжается в столбцах1+,1, 1+ 2 ... первой строки, пока не найден другой нуль, скажем в д-м столбце. Этот нуль заменяется выражением Е тсюгвре р Этот процесс продолжается до тех пор, пока не про- смотрена вся строка. Затем подобным образом произ- водится поиск нулей и их замена в других строках матрицы, После обработки всех строк начинают опять с первой строки.

Обработка матрицы продолжается до тех пор, пока за полный ее проход в ней ие де- лается никаких изменений. Результирующая матрица и будет матрицей Р. ОЧевидно, что ~, = е',.Ре = 1 тогда и только тогда,' когда 1-я и 1хя строки принадлежат одному и тому же диагональному блоку. Таким образом, все строки мат- рицы В, которые соответствуют ненулевым элементам первого столбца матрицы Р, принадлежат первому ди- агональному блоку. Если все строки матрицы Р, для которых 1п = 1, учтены, то следующий ненулевой столбец матрицы Р может бь|ть использован таким , же образом, как и первый столбец йтой матрицы, для нахождения строк матрицы В, принадлежащих вто. рому диагональному блоку матрицы В и так далее. Таким путем можно найти диагональные блоки мат- рицы В, к которым принадлежит каждая строка мат. рицы В.

Приводимое ниже следствие теоремы 3.5.1 можно применить для определения столбцов матрицы В, принадлежащих различным диагональным блокам матрицы В, Следствие 3.6.6, Если матрица г" определена как в теореме 3Х!, р*в-7 (3.5.6) и Ц =е~Ре~ — — 1, то 1-я строка и 1-й столбец матрицы В принадлежат одному и тому же диагональному блоку матрицы В.

3 б Диагональная блочная форма Доказательство. Из уравнения (3.5.6) имеем ~и= Х ~грЬр! (сумма булева) р и ~и= 1 тогда и только тогда, когда 1ья = Ьхч = 1 по крайней мере для одного ' значения р. Из теоремы 3 5,1 известно, что условие 1;р — — 1 означает, что 1-я и р-я строки принадлежат одному и тому же диагональному блоку матрицы В, и поскольку (ий столбец имеет по крайней мере один ненулевой элемент в р-й строке, постольку 1хй столбец должен находиться в том же диагональном блоке„ что и ь-я и р-я строки. Таким образом, равенство ~гг'— 1 означает, что ь-я строка и !хй столбец принадлежат одному и тому же диагональному блоку.

Этим, завершается доказательство следствия. Чтобы воспользоваться этим следствием, поступаем следующим образом. Для всех столбцов матрицы В, принадлежаших первому диагональному блоку и выбранных согласно теореме 3.5.1, должно быть 1;; =1. Такие столбцы вычеркиваются или как-то отмечаются в матрице Р. Следуюшая ненулевая строка результирующей матрицы дает множество столбцов матрицы В, которые принадлежат второму диагональному блоку и так далее. Если в теореме 3.5.1 пользоваться не формулой (3.5.2), а полагать В'= В'чВ, то получим теорему о перестановке столбцов для преобразования матрицы В в матрицу В. Однако путем небольших изменений можно пользоваться самой теоремой 3.5.1 и таким об.

'разом избежать необходимости дублировать работу, Это осуществляется следуюшим образом. Теорема 3.5.7. Если матрица Р определена, как е теореме 3.5.1, и ег (В' * Р а В) е! = 1, (3.5.8) то йй и 1гй столбцы матрицы В принадлежат одному и тому же диагональному блоку матрицы В, та Гл 3 Глополнительные методы минимизации памяти Доказательство. Иэ уравнений (3.5.2), (3.5.3) н (3.5.4) имеем Втм Ри В= В'* [(В и В )*(В е В ) и... е (В *В )) и В= = (В'* В) и (В'* В)»... е(В' * В) = = (В' и В)', о > т. Поэтому из определения столбцового графа йо и из тех же рассуждений, которые приводились при дока- зательстве теоремы 3.5.1, следует, что условие е,'(В' и Р и В) е = е,' (В' и В) е! = 1 1 0 0 1 0 1 1 О 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 0 тогда ят = 1001 0 1 1 0 0 1 1 0 1 О 0 1 предполагает наличие пути, связывающего 1-й и !'-й столбцы, и поэтому они принадлежат одному и тому же диагональному блоку.

Это завершает доказательство теоремы. Так как формула (3.5.8) содержит одно лишнее матричное умножение по сравнению с формулой (3.5.6), то для перестановки столбцов с целью приведения матрицы к диагональной блочной форме обычно пользуются следствием 3.5.5 вместо теоремы 3.5.7. Приведем простой пример, показывающий, каким образом можно применить теорему 3.5.1 и следствие 3.5.5 для приведения матрицы В путем перестановок к форме матрицы В. Пусть З.б. Треугольная блочная форма Так как ЯТа= — 'я7, то О 1 1 0 1 0 0 1 Р=((Т и РьВ ЯтьВ= 1 0 0 1 0 1Л 0 н из теоремы 3.5.1 следует, что первая и последняя строки матрицы В принадлежат первому диагональному блоку (так как Тп = огп — — )и = гам = 1), а остальные строки — второму диагональному блоку.