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

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