Аналіз топологій

Зміст

Вступ

Розділ 1. Способи задання топологій

Графічний спосіб

Матричний спосіб

Алгебраїчний спосіб

Розділ 2. Методи виявлення та перетворення топологічних структур

Виявлення послідовної топології

Виявлення паралельної топології

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

Висновок

Додатки

Список використаної літератури

Вступ

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

Для задання топологій можуть застосовуватись такі способи:

вербально-дедуктивні;

графічні;

матричні;

аналітичні.

Вербально-дедуктивний або словесно-логічний спосіб застосовується, як правило, на початку проектування систем, найчастіше на етапі формування технічного завдання. Цей найбільш простий і доступний спосіб для різних спеціалістів, які можуть бути залучені до створення систем, не маючи спеціальних знань. Однак, цей спосіб практично не має наочності і зовсім не придатний для проведення певних формальних перетворень топологій як ручним, так і автоматичним (машинним) способом. Якщо цим способом вдається описати топологію системи лаконічно, то опис, як правило, є неповним і вимагає від спеціалістів попереднього уточненняосновних понять та положень.

Як відомо, задачі аналізу топологій зводяться до виявлення в графах різних шляхів між початковими та кінцевими станами, контурів чи циклів, остові дерева, множини станів (вершин) чи дуг, що задовільняють певні умови тощо. Проте, ці методи аналізу топологій, що базуються на графах, є фактично ручними методами і не зовсім підходять до машинних методів, які використовуються длоя побудови програмних продуктів, оскільки графи в комп’ютерах не можуть безпосередньо вводитися, опрацьовуватися чи зберігатися в пам’яті. Найбільш придатними для цього є матричні методи аналізу та синтезу топологій. Однак, ці матричні методи в основному орієнтовані на зв’язок тільки деяких класичних задач (пошук контурів, украдки графів, перетворення матриць до певного виду, тощо) територій графів. Окремі способи були зроблені в розвитку матричних методів для синтезу систем керування та мінімізації логічних функцій, але цілісного підходу до створення матричних методів для аналізу та синтезу систем, зокрема комп’ютерних видавничо-поліграфічних не було.

Аналіз та синтез в класі станів зводиться до формалізованої моделі у вигляді графу станів, у якого вершини відповідають певним станам системи, а дуги – функціям і переходам між цими станами. Можна легко зауважити, що аналіз та синтез систем в класі станів проводиться тоді, коли між станами можливі альтернативні шляхи переходу, тобто ця задача зводиться д аналізу та синтезу структури зв’язків між станами – топології. Спочатку цей підхід використовували в процесі проектування цифрових актоматів, синтезу алгоритмів та програм роботи комп’ютерів, а згодом для розвитку задач синтезу електричних кіл, електричних схем, складих систем керування, а тепер ця задача стає актуальною для синтезу технологічних ліній.

Розділ 1. Способи задання топологій

Графічні способи

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

Граф G=(B,E) – це сукупність двох множин (об’єктів): В={b_>1>,b_>2>,…,b_>n>} – скінченна непуста множина вершин (вузлів); D={d_>1>,d_>2>,…,d_>m>} – скінчена множина пар вершин, що з’єднанні між собою і утворюють ребро (дугу) графа G.

Якщо пара вершин упорядковані, то граф називається орієнтованим (орграфом), в іншому випадку – неорієнтованим. Ребра (дуги) із множини D в орієнтованому графі зазвичай мають стрілку.

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

Наприклад, для задання топології поліграфічної системи оперативного викуску однокольорових брошур вказана така множина вершин В= {b_>1>– комп’ютер, b_>2> – дублікатор, b_>3> – колатор, b_>4> – степлер-фальцовщик, b_>5> – одноножовий різак } і така множина пар вершин D={d_>1>=(b_>1>b_>2>); d_>2>=(b_>2> b_>3>); d_>3>=(b_>3> b_>3>); d_>4>=(b_>3> b_>4>); d_>5>; d_>6>=(b_>5> b_>5>)}. В цій системі, орієнтований граф топології якої наведено на рис. 1.1., з’єднання, що відповідає парі вершин), забезпечує передачу інформації про поточну звертальну шпальту видання на дублікатор, який забезпечує друкування цієї шпальти заданим накладом. З’єднання (b_>2> b_>3>) відповідає передачі накладу задрукованої шпальти на колатор. В колаторі проводиться накопичення всіх шпальт брошури. Як тільки буде прийнято від дублікатора наклад останньої шпальти даного видання, тоді він приступить до формування зошитів брошури, що будуть складатися із певної послідовності задрукованих шпальт. Власне цей процес відображений парою вершин (b_>3> b_>3>). Зформований зошит брошури подається в степлер-фальцовщик за допомогою зв’язку, який описується парою вершин (b_>3> b_>4>). Після скріплення та фальцування шпальт брошура через зв’язок, який описується парою вершин (b_>4> b_>5>), подається на одноножовий різак. Парою вершин (b_>5> b_>5>) відображається послідовна обрізка трьох боків брошури. Цілком очевидно, що пара вершин є впорядкованими, тобто (b_>1> b_>2>)≠( b_>2> b_>1>).

Приклад орієнтованого графа більш складної топології системи показаний на рис.1.2., в якому вершини позначені просто числами.

Якщо в топології системи пари елементів, що з’єднані між собою, не впорядковані, тобто між парами встановлений зв’язок від одного елемента до іншого і навпаки (наприклад, з’єднання в комп’ютерно-видавничій системі комп’ютер-модем, модем-комп’ютер тощо), то така топологія задається неорієнтованим графом. Приклад такого графа є на рис.1.3. Дуга в неорієнтованому графі не має стрілок або має відразу дві стрілки на кінцях.

Топологія системи може мати деяку множину елементів, між якими встановлені певні відношення, та іншу множину елементів, між якими не встановлено відношень. Наприклад, для задання топології в комп’ютерно-видавничій системі (КВС) вказана така множина вершин В={b_>1>–_>>1-й комп’ютер, b_>2>– 2-й комп’ютер, b_>3>– сканер, b_>4>– модем, b_>4>– лазерна друкарка} і така множина пар вершин D= {d_>1>=(b_>1>,b_>2>); d_>2>=(b_>2>,b_>1>); d_>3>=(b_>2>,b_>4>); d_>4>=(b_>3>,b_>1>); d_>5>=(b_>1>,b_>4>); d_>6>=(b_>2>,b_>5>); d_>7>=(b_>4>,b_>1>); d_>8>=(b_>4>,b_>2>)}, для якої (b_>1>,b_>2>)= (b_>2>,b_>1>), (b_>1>,b_>4>)= (b_>4>,b_>1>), (b_>2>,b_>4>)= (b_>4>,b_>2>), але (b_>3>,b_>1>)≠ (b_>1>,b_>3>) і (b_>2>,b_>3>) ≠ (b_>5>,b_>2>). Ця топологія буде описуватися змішаним графом, який наведено на рис.1.4.

Основною перевагою графічного способу завдання топологій систем з одного боку це висока наочність безпосереднього відображення структури зв’язків між елементами системи, а з другого – достатньо розроблені в теорії графів методи їх опрацювання. Проте, графічний спосіб має й певні недоліки. По-перше, це труднощі автоматичного опрацювання графів в комп’ютерах, що пов’язані з попереднім розпізнаванням графічних образів та потреба великих обсягів пам’яті для зберігання графів. По-друге, це труднощі відображення топологій систем з великою кількістю (понад 30) елементів і як наслідок – втрата наочності. По-третє, одна і та ж топологія системи може бути задана великою кількістю еквівалентних графів із різним геометричним зображенням. Так, наприклад, топологія системи, що відображена на рис.1.1., може мати інше еквівалентне (гомоморфне) зображення, що наведене на рис.1.5., і таке не відразу може бути сприйняте як відображення однакової топології.

Власне тому графічний спосіб задання, як правило, використовується для первинного опису топологій з невеликою кількістю елементів перед введенням топологій систем в комп’ютер, а також для перевірки (верифікації) розроблених методів опрацювання при інших способах задання.

Щодо мереж Петрі, то вони застосовуються переважно для опису та моделювання систем з недетермінованою поведінкою, елемиенти яких функціонують незалежно і взаємодіють час від часу. За допомогою мереж Петрі описують як стани системи, так і дії її складових елементів. З цих міркувань застосовувати мережі Петрі для задання топологій систем недоцільно.

1.2 Матричні способи

До матричних способів відносяться: матриці (суміжності, інциденції, цикломатичні), n-мірні таблиці (масиви), n-мірні куби.

Матриця суміжності А – це квадратна матриця, що задає топологію системи і має наступний вигляд:

Матрицями суміжності можна задавати топології, що описуються як орієнтованими графами, так і неорієнтованими графами.

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

Матриця суміжності з’єднань за входами – це така матриця суміжності, в якій рядки позначені елементами (номерами елементів) системи, входи яких з’єднані з виходами тих елементів системи, якими позначені стовпці матриці.

Тобто, якщо в цій матриці А_>ij>=1, то це означає, що вхід і-го елеметна системи з’єднаний з виходом j-го елемента.

Так, наприклад, для топології, що на рис.1.1., матриця суміжності з’єднань за входами А_>І> буде такою:

Матриця суміжності з’єднань за виходами – це така матриця суміжності, в якій рядки позначені елементами системи, якими розначені стовпчі матриці.

Тобто, якщо в такій матриці a_>ij>_>>=1, то це означає, що вихід i-го елемента системи з’єднаний з входом j-го елемента.

Для тієї ж топології, що на рис.1.1, матриця суміжності з’єднань за виходами А_>о>буде такою:

Для задання топології систем, що описується неорієнтованим графом, застосовують тільки одну матрицю суміжності А, яка є об’єднанням матриць А_>І>та А_>о>

А= А_>І>_>>А_>О.>

Так, наприклад, для топології, що на рис. 1.3, матриця суміжності А буде такою:

Для задання топологій систем іноді застосовують матриці інциденцій

Якщо топологія задається орієнтованим графом G=(B,E), де B={b_>1>,b_>2>,…b_>n>}, D={d_>1>,d_>2>,…d_>m>}, то матриця інциденцій для дуг S матиме такий вигляд:

Наприклад, для топології, що на рис. 1.2., матриця інциденції для дуг S буде такою:

Якщо топологія задається неорієнтованим графом G=(B,E), де B={b_>1>,b_>2>,…b_>n>}, D={d_>1>,d_>2>,…d_>m>}, то матриця інциденцій для ребер 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 – номер стовпця матриці суміжності, р – кількість нульових рядків матриці суміжності.

0100090000032a0200000200a20100000000a201000026060f003a03574d464301000000000001002dd50000000001000000180300000000000018030000010000006c0000000000000000000000350000006f0000000000000000000000313400007d21000020454d46000001001803000012000000020000000000000000000000000000007f120000771a0000c80000001f010000000000000000000000000000000f030058600400160000000c000000180000000a0000001000000000000000000000000900000010000000530c0000e8070000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c0069006200720069000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000024003098240010000000949b240014992400e4503566949b24008c98240010000000fc992400789b24008a4f3566949b24008c9824002000000080e03c688c982400949b240020000000ffffffffec238701fbe03c68ffffffffffff0180ffff0180ff020180ffffffff0000010000080000000800007cf43f0501000000000000005802000025000000552e9001cc08020f0502020204030204ff0200e1ffac004009000000000000009f01000000000000430061006c0069006200720000000000430065006e007400750072007900200047006f00c0982400d53236682000000001000000fc982400fc982400007634682000000024992400ec2387016476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000006f00000001000000e7298740a48e87400000000057000000010000004c000000040000000000000000000000540c0000e9070000500000002000995d3600000046000000280000001c0000004744494302000000ffffffffffffffff540c0000ea070000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c02f3007a01040000002e0118001c000000fb020200010000000000bc02000000cc0102022253797374656d003f00003f3f3f3f3f3f3f3f3f3f0800000001003f3f3f3f3f00040000002d010000040000002d01000004000000020101001c000000fb02f5ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0a00000001000400000000007a01f30020000600040000002d010000040000002d010000030000000000

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

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

Висновок

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

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

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

До аналітичних способів задання топологій систем можна віднести логічні схеми алгоритмів (ЛСА).

Додаток 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)

z=0;

break

end

j=i;

if d(i,j)==1

z=1;

break

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

else

if ~(sum(c)==1)

if j==n

if p==0

z=0;

end

toc

Додаток 2

Текст програми виявлення паралельної топології

tic

n=5;

A(1:n,1:n)=0;

A(1,1)=1;

c=0;

for i=1:n

for j=1:n

c=c+A(i,j);

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

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

top

if z==1

disp (‘topologia derevo’)

else

disp (‘topologia ne derevo’)

end

Список викоhистаної літератури

Дунець Р.Б. Аналіз та синтез топологій комп’ютерних видавничо-поліграфічних систем: монографія. – Львів: НВФ “Українські технології”, 2003.

Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. – Спб Питер, 2004.

Берж К. Теория графов и ее применение. – М.: Иностранная литература, 1962.- 320 с.

Оре О. Теория графов. – М.: Наука, 1980.-336 с.

Дунець Р., Басюк Т. Структура програми перетворення графів в ярусно- паралельну форму//Комп’ютерні технології друкарства. – 2002. - №7. – С.97-102.

Капитонова Ю.В., Летичевский А.А. Математическая теория вычислительных систем. – М.: Наука, 1988. – 295 с.

Шатихин Л.Г. Структурные матрицы и их применение для исследования систем. – М.: Машиностроение, 1991. – 253 с.