Автоматизована обробка інформації складних систем проекційними методами, Детальна інформація

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. Структура матриці, що відповідає

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



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

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 SYMBOL 163 \f "Symbol" \s 14 Ј 2, покласти S=C і перейти до

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

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

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

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

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

і N(N – |S|.

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