Математичні моделі та методи аналізу й синтезу топологій комп'ютерних видавничо-поліграфічних систем

Розділ 2
МАТРИЧНІ МОДЕЛІ ТА МЕТОДИ ВИЯВЛЕННЯ Й ПЕРЕТВОРЕННЯ ТОПОЛОГІЧНИХ СТРУКТУР
Відомі методи аналізу видів топологій є або евристичними [8-10], особливо тоді,
коли моделями топологій є графи, або такими, що базуються на комбінаториці, а
відтак передбачають значні затрати часу на виконання великої кількості
порівнянь [2, 11, 108].
В цьому розділі розглядаються матричні моделі для всіх видів топологій
комп’ютерних видавничо-поліграфічних систем та методи виявлення й перетворення
топологічних структур комп’ютерних видавничо-поліграфічних систем, що базуються
на матричних моделях топології у виді матриць суміжностей.
2.1. Матричні моделі видів топологічних структур
Усе розмаїття топологічних структур комп’ютерних видавничо-поліграфічних систем
можна поділити на такі види [39]:
• послідовну;
• паралельну;
• “дерево”;
• деревоподібну;
• циклічну.
Означення 2.1. Послідовною топологією називається така топологія системи, яка
містить n елементів, серед яких є один вхідний елемент, один вихідний елемент,
а решта елементів з’єднані з ними таким чином, що від вхідного елементу до
вихідного є лише один маршрут з’єднань (рис. 2.1).
Рис. 2.1. Граф послідовної топології
Приклад 2.1. Нехай графічно задана така послідовна топологія системи (рис.
2.2).
Рис. 2.2. Приклад графа послідовної топології
Матриця суміжності з’єднань за входами AI цієї топології буде такою:
а матриця суміжності з’єднань за виходами АO буде такою:
Означення 2.2. Паралельною топологією називається така топологія системи, яка
містить n елементів, кожен з яких не має жодних зв’язків з іншими (рис. 2.3).
Рис. 2.3. Граф паралельної топології
Приклад 2.2. Нехай графічно задана паралельна топологія системи, що наведена на
рис.2.4.
Рис. 2.4. Приклад графа паралельної топології
Для цієї топології матриця суміжності з’єднань за входами AI і матриця
суміжності з’єднань за виходами AO буде нульовою:
, .
Означення 2.3. Топологією “дерево” називається така топологія системи, яка
містить n елементів , серед яких є один вхідний елемент, та m вихідних ,
причому від вхідного до кожного з вихідних елементів є лише один маршрут
з’єднань (рис. 2.5).
Рис. 2.5. Граф топології “дерево”
Означення 2.4. Топологією “дзеркальне дерево” називається така топологія
системи, яка містить n елементів , серед яких є m вхідних елементів та один
вихідний елемент, а від кожного вхідного елемента до вихідного є лише один
маршрут з’єднань (рис. 2.6).
Рис. 2.6. Граф топологій “дзеркальне дерево”
Слід зазначити, що тут топологія “дерево” включає топологію “зірка”, яка
знайшла застосування в комп’ютерних мережах [16], як частковий випадок.
Топологія “зірка” розглядається як топологія “дерево”, в якій є один початковий
елемент, що відповідає центральному елементу “зірки”, а решта — кінцеві
елементи. Крім того, передбачається, що в топології “дерево” кожен елемент,
крім кінцевих, може мати різну кількість зв’язків з іншими елементами.
Приклад 2.3. Нехай графічно задана така топологія “дерево” системи (рис.2.7).
Рис. 2.7. Приклад графа топології “дерево”
Матриця суміжності AI цієї топології буде такою:
а матриця суміжності AO буде такою:
Означення 2.5. Деревоподібною топологією називається така топологія системи,
яка містить n елементів, серед яких є f вхідних елементів, m вихідних
елементів, причому від одного вхідного елемента до одного вихідного елемента
може бути більше одного маршруту з’єднань.
Приклад такої топології приведений на рис. 2.8, а відповідно цій топології
матриця суміжності з’єднань за входами буде такою:
.
Можна легко зауважити, що в топології на рис. 2.8 від третього вхідного
елемента до восьмого вихідного елемента є два альтернативні маршрути (шляхи):
“3-4-5-7-8” і “3-4-9-7-8”.
Рис. 2.8. Приклад графа деревоподібної топології
Інший приклад деревоподібної топології був наведений в розділі 1 на рис. 1.2.
Означення 2.6. Циклічною топологією називається така топологія системи, в якій
в межах якогось маршруту від вхідного до вихідного елементу є хоч би один
елемент, вихід якого з’єднаний із входом попереднього до нього, по ходу
маршруту, елемента.
Очевидно, що таке з’єднання утворює контур.
Цілком зрозуміло, що циклічну топологію можна утворити з усіх попередніх типів
топологій — послідовної, паралельної, “дерево” та деревоподібної шляхом
внесення зворотних зв’язків між елементами цих топологій.
На рис. 2.9 приведено приклад графа циклічної топології, утвореної із
послідовної топології введенням трьох зворотних зв’язків, а відповідна матриця
суміжності з’єднань за входами буде такою:
Рис. 2.9. Приклад графа циклічної топології, утвореної із послідовної
В ній, як видно із рис. 2.9, елементи 1, 3, 4, 5 утворюють три контури: перший
— “3-5-1-4-3”, другий — “3-5-1-3” і третій — “5-5”.
На рис. 2.10 наведено приклад графа циклічної топології, утвореної із
паралельної топології шляхом введення одного зворотного зв’язку типу петля.
Рис. 2.10. Приклад графа циклічної топології, утвореної із паралельної
Відповідна цій топології матриця суміжності з’єднань за входами буде такою:
В цій топології є тільки один контур “1-1”, утворений першим елементом.
В циклічних топологіях, утворених з паралельних, в матриці суміжності з’єднань
за входами та матриці суміжності з’єднань за виходами є однаковими та містять
одиничні елементи лише на головній діагоналі.
На рис. 2.11 наведено приклад графа циклічної топології, утвореної із топології
“дерево”, в якій елементи 3, 4, 5, 6 утворюють такі контури: “3-4-5-6-3”,
“4-5-4”, “5-5”.
Рис. 2.11. Приклад графа циклічної топології, утвореної із “дерево”
Для цієї топології відповідна матриця суміжності з’єднань за входами буде