Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 8
Текст из файла (страница 8)
Наконец, находим ПИК(2) = — 5, что указывает окончание списка смежности для узла 5. (Вообще отрицательная связь — 1 указывает окончание списка смежности ПЗ Гя. 3. Некоторые сведения ив теории ерафов для узла ь) Общая длина массивов при таком способе представления графа равна !Х! 4-4!Е!, что существенно больше, чем в схеме хранения, используемой в наших ьрограммах.
Если в массивах НВ)кЯ и 1.1(у)К достаточно места, то легко можно добавлять новые ребра. Например, чтобы добавить к структуре смежности ребро (3, 6), изменим список смежности узла 3, полагая 1.1МК(13) = 1, )У!В)(Я(13) = 6, НЕАР(3)=13. Аналогичным образом изменим список смежности узла 6, полагая 11ХК(! 4) = 5, !У)ВЙЯ(14) = 3, НЕАР(6)=!4.
$3.3. Некоторые общие сведения о подпрограммах, оперирующих с графами В последующих главах будут описаны многочисленные подпрограммы, оперирующие с графами. Во всех этих подпрограммах граф 6 =(Х, Е) хранится посредством пары целых массивов (ХАМ, АРЗХСУ), как разъяснено в $3.2. Помимо этого, у многих подпрограмм есть и другие общие параметры. Чтобы избежать многократного описания таких параметров в дальнейшем, обсудим их роль здесь, а затем, в сл)чае необходимости, будем отсылать читателя к данному разделу. Должно быть ясно, что сам факт хранения графа посредством пары массивов (ХАЩ АРЗХСУ) предполагает конкретное помечивание этого графа.
Такое упорядочение будем называть исходной нумерацией, и если мы говорим об «узле !», то имеем в виду именно эту нумерацию. Когда подпрограмма находит новое упорядочение, информация о нем хранится в массиве РЕЯМ; при этом РЕ)кМ(!)=й означает, что узел с номером й в исходной нумерации имеет номер ! при новом упорядочении.
Часто будет использоваться и родственный вектор перестановки 1)нЧР (обратная перестановка); он имеет длину М и 1НЧР(РЕЯМ(!)) = й Таким образом, 1ЫЧР(й) указывает положение в массиве РЕЯМ узла, который в исходной нумерации имел номер л. Во многих наших алгоритмах необходимо оперировать лишь некоторыми подграфами графа О. Чтобы реализовать эти операции, ряд наших подпрограмм использует для задания подграфа целый массив МАЯК длины Лг.
Подпрограммы принимают в учет только те узлы 1, для которых МАЯК(!) ныл. На рис, 3,3.1 представлен пример, иллюстрирующий роль целого массива МАЯК. Наконец, некоторые наши подпрограммы имеют параметр, обычно называемый КОРТ, указывающий номер узла, для ко. торого МАЯК (КОРТ)ФО. Эти подпрограммы, как правило, оперируют с той связной компонентой подграфа, заданного массивом МАЯК, которая содержит узел ЙООТ. Таким образом, б 3.8. Подпрограмма, оперирующие с графами 33 комбинация КООТ и МАЯК определяет тот связный подграф в 6, который нужно обработать. Для ссылки на этот связный подграф мы часто будем пользоваться словосочетанием «компонента, задаваемая посредством КОРТ и МАЯК». Например, Пайераф графа О, аааабаемагй массибам МАзК 1йа<р (Р помеченный б соотбеагснгбии со схемой йронвнин нарос.
3.2.1 Рис. 3.3Л. Пример, показываюгний использование массива МА5К для задания нодграфа в графе б. комбинация (сООТ = 2 с массивом МАЯК и графом 6 на рис. 3.3.1 задает граф Резюмируя, перечислим некоторые часто используемые параметры наших подпрограмм вместе с их описанием: (ХАР), АРЯНС'г') Пара массивов, хранящая граф при исходном упорядочении. Исходные метки узлов, смежных с узлом 1, находятся в позициях АРЯМСУ(й), где ХАШ(1) ~ й(' =' ХАШ(г'+ 1); ХАРЯ(Аг+ 1) = 2(Е(+!. РЕЯМ Целый массив длины Аг, содержащий новое упорядочение. 1ЫЪ'Р Целый массив длины Ф, содержащий обратную перестановку.
МАЯК Целый массив длины Аг, используемый для задания подграфа в графе 6. Подпрограмма игнорирует те узлы, для которых МАЯК(г) = О. гсООТ Номер узла, для которого МАЯК(КООТ)~0. Подпрограмма обычно оперирует с той компонентой подграфа, заданного массивом МАЯК, которая содержит узел БООТ. 64 Гл.
3. Некоторзге сведения иэ теории графов Упражнения 3.3.1. Предположим, что для представления графа С (Х, Е) использована нижняя структура смежности. Это значит. что вместо хранения для каждого узла х полного смежного множества Ад)(х) мы храним только те узлы нз Ад)(х), метки которых большц чем у х. Например, граф рисунка 3.2.1 можно представить с помощью пары массивов (.АШ н ХВАШ, как показано ниже. Х1 АШ УУвгпУУма 1 4 3 4 5 6 Составьте подпрограмму, которая преобразует нижнюю структуру смежности в полную.
Считайте, что вы располагаете массивом 1АШ длины 2(Е), содержащим в первых (Е1 позициях нижнюю структуру смежности, н массивом Х(.АШ. Кроме то~о, имеется рабочий массив длины (Х!. Когда программа заканчивает работу, массивы Х1АШ н (.АШ должны содержать элементы массивов ХАШ и АШНСТ, как это описано в 3 3.2. 3.3.2. Предположим, что несвязный граф С = (Х, Е) хранится парой массивов ХАШ н АОЗНСУ в соответствии с описанием 5 3.2, Напишите подпрограмму, для которой узел л ш Х нвляется входным параметром н которая выдает узлы связной компоненты С, содержащей х. Убедитесь, что вы описали все параметры подпрограммы и все виды необходимой вспомогательпоп памяти.
33.3. Предположим, что (возможно, несвязный) граф С = (Х, Е) хранится парой массивов ХАШ и АШНС'т' в соответствии с описанием 4 3.2. Пусть подмножество У ~ Х задано целым массивом МАЯК длины Аг, нак это разъяснено в $3.3. Составьте программу, для которой входными параметрами были бы число АГ и массивы ХАРд, АШНС'т' н МАЯК н которая выдавала бы число связных компонент подграфа С(У). Чтобы ваша программа была проще и удобнее для чтения, может потребоваться рабочий массив длины Лг. 3.3.4.
Предположим, что граф матрицы А хранится парой массивов (ХАШ, АШ)чСУ) в соответствии с описанием э 3.2, и пусть массивы РВмМ н !ы)гР соответствуют матрицам перестановок Р н Р" (см $33). Напишите подпрограмму, выдающую столбцовый индекс первого ненулевого элемента наждой страни матрицы РАР'. Ваша программа должна также печатать число ненулевых элементов слева от диагонали в каждой строке РАР'. 3.3.5. Составьте программу, натирая отличалась бы от программы упр.
3 3.4 только той дополнительной особенностью, что она оперирует с подматрицей матрицы РАР', задаваемой массивом МАЯК 3.3.6. Предположим, что входной граф задан последовательностью ребер (пар номеров узлов) и длины списков смежности заранее не известны На. пишите программу под названием 1НЯЕЙТ, с помощью которой можно было бы построить связные списки смежности, пример которых показан на рис 323, Убедитесь, что вы ничего пе упустнлн в списке параметров, в обдумайте, как следует присвоить начальные значения массивам Вы ие должны предполагать, что числа (Х( и ( Е~ известны заранее. Предусмотрите нестандартные ситуации, например, массивы не вмещают все ребра, илн некоторое ребро ввв. дено повторно, н т. д. в 3.3. Подпрограммы, оперирующие с графами 55 3.3.7.
Предположнм, что граф матрнцы А хранятся парой массивов (ХАРЯ, АВАНСУ) в соатвегсхвяа с описанием 3 3.2. Составьте программу, для которой входом бычн бы зтн хва массива вместе с двумя номерами узлов ! н г н которая бы опредвзаиа, схнеется ля в графе соединяющнй их путь. Если да, программа выдает длину такого кратчайшего пути; в противном лучае ока выдаат нуль. Опасать все рабочие массивы, которые вам понадобятся.
33,3. Составьте программу, которая отличалась бы от программы упр. 337 только той дополнительной особенностью, что она оперирует с подграфом, за. даваемым масснвом МАЯК 4. Ленточные и профильные " методы й 4.0. Введение В этой главе мы рассмотрим один из простейших подходов к решению разреженных систем, а именно ленточные схемы и тесно связанные с ними оболочечные, или профильные, методы.
Говоря приблизительно, цель здесь состоит в таком упорядочении матрицы, чтобы ненулевые элементы РАР" группировались «возле» главной диагонали. Поскольку это свойство сохраняется:оответствуюшим множителем Холесского ~., такие упорядочения привлекательны с точки зрения сокрашения заполнения и широко используются в практике (Сц(11!П 1972, ге!!рра 1975, Ме1оз)т, Ватп!огд 1969). Хотя эти упорядочения зачастую далеки от оптимальных в смысле критерия наименьшей арифметики или наименьшего заполнения, они являются практически выгодным компромиссом.
Как правило, программы и структуры данных, нужные для эксплуатации создаваемой ими разреженности, относительно просты; тем самым издержки в памяти и вычислительной работе для них малы в сравнении с более сложными упорядочениями (вспомните замечания в $ 2.3). Само получение упорядочений обычно значительно дешевле, чем для (теоретически) более эффективных методов. Для малых задач и даже задач среднего размера, которые нужно решать лишь в небольшом количестве, возможность применения методов, описываемых в этой главе, должна рассматриваться всерьез. й 4.1. Ленточный метод Пусть А — симметричная положнгельио определенная матрица порядка 7т' с элементами ач.
Для с'-й строки А, ! = 1, 2,... ..., й!. положим )т(А) =гп(п(! !аи ~ь О) В,(А) =1 — 1,(А). В оригииале — епте!оре гпейобв Мы предпочли буквальному переводу «оболочечиые методы» терпки «профильные методы»,— Прин, перев, й 4.!. Ленточный метод 67 Число (,(А) — это столбцовый индекс первого ненулевого эле- мента рй строки А. Так как диагональные элементы ао положи- тельны, имеем ~, (А) ((, й~ (А):-» О. Вслед за Катхиллом и Макки определим ширину ленты А как ') 13 (А) = ох а х (й, (А) ! 1 ( ( ~~ У) = гпах(1 г' — 1'1~ а„~ О).
Число р,(А) называется ачй шириной ленты А. Ленту определяем таким образом: Вано(А)=(((, 010 <ю' — /~ )1(А)), т. е. как область матрицы, удаленную от главной диагонали нс более чем на р(А) позиций. Поскольку А симметрична, в (4.1,1) (4.1.1) (т(А ) Рнс. 4.(Л. Пример, показывающий й(А) и Р,(А). используются неупорядоченные пары (й 1). Матрица на рис. 4.1.1 имеет ширину ленты, равную трем. Матрицы с шириной ленты, равной единице, называются трехдиагональными. Применение ленточного метода подразумевает, что нули вне Вано(А) игнорируются; нули же внутри ленты обычно хранятся, хотя их присутствие часто используется на этапе численного решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
