Виявлення топології «дерево»

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аведено алгоритм виявлення топології «дерево», в осноку якого покладено аналіз матриці суміжності.

Алгоритм виявлення топології «дзеркальне дерево» аналогічний алгоритму виявлення топології «дерева» лише з однією відміністю, а саме в першій вершині графа замість операції А: - A_I повинна бути операція А: = A_O.

Висновок

Отже, топологія – це така структура зв’язків між елементами системи, множина відображень яких є гомоморфною.

Топологію можна задавати за допомогою вербально-дедуктивного, графічного, матричного та аналітичного способу.

До графічних способів належать графи та мережі Петрі.

Основною перевагою графічного способу завдання топологій систем з одного боку це висока наочність безпосереднього відображення структури зв’язків між елементами системи, а з другого – достатньо розроблені в теорії графів методи їх опрацювання. Проте, графічний спосіб має й певні недоліки. По-перше, це труднощі автоматичного опрацювання графів в комп’ютерах, що пов’язані з попереднім розпізнаванням графічних образів та потреба великих обсягів пам’яті для зберігання графів. По-друге, це труднощі відображення топологій систем з великою кількістю (понад 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 с.