76 77 78 79 80 98 32 31 30 29

71 72 73 74 75 97 28 27 26 25

66 67 68 69 70 96 24 23 22 21

61 62 63 64 65 95 20 19 18 17

56 57 58 59 60 94 16 15 14 13

51 52 53 54 55 93 12 11 10 9

46 47 48 49 50 92 8 7 6 5

41 42 43 44 45 91 4 3 2 1

Мал. 2. Однорівневе упорядкування Мал. 3. Структура матриці, що відповідає

за допомогою перетинів сітки (1010) однорівневому упорядкуванню за. допомогою перетинів.

Щоб одержати упорядкування, що відповідає методу вкладених перетинів, перейдемо до перетину двох компонент, які ще зостались. Виберемо множини вершин

Sj Rj , j = 1,2, ... ,

сіткових ліній, що складаються з вузлів, що поділяють Rj на рівні (по можливості) частини. Якщо змінні, асоційовані з вершинами з Rj – Sj, ми перенумеруємо до того, аніж ті змінні, що асоційовані з вершинами Sj, то таким чином ми побудуємо на двох головних підматрицях точнісінько ту ж структуру, що і на всій матриці.

Процес можна продовжувати, поки не залишаться вже неподільні компоненти. Це і дає упорядкування за допомогою вкладених перетинів.

Алгоритм вкладених перетинів. Як знайти малий роздільник, який розбив би заданий граф на компоненти приблизно однакового розміру?

Запропонований інтуітивний метод складається з побудови для графа довгої структури рівнів і вибору малого роздільника з "середнього" рівня.

Нехай G=(X,E) - заданий граф. Алгоритм упорядкування за допомогою перетинів можна описати так:

А Л Г О Р И Т М:

ПОЧАТОК

Крок 1 (ініціалізація). Покласти R=X, N=|X|.

Крок 2 (побудувати структуру рівнів). Знайти в G(R) зв”язану

компоненту G(C) і побудувати для неї структуру рівнів із

коренем у псевдопериферійному вузлі r:

Z(r)={L0, L1, ... , Li}.

Крок 3 (знайти роздільник). Якщо l 2, покласти S=C і перейти до

кроку 4. У противному випадку покласти j=[l + 1)/2] і

визначити множину S L таке, що

S = {y Lj | Adj(y)Lj + 1 }.

Крок 4 (упорядкування роздільника і цикл). Перенумерувати вузли

роздільника S числами від N – |S|+1 до N. Покласти RR-S

і NN – |S|.

Якщо R 0, перейти до кроку 2.

КІНЕЦЬ

На кроку 3 алгоритму роздільник S можна одержати простим відкиданням тих вузлів з Lj, що не суміжні з жодним вузлом із Lj+1. У багатьох випадках це зменшує розмір роздільника.

Використана література

Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. _М.: Наука, 1981. – 256 с.

Зенкевич О., Чанг И. Метод конечных элементов в теории сооружений и в механике сплошных сред. – М.: Недра, 1974. – 240 с.

Корячко В.П. Курейчик В.М., Норейков Н.П. Теоретические основы САПР. – М.: Энергоатомиздат, 1987. – 400 с.

Джордж А., Ли Дж. Численное решение больших разреженных систем уравнений. – М.: Мир, 1984. – 287 с.

Додатки