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