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

за допомогою перетинів сітки (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 £ 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|.