Пристрій для пошуку максимальних незалежних множин графа

Пристрій для пошуку максимальних незалежних множин графа, що містить генератор тактових імпульсів, лічильник, дешифратор, матрицю осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера, групу елементів АБО за кількістю стовпців матриці осередків формування топології досліджуваного графа, реєстраційний блок, причому вихід генератора тактових імпульсів підключений до входу лічильника, вихід лічильника підключений до входу дешифратора, виходи елементів І осередків одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного елемента АБО, вхід генератора тактових імпульсів є входом запуску пристрою, нульові входи тригерів всіх осередків матриці формування топології досліджуваного графа об'єднані та підключені до входу скидання пристрою в початковий стан, одиничні входи тригерів всіх осередків матриці формування топології досліджуваного графа є установочними входами пристрою, який відрізняється тим, що додатково містить другий лічильник, дворозрядний лічильник, елемент НІ, два елементи АБО, два елементи І, групу елементів І за кількістю стовпців матриці осередків формування топології досліджуваного графа, елемент АБО-НІ, реєстраційний блок виконано у вигляді реєстраційного масиву осередків незалежної множини за кількістю стовпців матриці формування топології досліджуваного графа, ко 2 (19) 1 3 88801 4 скидання другого лічильника підключений до входу скидання пристрою в початковий стан, перший вхід другого елемента АБО підключений до входу скидання пристрою в початковий стан, другий вхід другого елемента АБО є входом скидання початкової множини. Винахід відноситься до обчислювальної техніки та може бути застосована в інженерії, економіці, комп'ютерному зорі, підчас планування радіомереж, складання маршрутів, проектування великих інтегральних схем. Відомий пристрій для розв'язання задач на графах (авт.св. СРСР №1684795, МПК G06F15/20, опубл. 15.10.91р., бюл. №38), що містить блок синхронізації, до складу якого входить генератор тактових імпульсів, блок визначення кінцевих вершин ребер, наддіагональну матрицю формування топології досліджуваного графа, комутатор, блок пам'яті, суматор, причому вхід запуску пристрою є входом блока синхронізації, перший ті другий виходи якого підключені до керівного входу комутатора та входу признаку запису блока пам'яті відповідно, третій вихід блоку синхронізації підключений до тактового входу суматора, вихід значення елемента матриці формування топології досліджуваного графа підключений до входу признака існування відповідного ребра в графі блоку визначення кінцевих вершин ребер, виходи блоку визначення кінцевих вершин ребер підключені до відповідних входів комутатора, виходи комутатора підключені до відповідних входів блоку пам'яті, виходи блоку пам'яті підключені до відповідних входів суматора, вихід якого підключений до інформаційного входу блока пам'яті. Використання пристрою для розв'язання задач на графах не дозволяє вести пошук максимальних незалежних множин графа через те, що результатом його роботи є інформація про кількість шляхів між кожною парою вершин графа, пошук будь-яких підмножин графа при цьому не ведеться. Найбільш близьким аналогом винаходу, що заявляється, є пристрій для дослідження зв'язності графа (авт.св. СРСР №1594558, МПК G06F15/20, опубл. 23.09.90р., бюл. №35), що містить генератор тактових імпульсів, лічильник, дешифратор, матрицю осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та двох елементів І, перший вхід першого елемента І підключений до виходу тригера, а вихід першого елемента І підключений до першого входу другого елемента І, першу та другу групу елементів АБО за кількістю рядків та стовпців матриці формування топології досліджуваного графа відповідно, групу елементів НІ, додаткову групу тригерів, реєстраційний блок, виконаний у вигляді реєстраційної матриці осередків, кожен осередок якої складається з тригера та елемента І, вихід якого підключений до одиничного входу тригера, причому вхід запуску генератора тактових імпульсів є входом запуску пристрою, вихід генератора тактових імпульсів підключений до входу лічильника і нульових входів тригерів додаткової групи, вихід лічильника підключений до входу дешифратора, виходи дешифратора підключені до перших входів відповідних елементів АБО першої групи та першим входам елементів І осередків відповідних рядків реєстраційної матриці, виходи елементів АБО першої групи підключені до других входів перших елементів І осередків відповідного рядка матриці формування топології досліджуваного графа, входи елементів АБО другої групи підключені до виходів других елементів І осередків відповідного стовпця матриці формування топології досліджуваного графа, виходи елементів АБО другої групи підключені до одиничних входів тригерів додаткової групи, виходи тригерів додаткової групи підключені до входів елементів НЕ, входів елементів АБО першої групи та другим входам елементів І осередків відповідного стовпця реєстраційної матриці, виходи елементів НЕ підключені до других входів других елементів І осередків відповідного стовпця матриці формування топології досліджуваного графа, нульові входи тригерів осередків реєстраційної матриці та матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан, одиничні входи тригерів матриці формування топології досліджуваного графа є установочними входами пристрою, вихід дешифратора, що відповідає найбільшому значенню лічильника підключений до входу зупинки генератора тактових імпульсів. Для початку роботи з пристроєм подається сигнал на вхід скинення пристрою в початковий стан. Після цього в пристрій за допомогою установочних входів завантажується інформація про топологію орієнтованого графа без петель. При цьому тригер ij встановлюється в одиничний стан, якщо є ребро з вершини і в вершину j. Потім подається сигнал на вхід запуску пристрою, і пристрій починає працювати за тактами. В кожному такті визначаються номера вершин, що зв'язані з вершиною, номер якої співпадає з номером такту. На початку кожного такту тригери додаткової групи переводяться в нульовий стан, а на виходах елементів АБО другої групи формуються сигнали, що дорівнюють вихідним сигналам тригерів осередків рядка матриці формування топології досліджуваного графа, номер якого співпадає з номером такту. Рядок матриці формування топології досліджуваного графа запам'ятовується тригерами додаткової групи, і елементи НЕ блокують виходи матриці формування топології графа, на яких було сформовано одиничній сигнал, що не дозволяє до кінця такту ще раз змінити значення тригерів, встановлених в одиничний стан. Одиничні сигнали від тригерів додаткової групи потрапляють входи елементів АБО першої групи, що дозволяє тригерам інших рядків матриці формування топології, що знаходяться в одиничному стані, встановити одиничні значення в інших тригерах додаткової групи, так як це описано раніше. До того ж тригер додаткової групи встановлюється в одиничний стан тільки якщо є шлях із вершини графа з номером, що 5 співпадає з номером такту, в вершину графа, номер якої співпадає з номером тригеру. Одиничні сигнали від тригерів додаткової групи потрапляють на входи елементів і реєстраційної матриці. Реєстраційна матриця також керується дешифратором, тому на кожному такті виходи тригерів додаткової групи запам'ятовуються одним рядком реєстраційної матриці. Після виконання n тактів, де n - кількість вершин графа, пристрій зупиняється, а стан тригера ij реєстраційної матриці означає наявність, якщо тригер у одиничному стані, або відсутність, якщо тригер у нульовому стані, шляху із вершини і графа в вершину j. Ознаками найбільш близького аналогу, що збігаються з істотними ознаками винаходу, що заявляється, є: - генератор тактових імпульсів, вихід якого підключений до входу лічильника; - лічильник, вихід якого підключений до входу дешифратора; - дешифратор; - матриця осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера; - група елементів АБО за кількістю стовпців матриці осередків формування топології досліджуваного графа; - реєстраційний блок; - виходи елементів І осередків одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного стовпцю елемента АБО; - нульові входи тригерів всіх осередків матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан. Використання найбільш близького аналогу не дозволяє вести пошук найбільших незалежних множин графа через те, що результатом його роботи є інформація про наявність шляхів між кожною парою вершин графа, пошук будь-яких підмножин графа при цьому не ведеться. В основу винаходу поставлено задачу вдосконалення пристрою, в якому за рахунок уведення нових конструктивних ознак забезпечується багаторазовий пошук максимальних незалежних множин неорієнтованого графа виходячи з початкової множини і отримання кількості вершин графа в знайденій множині. Поставлена задача вирішується тим, що пристрій, який містить генератор тактових імпульсів, лічильник, дешифратор, матрицю осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера, групу елементів АБО за кількістю стовпців матриці осередків формування топології досліджуваного графа, реєстраційний блок, причому вихід генератора тактових імпульсів підключений до входу лічильника, вихід лічильника підключений до входу дешифратора, виходи елементів І осередків одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного елемента АБО, вхід генератора тактових ім 88801 6 пульсів є входом запуску пристрою, нульові входи тригерів всіх осередків матриці формування топології досліджуваного графа об'єднані та підключені до входу скидання пристрою в початковий стан, одиничні входи тригерів всіх осередків матриці формування топології досліджуваного графа є установочними входами пристрою, згідно винаходу додатково містить другий лічильник, дворозрядний лічильник, елемент НІ, елемент АБО, два елементи І, групу елементів І за кількістю стовпців матриці осередків формування топології досліджуваного графа, елемент АБО-НІ, реєстраційний блок виконано у вигляді реєстраційного масиву осередків незалежної множини за кількістю стовпців матриці формування топології досліджуваного графа, кожен осередок якого складається з елементу НІ, двох елементів І, двох елементів АБО та тригера, нульовий та одичний входи якого підключені до виходів першого й другого елементів АБО відповідно, вихід елементу НІ підключений до першого входу першого елемента І, а виходи елементів І підключені до других входів відповідних елементів АБО, причому виходи групи елементів АБО підключені до перших входів відповідних елементів групи елементів І, виході елементів І підключені до входів елемента АБО-НІ, вихід елемента АБО-НІ підключений до входів елементів НІ всіх осередків реєстраційного масиву незалежної множини, перших входів других елементів І всіх осередків реєстраційного масиву незалежної множини та першого входу другого елемента І, виходи тригерів осередків реєстраційного масиву незалежної множини підключені до других входів відповідних елементів групи елементів І, кожен вихід дешифратора підключений до других входів елементів І всіх осередків відповідного рядка матриці формування топології досліджуваного графа та до других входів першого і другого елементів І відповідного осередку реєстраційного масиву незалежної множини, вихід дешифратора, що відповідає найбільшому значенню лічильника, також підключений до першого входу першого елемента І, вихід першого елемента І підключений до першого входу першого елемента АБО, вихід першого елемента АБО підключений до входу дворозрядного лічильника, вихід старшого розряду дворозрядного лічильника підключений до входу зупинки генератора тактових імпульсів, вихід молодшого розряду дворозрядного лічильника підключений до другого входу другого елемента І, вихід генератора також підключений до входу елемента НІ, вихід елемента НІ підключений до другого входу першого елемента І та до третього входу другого елемента І, вихід другого елемента І підключений до входу другого лічильника, вихід другого елемента АБО підключений до перших входів перших елементів АБО всіх осередків реєстраційного масиву незалежної множини та до входів скидання другого лічильника та дворозрядного лічильника, другий вхід першого елемента АБО є входом вибору режиму праці пристою, перші входи других елементів АБО осередків реєстраційного масиву незалежної множини є входами установки початкової множини, вхід скидання другого лічильника підключений до входу скидання пристрою в початковий стан, 7 перший вхід другого елемента АБО підключений до входу скидання пристрою в початковий стан, другий вхід другого елемента АБО є входом скидання початкової множини. Ці елементи складаюсь суть винаходу, тому що необхідно забезпечити можливість завантаження початкової множини в пристрій, можливість роботи пристрою у режимі, якщо реєстраційний масив описує незалежну немаксимальну множину, у режимі, якщо реєстраційний масив описує не незалежну множину, і можливість підрахунку кількості вершин графа у знайденому рішенні. Суть винаходу пояснюється рисунком, де на Фіг.1 наведено функціональну схему пристрою для пошуку максимальних незалежних множин графа. Пристрій для пошуку максимальних незалежних множин графа містить генератор 1 тактових імпульсів, лічильник 2, дешифратор 3, дворозрядний лічильник 4, елемента НІ 5, елемент АБО 6, елемент І 7, матрицю 8 осередків формування топології досліджуваного графа, кожний осередок якої складається з тригеру 9ij та елементу І 10ij (де i,j=1, 2,...,n), групу елементів АБО НІ, елемент АБО 12, реєстраційний масив 13 осередків незалежної множини, кожен осередок якого складається з елементу НІ 14і, елементів І 15і та 16і, елементів АБО 17і та 18і, тригеру 19і, а також елементи І 20і20n, елемент АБО-НІ 21, елемент І 22, лічильник 23, вхід 24 скидання пристрою в початковий стан, вхід 25 запуску пристрою, вхід 26 переведення пристрою в другий режим, входи 2711-27nn установки топології досліджуваного графа, вхід 28 скидання початкової множини та входи 291-29n установки початкової множини. Пристрій для розв'язання задачі про максимальну незалежну множину графа працює наступним чином. Необхідно знайти таку підмножину вершин заданого неорієнтованого графа без петель, щоб будь-які дві з них не були суміжними, і додавання будь-якої іншої вершини до цієї підмножини призводило б до порушення попередньої умови; також знайти міцність знайденої множини. В залежності від режиму праці пристрою треба вести пошук спочатку будь-якої незалежної множини, потім додати вершини, щоб створити максимальну множину, або виконати тільки останню дію. Спочатку імпульс з входу 24 перемикає тригери 911-9nn, та лічильники 2, 4 в нульовий стан, також цей імпульс подається на вхід елемента АБО 12, на виході якого формується одиничний сигнал, який потрапляє на входи елементів АБО 171-17n, що призводить по подання одиничного сигналу на нульовий вхід тригерів 19і-19n та перемикання їх в нульовий стан, також одиничний сигнал з виходу елемента АБО 12 перемикає в нульовий стан лічильник 22. Це підготовлює пристрій до роботи. Потім в пристрій за допомогою установочних входів 2711-27nn завантажується інформація про топологію неорієнтованого графа без петель - матриця суміжності. При цьому тригери 9ij та 9ji перемикаються до одиничного стану, якщо в графі є ребро між вершинами і та j. Після цього, якщо в наявності є початкова множина, отримана будь-яким способом, її можна завантажити за допомогою входів 29і-29n. При 88801 8 цьому, якщо вершина і графа належить початковій множині, тригер 19, повинен бути установленим в одиничний стан. Подання одиничного сигналу на вхід 29і призводить до появи одиничного сигналу на виході елемента АБО 18i, який потрапляє на одиничний вхід тригеру 19i, що перемикає тригер 19і в одиничний стан. Якщо завантажена початкова множина є незалежною не максимальною множиною, подається сигнал на вхід 26 для переведення пристрою в другий режим праці. Коли всю необхідну інформацію завантажено, подається сигнал на вхід 25, і пристрій починає працювати за тактами. Впродовж кожного такту перевіряється можливість присутності однієї вершини в максимальній незалежній множині. Сигнал від генератора 1 тактових імпульсів через лічильник 2 потрапляє на вхід дешифратора. На виході дешифратора з номером, що відповідає значенню лічильника 2, встановлюється одиничний сигнал, на інших виходах - нульові сигнали. На такті і (де і=1, 2,...,n) на виході і дешифратора 3 встановлюється одиничний сигнал. Цей сигнал потрапляє на другі входи елементів І 10i110in, на виходах яких формуються сигнали, що дорівнюють станам відповідних тригерів 9i1-9in. На другі входи інших елементів І 10j1-10jn (де j=1, 2,...,n; j≠i) потрапляють нульові сигнали з інших виходів дешифратора 3, тому на виходах цих елементів з'являється нульовий сигнал. На входи кожного з елементів АБО 111-11n подаються вихідні сигнали всіх елементів І 101k-10nk (де k=1, 2,...,n), причому вихідний сигнал елементу І 10ik дорівнює стану тригера 9іk, вихідні сигнали інших елементів І стовпця к матриці 8 осередків формування топології досліджуваного графа нульові, через це на виходах елементів АБО 111-11n формуються сигнали, що дорівнюють вихідним сигналам тригерів 9i1-9in. Таким чином на виходах елементів АБО 11і11n з'являються сигнали, що відповідають рядку матриці 6 осередків формування топології досліджуваного графа, тобто рядку матриці суміжності графа. На входи елементів І 20і-20n потрапляють сигнали з виходів елементів АБО 11і-11n та виходів тригерів 19і-19n реєстраційного масиву 13 осередків незалежної множини. На виході елемента І 20k з'являється одиничний сигнал, якщо вершина k належить до поточного наближення шуканої множини, тобто тригер 19k знаходиться в одиничному стані, та в графі є ребро між вершинами k та і, тобто тригер 9ik знаходиться в одиничному стані на виході елемента АБО 11k одиничний сигнал, або нульовий сигнал, якщо вершина k не належить до поточного наближення шуканої множини, тобто тригер 19k знаходиться в нульовому стані, або в графі немає ребра між вершинами k та і, тобто тригер 9ik знаходиться в нульовому стані - на виході елемента АБО 11k нульовий сигнал. Виходи всіх елементів I 20і-20n подаються на входи елементу АБО-HI 21, на виході якого формується нульовий сигнал, якщо вершина і суміжна хоча б з однією вершиною, що належить до поточного наближення до шуканої множини, і одиничний сигнал, якщо вершина і не суміжна ні з одною ве 9 ршиною, що належить до поточного наближення шуканої множини. Вихідний сигнал елемента АБО-HI 21 потрапляє на входи кожного з елементів HI 14і-14n, які інвертують сигнал та відсилають його до перших входів елементів І 15і-15n, та перши входи кожного з елементів І 16і-16n. Сигнали від дешифратора 3 потрапляють на другі входи елементів І 15і-15n та 16і-16n. Тому, на виходах елементів I 15i-15n та 16і16n, крім елементів І 15i та 16i формуються нульові сигнали, а вихідні сигнали елементів I 15i та 16i формуються наступним чином: якщо вихідний сигнал елементу АБО-HI 21 нульовий, на виході елемента І 15і з'являється одиничний сигнал, а на виході елемента І 16і з'являється нульовий сигнал, та якщо вихідний сигнал елементу АБО-HI 21 одиничний, на виході елемента І 15і з'являється нульовий сигнал, а на виході елемента І 16і з'являється одиничний сигнал. Виходи елементів I 15і-15n потрапляють на входи елементів АБО 17і-17n, інші входи елементів АБО 17і-17n залишаються нульовими впродовж роботи пристрою, тому на сигнал виходах елементів АБО 17і-17n дорівнюватиме вихідному сигналу елементів І 15і-15n. Виходи елементів І 16і-16n потрапляють на входи елементів АБО 18і-18n, інші входи елементів АБО 18і-18n залишаються нульовими впродовж роботи пристрою, тому сигнал на виходах елементів АБО 18і-18n дорівнюватиме вихідному сигналу елементів I 16і-16n. Виходи елементів АБО 17і-17n потрапляють на нульові входи тригерів 19і-19n, а АБО 18і-18n потрапляють на одиничні входи тригерів 19і-19n, тому тригер 19і перемикається в одиничний стан, якщо вершина і графа не суміжна з жодною вершиною, що належить до поточного наближення до шуканої множини, та в нульовий стан, якщо вершина і графа суміжна хоча б з однією вершиною, що належить до поточного наближення до шуканої множини. Стани інших тригерів 19і-19n, не змінюються. На такті n, крім описаних дій, одиничний сигнал з виходу n дешифратора 3 попаде на вхід елемента І 7. Крім того, по закінченні такту, нульовий сигнал генератора 3 потрапить на вхід елементу HI 5. На виході елемента НІ 5 з'явиться одиничний сигнал, який потрапить на другий вхід елемента 17. Це призведе до появи одиничного сигналу на виході елемента І 7 і, як наслідок, елемента АБО 6, що збільшить значення дворозряд 88801 10 ного лічильника 4 на одиницю. Впродовж інших тактів, вихід n дешифратора 3 залишається нульовим, тому сигнал на виході елемента І 7 залишається нульовим. Якщо пристрій не переводився до другого режиму праці, на виході дворозрядного лічильника сформується код «01», інакше код «10». В першому випадку, на наступному такті значення лічильника 2 буде скинуто в 0, та цикл з n тактів повториться. У другому випадку, одиничний сигнал з виходу старшого розряду дворозрядного лічильника 4 потрапить на вхід зупинки генератора тактових імпульсів, та пристрій зупинить свою роботу. Якщо початкова множина, яку було завантажено в реєстраційний масив 13 є незалежною множиною, реєстраційний масив 13 описує на даний момент максимальну незалежну множину графа, що представлений в матриці 8 формування топології досліджуваного графа. Інакше реєстраційний масив 13 описує немаксимальну незалежну множину, і повторне виконання n тактів призведе до того, що реєстраційний масив 13 описуватиме максимальну незалежну множину графа. Крім того, на такті 2n одиничний сигнал з виходу n дешифратора 3 попаде на вхід елемента 17. Крім того, по закінченні такту, нульовий сигнал генератора 3 потрапить на вхід елементу HI 5. На виході елемента HI 5 з'явиться одиничний сигнал, який потрапить на другий вхід елемента І 7. Це призведе до появи одиничного сигналу на виході елемента І 7 і, як наслідок, елемента АБО 6, що збільшить значення дворозрядного лічильника 4 на одиницю. На виході дворозрядного лічильника 4 сформується код «10». Одиничний сигнал з виходу старшого розряду дворозрядного лічильника 4 потрапить на вхід зупинки генератора тактових імпульсів, та пристрій зупинить свою роботу. На цей момент реєстраційний масив 13 гарантовано описує максимальну незалежну множину графа. При необхідності продовження пошуку інших максимальних незалежних вершин необхідно подати одиничний сигнал на вхід 28 скидання початкової множини, що призведе до формування одиничного сигналу на виході елемента АБО 12 та скидання тригерів 19і-19n і лічильника 23 в нульовий стан, після цього завантажити до реєстраційного масиву іншу початкову множину і подати одиничний сигнал на вхід 25 запуску пристрою, щоб повторити процес пошуку рішення. 11 Комп’ютерна верстка О. Рябко 88801 Підписне 12 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601