Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 17
Текст из файла (страница 17)
6.1.2. Рзссмотрнм звездный граф с 7 узлзмн (рнс. 4.2.3), Предполагая, что центральный узел нумеруется первым, определите последовзтельность грзфов исключения. 6.1.3. Для данного помеченного графа бг = (Хг, Е") показать, что ((езсЬ(хи (хь хт, .... х! !)) ~ Лб1((хь кз, ..., х,)) Вывести отсюда, что ГВ1(А) ~ Епч(А). 6.1.4. Покзззть, что подгрзф Лл ()(езсЬ (хо (хь ..., х, ~)) 0 (хг)) является кликой в графе заполнения бг 6.!.6. (йоге !972з) Граф называется гриаыгулирозаыыым, если для кзждого цнклз (хь хг, ....
хь х~) ллнны () 3 найдется ребро, соединяющее две несоседнне вершины цнклз. (Тзкое ребро называется хордой цикла.) Покажите, что следующие условия эквивалентны: в) граф Лг трнзнгулнровзн; б) существует матрица перестановки Р, текля, что Р!Н (РАРг) б.!.6. Похзззть, что граф Л"к' трязнгулнровзн. Указать перестзновку Р такую, что РН!(РР(А)Р') = Ж Вывести отсюда (нлн доказать каким-либо иным способом), что Ыопз (Р (А)) = Ыопх (Р(Р (А))). бл.?.
Пусть 5 ш. Т н у Ф Т Показать, что ((езсЬ (у, 5) ~= йезсЬ (у, Т) 0 Т. 6.1.8. Пусть у ~ 5. Определим окрестность у в 5 кзк множество ЫЬгЬб (у, 5) = (зев 5(з достижимо нз у через подмножество множества 31. Пусть х ф 5. Показать, что если Аб)(х) ш )?езсЬ (у, 5) 0 ХЬгЬб (у, 5) 0 (у1, з) ЫЬгЬб(х, 5) щ ЫЬгьб(у, 5), б) кезсЬ(х, 5) ~ (?езсЬ(у, 5) 0 (у). 6.!.9. Гкокзззть теорему б.!.3 $3.2. Машинное представление графов исключения Как уже говорилось в 35.1, гауссово исключение для разреженной симметричной линейной системы можно моделировать последовательностью графов исключения. В атом разделе ') Со структурой (Чопх(А).
— Прим. перев. !08 Гв б. Универсальные раврвненные методы мы изучим способы машинного представления и преобразования графов исключения. Эти вопросы важны для реализации универсальных разреженных методов. Б.2.1. Явные и неявные представления Графы исключения являются в конечном счете симметричными графами, поэтому они могут быть представлены посредством одной из описанных в 5 3.2 схем Однако нам важно, чтобы представление было подогнано под исключение, так чтобы в последовательности графов исключения можно было легко выполнять переход от любого члена к следуюшему.
Исследуем шаги преобразования, Пусть 6,— граф исключения, полученный из 6, ~ исключением узла хь Структуру смежности 6, можно найти следуюшим образом Шае 1. Определить смежное множество Аб!а,,(х,) в гра. фе 6 Шаг 2. Удалить узел х, и его список смежности из структуры смежности. Шаг 8. Для каждого узла у~ Ад!а,, (х,) новый спнсои смежности у в 6, получается объединением подмножеств Ад)а, (у) — (хг) и Ад!а (хо) — (у) Это — алгоритмическая формулировка рецепта Партера (раздел 5.1.1) для выполнения преобразования Нужно отметить два момента, связанные с реализацией. Во-первых, место, занимаемое в структуре смежности множеством Ад)а,,(х,), можно после шага 2 использовать для других целей Во-вторых, явния структура смежности для 6, может потребовать значительно большей памяти, чем структура 6, ь Например, если в звездном графе с М узлами (рис.
4.2.3) центральный узел нумерован первым н 6о= (Хо Ео) 61= (ХьЕо) — соответствуюшие графы исключения, то легко показать (см упр. 5.!.2), что ! Ео ! = О (Ф) а ! Е, != — 0(Ф'). Эти замечания показывают, что явная реализация, поэзо ляюшая динамическое изменение структуры ~рафов исключения, должна использовать очень гибкую структуру данных Подходяшей кандидатурой являются описанные в $ 3.2 связные списки смежности, Всякое явное машинное представление имеет два недостатка.
Во-первых, за гибкость структуры данных приходится расплачиватьая значительными издержками в памяти и време- О д2. Маеииннов лрвдставление ерафов исключения 109 ни исполнения. Во-вторых, максимум необходимой памяти непредсказуем, Памяти должно хватать для наибольшего ') из получающихся графов исключения 6,, Это может значительно превысить память, требуемую для хранения исходного графа 6о. Максимум этого превышения неизвестен до самого конца про. цесса исключения Теорема 5 1 3 дает другой способ представления графов исключения Онп могут храниться неявно посредствоч исходного графа б и исключенного подмножества 5,.
Множество узлов, смежных с у в те„ктожно получгпь, генерируя по исходному графу достижимое множество аеас)4(у,5,). Это неявное представление не имеет недостатков, свойственных явному методу. Запросы к памяти здесь скромны и предсказуемы, и структура смежности заданного графа сохраняется. Однако работа, необходимая для построения достижимых множеств, может оказаться чересчур большой, особенно на поздних этапах исключения, когда велико число )5,). В следующем разделе мы рассмотрич другую модель, более приспособленную для машинной реализации и сохраняющую многие иэ достоинств техники достижимых множеств.
5.2.2. Модель фактор-графов Рассмотрим вначале процесс исключения для графа, изображенного на рис. 5.1.6. После исключения узлов хь х,, ха, хо, Рис. бати. Пример графа и сватается куюшего графа исключения х, получается граф исключения, приведенный на рис. 5 2.1. Заштрихованы на нем исключенные узлы Пусть 5 = (хь хш хм хе, ха) Чтобы, пользуясь неявной моделью, установепь, что то и= Кеас)4(хт„5), нужно найти путь (Хт Х4 Ха Хк, Хо). ') Здесь слово «наибольший» относится к числу ребер, а ие к числу уалоо. 110 Гл.
Ю. '«нлвнрсальныл разреженные млтодм Аналогично хз ев КеасЦхт, Я), поскольку существует путь (хт, хы хз, хз, хы хз). Отметим, что длины этих путей равны 4 н 5 соответственно. Сделаем следующие два замечания: а) работу по генерированию достижимых множеств можно было бы сократить, если бы были уменьшены длины путей к неисключенным узлам; б) если эти пути укоротить до предела, мы получим явные графы исключения с теми нежелательными их свойствами, какие были отмечены в предыдущем разделе.
Поищем компромиссное решение. Отождествляя связанные исключенные узлы, мы получим новую графовую структуру, Рмс. З.2.2. Граф, полученный отождествлением связанных исключенных узлов. полезную для наших целей. Например, на рис. 5.2.1 в графе б(5) имеются две связные компоненты; соответствующие множества узлов суть (хьхьхьха) и (хз). Образуя два «супер- узла», придем к графу, изображенному на рис. 5.2.2. Удобйо обозначать эти связные компоненты 5 через хз = = (хо ха,хч, хз) и хз = (хз). Замечаем, что в новом графе пути (хт, хз, хз) и (хт, хч, хз) имеют длину два н ведут от узла х, к хз и хз соответственно.
В общем случае, если мы принимаем эту стратегию, длины всех таких путей не превосходят 2. Это очевидное преимушество по сравнению с генерированнем достижимых множеств на исходном графе, где пути могут быть произвольной длины (меньшей чем М). А каковы преимущества по отношению к явным графам исключения? В следующем разделе мы покажем, что данный метод можно реализовать на месте; т. е. не требуется дополнительной памяти по сравнению с исходной графовой структурой. Короче, новая структура графов позволяет весьма эффективно генерировать достижимые' множества (или смежные мно- Э Ю.2. Машинное представление графов исключения 111 жества в графе исключения) и при этом использует фиксированное место в памяти.
Чтобы формализовать зту модель исключения, введем понятие фактор-графа. Пусть О = (Х,Е) — заданный граф, ч)— разбиение его множества узлов Х: н (! и )2~ )р). Р Это значит, что () Уи = Х и У, П У, = О для 1 Ф !. Определим 2 фактор-граф графа 6 относительно $ как граф ($, д'), для которого (У„уд ен д' тогда и только тогда, когда А1Ц(У,)() Уг Ф 2о.
Этот граф в дальнейшем часто обозначается через 6/$» Например, граф на рис. 5.2.2 есть фактор-граф для графа на рис, 5,2.! относительно разбиения (х, х, х, хд, (хд, (хд, (хт), (хд (хд. Понятие фактор-графа более подробно будет исследовано в главе 6, где рассматриваются блочные матрицы. Здесь мы изучим роль этих графов в моделировании исключения. Новая модель изображает процесс исключения как последовательность фактор-графов.
Пусть О = (Х, Е) — заданный граф. Рассмотрим этап исключения, соответствующий множеству 5 исключенных узлов. Сопоставим ему фактор-граф относительно множества 5, как это подсказывает пример на рис. 5.2.2, Определим множество г(5) = (5.2.!) (С ~ 5) 6(С) — связная компонента в подграфе 6(5)) и разбиение множества Х: г(5) =((у) ~учи Х вЂ” 5) () г(5). Они однозначно определяют фактор-граф 6/г (5); можно счьыать, что этот граф получен отождествлением связанных узлов в 5. Граф рис. 5.2.2 есть фактор-граф относительно множества 5 = (хь х2, хз, хь хе).
Изучим теперь связь фактор-графов с исключением. Пусть хь х2, ..., хн — поРЯдок исключениЯ Узлов в заданном гРафе О. Как и прежде, положим 51=(хь х2, ° ° °, хе), ! <(<у. Для каждого 1 подмножество 5~ индуцирует разбиение е (52) и соответствующйй фактор-граф и'г = ОР(52) =(е(52), Ю'2) (6.2.3) 112 Га 5. Унаеерсальные разреженные методы Таким образом, по заданной последовательности исключения узлов определяется последовательность фактор-графов 5,--~2--...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
