Аналіз топологій (стр. 2 из 3)
Матриця суміжності з’єднань за виходами – це така матриця суміжності, в якій рядки позначені елементами системи, якими розначені стовпчі матриці.
Тобто, якщо в такій матриці aij=1, то це означає, що вихід i-го елемента системи з’єднаний з входом j-го елемента.
Для тієї ж топології, що на рис.1.1, матриця суміжності з’єднань за виходами Ао буде такою:
Для задання топології систем, що описується неорієнтованим графом, застосовують тільки одну матрицю суміжності А, яка є об’єднанням матриць АІ та Ао
А= АІ 
АО.
Так, наприклад, для топології, що на рис. 1.3, матриця суміжності А буде такою:
Для задання топологій систем іноді застосовують матриці інциденцій
Якщо топологія задається орієнтованим графом G=(B,E), де B={b1,b2,…bn}, D={d1,d2,…dm}, то матриця інциденцій для дуг S матиме такий вигляд:
Наприклад, для топології, що на рис. 1.2., матриця інциденції для дуг S буде такою:
Якщо топологія задається неорієнтованим графом G=(B,E), де B={b1,b2,…bn}, D={d1,d2,…dm}, то матриця інциденцій для ребер R матиме такий вигляд:
Для топології, що на рис 1.3. матриця інциденції для ребер R буде такою:
Цикломатичні матриці, яких ще називають другі матриці інциденції, можуть застосовуватися для опису топологій, що містять v незалежних циклів (контурів). Вони мають такий вигляд:
Так, наприклад, для топології, що на рис. 1.3., цикломатична матриця С, що має один незалежний контур, буде такою:
Можна легко зауважити, що для задання топології цикломатичні матриці є непридатними, бо у випадку відсутності в топології контурів, що часто буває в топологічних системах, такі матриці містять лише нулі, а тому топології не описують.
Матриці інциденції можуть застосовуватися для задання топологій систем, але вони не можуть задавати топології, що містять петлі – контури, що складаються лише з одного елемента. Наприклад, скласти матрицю інциденції для топології (рис.1.1.) є проблематичним. Крім того, елементи таких матриць можуть приймати одне із трьох значень +1,1,0, а тому для перетворення матриць інциденції з метою аналізу заданих топологій потрібно застосовувати або звичайні алгебраїчні операції, які є більш трудомісткі, ніж логічні операції двійкової алгебри логіки, або операції трійкової алгебри логіки, які хоч менш трудомісткі від звичайних операцій, але складніші від операційбулевої алгебри. З цих міркувань монографії для задання топологой систем застосовуються лише матриці суміжності.
Перевага застосування матриці суміжностей полягає у зручності представлення, опрацювання та зберігання в комп’ютерах топологій з довільною кількістю елементів. Такі матриці в комп’ютерах записуються як масиви або списки зв’язності, що очевидно є для них найбільш природним представленням. Враховуючи також і те, що елементи матриць суміжностей приймають тільки два значення, то над ними зручно застосовувати менш трудомісткі операції алгебри логіки та інші спеціальні для аналізу топології систем.
Єдиним, але суттєвим, недоліком матричних способів задання топологій є низька наочність. Тому, для виведення на екран монітора результатів аналізу топологій у відповідних програмах необхіджно передбачити перетворення матриць у графи.
1.3 Аналітичний спосіб
До аналітичних способів задання топологій систем можна віднести логічні схеми алгоритмів (ЛСА). ЛСА спочатку були розролені для компактного опису процесу функціонування цифрових пристроїв у вигляді формул, що можуть складатися з двох об’єктів – операторів та логічних умов. Оператори, як правило, позначаються великими латинськими літерами з індексами чи без них, а логічні умови – малими латинськими буквами (з індексами чи без них) та пронумерованими стрілками, що розміщуються праворуч від логічних умов. Ці стрілки вказують альтернативні маршрутипереходів при різних значеннях логічних умов. ЛСА формується як деяка система послідовностей запису з цих об’єктів, в кожній з яких виконання операторів проводиться послідовно, починаючи зліва.
Якщо операторам ЛСА поставити у відповідність елементи топології системи, то можна отримати її аналітичний опис. Так, наприклад, для топологій (рис.1.2.) аналітичний опис матиме такий вигляд:
Логічні умови р1-р3 виконують функції комутування з’єднань між елементами системи у тому випадку, коли деякий елемент системи з’єднаний одночасно з декількома іншими.
Цілком очевидно, що основна перевага аналітичного способу – це компактність запису топології системи у вигляді системи формул. У зв’язку з цим, його інколи зручно використовувати в теоретичних дослідженнях. Однак, є ряд суттєвих недоліків, а саме: труднощі введення, опрацювання та зберігання в комп’ютерах топологій систем, а також низька наочість представлення топологій. Крім того, виникають додаткові проблеми при заданні аналітичним способом топологій систем, що описуються неорієнтованими графами.
Якщо для порівняння описаних способів задання топологій взяти такі два параметри, як кількість елементів N, з яких складається система, та кількість систем S, топології яких повинні бути задані, то отримаємо співвідношення, наведені на рис.1.6.
Таким чином, для задання топологій систем доцільно використовувати одночасно два способи – графічний для побудови інтерфейсу користувача з метою спрощення процесів створення, введення, коригування топології систем та виведення синтезованої топології та матричний (матриці суміжності) для проведення аналізу, перетворення, зберігання топології в комп’ютері. Аналітичний спосіб не доцільно застосовувати, бо він об’єднує недоліки графічного та матричного.
Розділ 2. Методи виявлення та перетворення топологічних структур
Відомі методи аналізу топологій є або евристичними, особливо для представлення топологій графами, або такими, що базуються на комбінаториці, а відтак передбачають значні затрати часу на виконання великої кількостіпорівнянь.
2.1 Виявлення послідовної топології
Послідовною топологією називається така топологія систем, яка містить n- елементів, серед яких є один вхідний елемент, один вихідний елемент, а решта елементів з’єднані з ними таким чином, що від вхідного елемента до вихідного є лише один маршрут з’єднань (рис.2.1.).
Нехай графічно задана така послідовна топологія (рис.2.2.).
Матриця суміжності з’єднань за входами АІ цієї топології буде такою:
А матриця суміжності з’єднань за виходами А0 буде такою:
На рис.2.3. наведено алгоритм виявлення послідовних топологій, в основу якого покладено аналіз матриці суміжності. В ньому, крім попередніх та загальновідомих позначень , прийнято, що і – номер рядка матриці суміжності, j – номер стовпця матриці суміжності, р – кількість нульових рядків матриці суміжності.
2.2 Виявлення паралельної топології
Паралельною топологією називається така топологія системи, яка містить n елементів, кожен з яких не має жодних зв’язків з іншими (рис.2.4.)
Нехай графічно задана топологія, що наведена на рис.2.5.
Для цієї топології матриця суміжності з’єднань за входами АІ і матриця суміжностей за виходами Ао буде нульовою:
На рис.2.6. наведено алгоритм виявлення паралельних топологій, в основу якого покладено аналіз матриці суміжності.
2.3 Виявлення топології «дерево»
Топологією «дерево» називається така топологія системи, яка містить n елементів (n≥3), серед яких є один вхідний елемент, та m вихідних ((n-1)≥m>1), причому від вхідного до кожного з вихідних елементів є лише один маршрут з’єднання (рис.2.7.).
Топологією «дзеркальне дерево» називається така топологія системи, яка містить n елементів (n≥3), серед яких є m вхідних елементів ((n-1)≥m>1) та один вхідний елемент, а від кожного вхідного елемента до вихідного є лише один маршрут з’єднань (рис.2.8.).