Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 18
Текст из файла (страница 18)
->~н. Рис. 5.2.3 показывает такую последовательность для графа на рис, 5,2.1. Из соображений удобства «суперузлы» в г(5;) обозначаются как у, а не (у). Рас. 5.2.3. Последовательность фактор-графов Следуюп1ая теорема показывает, что фактор-графы вида (5.2.3) действительно являются представлениями 1рафов исключения. з З.я Машинное нредставление графов исключения 113 Теорема 5.2.1. Для у еи Х вЂ” 5, Кеасп (у, 5с) = Кеасп, (у„т(5,)). Доказательгтво, Пусть и ~ КеасЬо(у,5с). Если узлы у и и смежны в 6, то это же верно для тех же узлов в Уь В против- ном случае в 6 найдется путь у, з„..., з„и, где (зь ..., зс) ~5ь Пусть 6(С) — связная компонента в 6(5;), содержащая зь Тогда в У, имеется путь у,С,и; поэтому и ~ гтеас)чт,(у, с (5с)).
Пусть, обратно, и ~ Кеаспт,(у, г(5ч)), Найдется в У, путь у, С„...,С„и, такой, что (Сь ..., Сс) с: т(5,). Если ~ = О, то у и и смежны в исходном графе 6. Если же ( ) О, то, по определению связ- ных компонент, ( не может быть больше единицы; следова- тельно, путь должен иметь вид у, С, и, так что в графе 6 есть путь из у в и через С. Поэтому и еи Кеаспа(у, 5,.) Построение достижимых множеств по фактор-графу У~ весьма просто. Следующий алгоритм вычисляет множество аеас)ге,(у, т(5~)) по заданному узлу у ~ Р(5ч).
Шаг 1 (инициализация), Я ч-о. Шаг 2 (найти достижимые уэльс). Для х~Ад) (и) Если х~ '(5,) то сг — )г() Ад) (х) иначе сг — )г () (х). Шаг 3 (выход) )г есть искомое достижимое множество. Связь между графами исключения и фактор-графами (5.2.3~ вполне очевидна. В самом деле, структуру графа исключения 6~ можно получить из структуры У, следующим простым алго- ритмом. Шаг А Удалить суперузлы и инцидентные им ребра из фактор-графа. Шаг 2. Для каждого С ~ с(5;) добавить к фактор-графя ребра так, чтобы все узлы, смежные с С, были попарно смеж.
ны в графе исключения. С целью иллюстрации рассмотрим ггреобразование Ул в 6, для примера на рис. 5.2.3. Граф исключения 6, показан на рис. 5.2.4. Как средство представления процесса исключения и по степени неявности модель фактор-графов лежит между методом достижимых множеств и моделью графов исключения. Достижимые множества по исходному — ь Фактор- — ь Граф графу граф исключения Соответствие между тремя моделями суммировано в таблице 5.2.).
Таблица 5.2.5 Неявная модель фактор-модель Явна» ь1одель Представление о, о кеасол (у, ((Яд) ! Смежность Рассмотрим фактор-граф У = 6/ссг(5), отвечающий исключенному множеству 5. Если з ен 5, то удобно пользоваться обозначением з для той связной компоненты подгрифа 615), 114 Гл. б. Универсальные разреженные методы Рис. 5.2.4. От фактор-графа к графу исключения. За 8а ~н-1 йеаси (У, дт) 5.2.3 Реализация фактор-модели о Дб) о,(у) а 6.2 Миигинног иргдггиелгиие графов искмоигиии 11б которая содержит узел з, Например, для фактор-графа на рнс.
5.2,2 хг = х, = х, = хг = (хо хг, хо хь). С другой стороны, для задзнного Сан г(5) можно выбрать произвольный узел х из С и использовать х как представитель С, это означает, что х = С. Прежде чем обсуждать способ выбора представителя в реализации, установим некоторые результаты, которые будут использованы для демонстрации, что модель можно осушествить на месте, т.
е, на сегменте памяти, отведенном для структуры смежности исходного графа. Лемма 5.2.2. Пусть б = (Х,Е), и пусть С ~ Х таково, что б(С) есть связный подграф. Тогда ~ ! Аб) (х)! „з !Ад! (С) !+ 2()С! — !). гиС Доказагельсгво, Так как б(С) связен, в нем имеется по крайней мере )С! — 1 ребер, В сумме ~ !Ад!(х)! эти ребра с засчитываются дважды, откуда и следует утверждение. Пусть хь хг, ..., хи — последовательность узлов и 5~ * (хь ..., х), ! ~1( У. Положим Уг = бП (5г) = (г (51) ~г). Лемма 5.2.3. Пусть уев Х вЂ” 5ь Тогда ! Ад) (у)! =э ~ Ад) (у)~.
Доказательство. Это следует из неравенства ~ Ад), (у) ! ~ ~ А<Ци, (у) ~, где у е= Х вЂ” 5~+в Проверка этого неравенства предоставляется читателю в качестве упражнения. Теорема 5.2.4. гп ах ! о, ) < ! Е !. ~к!ки Доказательство. Рассмотрим фактор-графы У; и У~ы. Если в подграфс б(5,+1) узел х;+1 изолирован, то ясно, что )8~+1~= =!Ю,~. В противном случае х,+1 присоединяется к некоторым компонентам в 5„в результате получается новая компонента в 5;+ь Применяя результаты лемм 5.2.2 н 5.2.3, получим ! юг(+1! < ! о г ! Следовательно, во всех случаях !Уг !<1~1!- откуда вытекает нужное утверждение. 116 Гл, д ениверсалвные разреженные метода Теорема 5.2.4 показывает, что последовательность фактор- графов, порождаемая исключением, требует памяти не больше, чем структура исходного графа.
При объединении узлов связного множества С в суперузел лемма 5.2.2 гарантирует, что места, отведенного для множеств Аг(1 (х), х ен С, достаточно для хранения Аг(1(С). Более того, при 1С1.з» 1 имеется избыток в 2(~С( — 1) слов, который можно использовать для связей или указателей. Рис. 5,2.5 иллюстрирует структуру данных, используемую для представления множества Аг() (С) в фактор-графе У, причем С = (а, Ь, с). Нуль указывает конец данного списка в У. Исхпйяая сир~ кпгурп Фпягяор-сп рутурп Рис. 5.2.5.
Структура данных длн фактор-графа. Заметим, что в этом примере в качестве представителя множества С= (а, Ь, с) выбран узел «а», При машинной реализации важно, чтобы каждому Сепг(5) соответствовал единственный представитель: тогда любую ссылку на С можно заменить ссылкой на представителя. Пусть хь хт, ..., хн — последовательность узлов, и пусть С ен г(5).
В качестве представителя С будем выбирать узел х,ен С такой, что г = гп ах (/1х, ~ С). (5.2.4) Таким образом, х,— узел из С, исключенный последним. До сих пор говорилось о структуре данных для фактор-графов и о том, как представлять суперузлы. Другим важным аспектом в реализации факторной модели исключения является преобразование фактор-графа, отвечавшее исключению узла, Рассмотрим поэтому, как можно получить структуру смежности У, из структуры смежности У, ~ при исключении узла хь Это преобразование выполняет слсдуюший алгоритм, Шаг 1 (подготовка).
Определить множества Т= Ао),,г (х,) П г(Зг-1) )г = Кеас)тп, (хо '(5,,)). р 5.2. Машинное представление ерофее исключения Шаг 2 (формирование нового суперузла и разбиения). Образовать х4 = (х4) () Т, г(37) =(г(3,,) — Т) () (хч). Шаг 3 (изменение списков смежности). Аб) (х,) = 7«. л Для уеитт А4Ц„(у)=(х4) () А4Ц (у) — (Т () (х4)). 3( 8) 4 (.:Х:Г"Г3 6 ~ !Д~8 гГ4~ 4 ~~8 Рис. ззна.
Представление структуры смежности. Применим этот алгоритм к преобразованию У4. в Уе в примере на рнс. 5.2.3. В У4 г(54) =(х„хе, х4). Выполняя для узла хе шаг 1, получим Т=( „ и (хе хт Х8) ' Следовательно, новым «суперузлом» будет Хе (Хе) () Х7 () Х4 (Х7 Хе Хи Хе)~ а новым разбиением— 'Рд=( ° '). Наконец, на шаге 3 модифицируются смежные множества: А4Ц, (х,) =- (х„хе), А4Ц,(х,) = (хя), Абтр (х8) (хе, хе, хе, хе) 5 5.5. Алгоритм минимальной степени 119 Аб),„,(хз) =ге =(хз, хт, хз). Воздействие трансформации фактор-графа на структуру данных можно иллюстрировать примером. Будем считать, что для графа иа рис. 5.2.3 структура смежности представлена так, как показано на рис.
5.2.6. Рис. 5.2.7 демонстрирует некоторые важные этапы построения фактор-графов для этого примера. При формировании фактор-графов йгь Уг и 5з струкгура смежности остается неизменной. При преобразовании оз в У4 узлы хз и ха отождествляются, так что в л4 смежное множество для узла х4 содержит смежное множество для (хх, х,) в исходном графе. Этим смежным множеством будет (х;, хт). Последняя ячейка в списке смежности для ха используется для связи. Заметим сп(е, что в списке смежности узла хз сосед хз был заменен в У4 на х„, поскольку узел ха стал предстаиителем компоненты (хз, ха). Представления по этой схеме для Уз и оз также приведены на рис. 5.2.7.
Такой способ представления фактор-графов исключения будет использован в реализации алгоритма минимальной степени, обсуждаемого в б 5.4. Упражнения 5.2.1. а) Составьте подпрограмму под назваклем КЕАСН, которую можно было бы использова~ь для вычисления достижимого множества данного узла )1ООТ через подмножество Я Подмножество задается с помощью массива 5ГьАО. узел ~ принадлежит Я, если переменная ЯгьАО(1) не равна нулю, Опишите параметры подпрограммы и дополнительную память, которая вам потребуется б) Пусть граф хранится парой массивов (ХАОа, АОагчСУ). Используйте подпрограмму КЕАСН для вывода на печать структур смежности графов исключения для любого заданного порядка исключения.
5.2.2. Для множеств Г (Я,), определенных в (5 2.2), показать, что (~(Втн)) <(г(бг) ). 5.2.5. доказать неравенство, используемое при выводе леммы 5.2.3. 5.2А. пусть х =-(с1сезг(5,) для некоторого 1). показать, что (а( м. 5.2.5. Пусть С ен а'(5,) и х, = С, где г = шах (1 ) х1 зв С), доказать, что: а) Аб)а(С) = — Кеасиа(ха 3,); б) )(еасьа[х„ 5,) = )(еасйа(хо 5,-,). 5.2.6 Начертить последовательность (5*~) фактор-графов для звездного графа с семью узлами.
Пеитральиый узел занумероваи первым. $5.3. Алгоритм минимальной степени Пусть А — заданная симметричная матрица, а Р— матрица перестановки. Хозя структуры ненулевых элементов А н РАР различны, их размеры одинаковы, ))з)опг(А)) = ')"гчопг(РАРг)( !20 Гл. д. Универсальные роярвженныв методы Однако, и это обстоятельство огромной важности, между ) 5(опт(Р(А) ) ( и /Хопг (Р(РАР') ) ) для некоторой перестановки Р различие может быть очень велико. Иллюстрация этого факта — пример на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
