Для топології, що на рис 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 - номер стовпця матриці суміжності, р - кількість нульових рядків матриці суміжності.
8
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.).
Нехай графічно задана така топологія «дерево» (рис.2.9)
Матриця суміжності АІ цієї топології буде такою:
а матриця суміжності Ао буде такою:
На рис.2.10. yаведено алгоритм виявлення топології «дерево», в осноку якого покладено аналіз матриці суміжності.
Алгоритм виявлення топології «дзеркальне дерево» аналогічний алгоритму виявлення топології «дерева» лише з однією відміністю, а саме в першій вершині графа замість операції А: - AI повинна бути операція А: = AO.
Висновок
Отже, топологія - це така структура зв'язків між елементами системи, множина відображень яких є гомоморфною.
Топологію можна задавати за допомогою вербально-дедуктивного, графічного, матричного та аналітичного способу.
До графічних способів належать графи та мережі Петрі.
Основною перевагою графічного способу завдання топологій систем з одного боку це висока наочність безпосереднього відображення структури зв'язків між елементами системи, а з другого - достатньо розроблені в теорії графів методи їх опрацювання. Проте, графічний спосіб має й певні недоліки. По-перше, це труднощі автоматичного опрацювання графів в комп'ютерах, що пов'язані з попереднім розпізнаванням графічних образів та потреба великих обсягів пам'яті для зберігання графів. По-друге, це труднощі відображення топологій систем з великою кількістю (понад 30) елементів і як наслідок - втрата наочності. По-третє, одна і та ж топологія системи може бути задана великою кількістю еквівалентних графів із різним геометричним зображенням.
До матричних способів відносяться: матриці (суміжності, інциденції, цикломатичні), n-мірні таблиці (масиви), n-мірні куби.
До аналітичних способів задання топологій систем можна віднести логічні схеми алгоритмів (ЛСА).
Додаток 1
Текст програми виявлення послідовної топології
tic
n=15;
A(1:n,1:n)=0;
A(1,7)=1;
A(1,13)=1;
A(3,13)=1;
A(3,14)=1;
A(4,15)=1;
A(5,1)=1;
A(6,9)=1;
A(7,3)=1;
A(8,12)=1;
A(9,8)=1;
A(10,11)=1;
A(11,2)=1;
A(12,10)=1;
A(13,4)=1;
A(14,7)=1;
A(15,13)=1;
d=A
p=0;
for i=1:n;
c=d(i,:);
if sum(c)==0;
p=p+1;
if p>1
z=0;
break
end
else
if ~(sum(c)==1)
j=i;
if d(i,j)==1
z=1;
if p==0
for j=1:n
c=d(:,j);
if sum(c)==0
if j==n
z
toc
Додаток 2
Текст програми виявлення паралельної топології
n=5;
A(1,1)=1;
A
c=0;
for i=1:n
c=c+A(i,j);
if c>0
input(' topologia ne paralelna')
input('topologia paralelna')
Додаток 3
Текст програми виявлення топології «дерево»
n=7
A (1:n,1:n)=0;
A(1,4)=1;
A(2,4)=1;
A(4,3)=1;
A(5,3)=1
A(6,5)=1;
A(7,5)=1;
if sum (c)==0;
if~(sum(c)==1)
p=0
c=d(:j);
if sum (c)==0
z=1
z=0
top
if z==1
disp (`topologia derevo')
disp (`topologia ne derevo')
Список викоhистаної літератури
Дунець Р.Б. Аналіз та синтез топологій комп'ютерних видавничо-поліграфічних систем: монографія. - Львів: НВФ “Українські технології”, 2003.
Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. - Спб Питер, 2004.
Берж К. Теория графов и ее применение. - М.: Иностранная литература, 1962.- 320 с.
Оре О. Теория графов. - М.: Наука, 1980.-336 с.
Дунець Р., Басюк Т. Структура програми перетворення графів в ярусно- паралельну форму//Комп'ютерні технології друкарства. - 2002. - №7. - С.97-102.
Капитонова Ю.В., Летичевский А.А. Математическая теория вычислительных систем. - М.: Наука, 1988. - 295 с.
Шатихин Л.Г. Структурные матрицы и их применение для исследования систем. - М.: Машиностроение, 1991. - 253 с.
Страницы: 1, 2
