Задача-приклад №2:
Виділення внутрішніх комплексів в ТК.
Скласти матрицю зв’язків та виділити внутрішні комплекси на графовій моделі об’єкту, що представлений на рисунку.
Розвязок:
Рис.9. Графова модель об’єкту
Внутрішній комплекс — це множина зв’язаних контурів графа, тобто максимальна можлива множина вершин і дуг, які мають ту властивість, що для будь-яких двох вершин цієї множини існує з’єднуючий їх шлях.
Матриця зв’язків — це квадратна матриця, в якій число стовпців та рядків дорівнює кількості вершин. Номери рядків вказують номери вершин, з яких виходять дуги. Сума одиниць в рядку визначає число потоків з елемента, а сума одиниць в стовпці — число потоків в елемент.
Матриця зв’язків:
і |
j |
||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
8 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Виділення внутрішніх комплексів на графах.
Існують різні підходи, які дають можливість на основі графових моделей виділити внутрішні комплекси, які потім використовуються при розподілених систем управління. Один з алгоритмів виділення внутрішніх комплексів заснований на використанні матриці шляхів на графі (Р-матриця).
Шлях показує множину дуг, за допомогою яких можна попасти з і-ої вершини в j-ту.
Р-матриця:
і |
j |
||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
3 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
4 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
5 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
9 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
10 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
11 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
На основі Р-матриці складається допоміжна S-матриця за таким правилом:
S-матриця:
і |
j |
||||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
3 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
8 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
9 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
10 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
Матриця S дозволяє визначити наявність внутрішніх комплексів, а також тих вершин, які можуть розраховуватись окремо. Якщо в і-тому рядку є лише один ненульовий елемент Sij (на головній діагоналі), то цей елемент можна розраховувати окремо. В даному прикладі — це елементи: 4, 6, 7.
Рядки матриці S, які мають крім ненульового елемента в діагоналі інші ненульові елементи, утворюють внутрішні комплекси.
Отже, можна виділити два внутрішні комплекси (ВК) для даного об’єкту: ВК1, до якого входять такі вершини: 1, 2, 3, 8, 9, 10; та ВК2 з вершинами 5, 11. Ці комплекси зображені на графовій моделі пунктирною лінією.
Рис.10. Виділення внутрішніх комплексів на графовій моделі.