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

Пристрій для розв'язання задачі про максимальну незалежну множину графа, що містить генератор тактових імпульсів, лічильник, дешифратор, матрицю комірок формування топології досліджуваного графа, кожна комірка якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера, групу елементів АБО за кількістю стовпців матриці комірок формування топології досліджуваного графа, реєстраційний блок, причому вихід генератора тактових імпульсів підключений до входу лічильника, вихід лічильника підключений до входу дешифратора, виходи елементів І комірок одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного стовпцю елемента АБО, вхід генератора тактових імпульсів є входом запуску пристрою, нульові входи тригерів всіх комірок матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан, одиничні входи тригерів всіх комірок матриці формування C2 2 UA 1 3 82251 формування топології досліджуваного графа, комутатор, блок пам'яті, суматор, причому вхід запуску пристрою є входом блока синхронізації, перший ті другий ви ходи якого підключені до керівного входу комутатора та входу признаку запису блока пам'яті відповідно, третій вихід блоку синхронізації підключений до тактового входу суматора, вихід значення елемента матриці формування топології досліджуваного графа підключений до входу признака існування відповідного ребра в графі блоку визначення кінцевих вершин ребер, виходи блоку визначення кінцевих вершин ребер підключені до відповідних входів комутатора, виходи комутатора підключені до відповідних входів блоку пам'яті, виходи блоку пам'яті підключені до відповідних входів суматора, вихід якого підключений до інформаційного входу блока пам'яті. Використання пристрою для розв'язання задач на графах не дозволяє знайти максимальну незалежну множину графа через те, що результатом його роботи є інформація про кількість шляхів між кожною парою вершин графа, пошук будь-яких підмножин графа при цьому не ведеться. Найбільш близьким аналогом винаходу, що заявляється, є пристрій для дослідження зв'язності графа [авт.св. СРСР №1594558, МПК G06F15/20, опубл. 23.09.90р., бюл. №35], що містить генератор тактових шпульсів, лічильник, дешифратор, матрицю осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та двох елементів І, перший вхід першого елемента І підключений до виходу тригера, а вихід першого елемента І підключений до першого входу другого елемента І, першу та др угу груп у елементів АБО за кількістю рядків та стовпців матриці формування топології досліджуваного графа відповідно, груп у елементів НЕ, додаткову гр упу тригерів, реєстраційний блок, виконаний у вигляді реєстраційної матриці осередків, кожен осередок якої складається з тригера та елемента І, вихід якого підключений до одиничного входу тригера, причому вхід запуску генератора тактових імпульсів є входом запуску пристрою, вихід генератора тактових імпульсів підключений до входу лічильника і нульових входів тригерів додаткової групи, вихід лічильника підключений до входу де шифратора, ви ходи дешифратора підключені до перших входів відповідних елементів АБО першої групи та першим входам елементів І осередків відповідних рядків реєстраційної матриці, виходи елементів АБО першої групи підключені до других входів перших елементів І осередків відповідного рядка матриці формування топології досліджуваного графа, входи елементів АБО другої гр упи підключені до виходів других елементів І осередків відповідного стовпця матриці формування топології досліджуваного графа, виходи елементів АБО др угої групи підключені до одиничних входів тригерів додаткової групи, ви ходи тригерів додаткової групи підключені до входів елементів НЕ, входів елементів АБО першої групи та др угим входам елементів І осередків відповідного стовпця 4 реєстраційної матриці, виходи елементів НЕ підключені до других входів других елементів І осередків відповідного стовпця матриці формування топології досліджуваного графа, нульові входи тригерів осередків реєстраційної матриці та матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан, одиничні входи тригерів матриці формування топології досліджуваного графа є установочними входами пристрою, вихід дешифратора, що відповідає найбільшому значенню лічильника підключений до входу зупинки генератора тактових імпульсів. Для початку роботи з пристроєм подається сигнал на вхід скинення пристрою в початковий стан. Після цього в пристрій за допомогою установочних входів завантажується інформація про топологію орієнтованого графа без петель. При цьому тригер ij встановлюється в одиничний стан, якщо є ребро з вершини і в вершину j. Потім подається сигнал на вхід запуску пристрою, і пристрій починає працювати за тактами. В кожному такті визначаються номера вершин, що зв'язані з вершиною, номер якої співпадає з номером такту. На початку кожного такту тригери додаткової групи переводяться в нульовий стан, а на виходах елементів АБО другої групи формуються сигнали, що дорівнюють вихідним сигналам тригерів осередків рядка матриці формування топології досліджуваного графа, номер якого співпадає з номером такту. Рядок матриці формування топології досліджуваного графа запам'ятовується тригерами додаткової групи. Після цього, елементи НЕ блокують виходи матриці формування топології досліджуваного графа, на яких було сформовано одиничній сигнал, що не дозволяє до кінця такту ще раз змінити значення тригерів, встановлених в одиничний стан. Одиничні сигнали від тригерів додаткової групи потрапляють входи елементів АБО першої групи, що дозволяє тригерам інших рядків матриці формування топології, що знаходяться в одиничному стані, встановити одиничні значення в інших тригерах додаткової групи, так як це описано раніше. До того ж тригер додаткової групи встановлюється в одиничний стан тільки якщо є шлях із вершини графа з номером, що співпадає з номером такту, в вершину графа, номер якої співпадає з номером тригеру. Одиничні сигнали від тригерів додаткової групи потрапляють на входи елементів і реєстраційної матриці. Реєстраційна матриця також керується дешифратором, тому на кожному такті виходи тригерів додаткової групи запам'ятовуються одним рядком реєстраційної матриці. Після виконання n тактів, де n - кількість вершин графа, пристрій зупиняється, а стан тригера ij реєстраційної матриці означає наявність, якщо тригер у одиничному стані, або відсутність, якщо тригер у нульовому стані, шляху із вершини і графа в вершину j. Ознаками найбільш близького аналогу, що збігаються з істотними ознаками винаходу, що заявляється, є: 5 82251 - генератор тактових імпульсів, вихід якого підключений до входу лічильника; - лічильник, вихід якого підключений до входу дешифратора; дешифратор; - матриця осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера; - група елементів АБО за кількістю стовпців матриці осередків формування топології досліджуваного графа; - реєстраційний блок; - виходи елементів І осередків одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного стовпцю елемента АБО; - нульові входи тригерів всіх осередків матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан. Використання найбільш близького аналогу не дозволяє знайти максимальну незалежну множину графа через те, що результатом його роботи є інформація про наявність шляхів між кожною парою вершин графа, пошук будь-яких підмножин графа при цьому не ведеться. В основу винаходу поставлено задачу вдосконалення пристрою, в якому за рахунок уведення нових конструктивних ознак забезпечується пошук максимальної незалежної множини вершин неорієнтованого графа. Поставлена задача вирішується тим, що пристрій, який містить генератор тактових імпульсів, лічильник, дешифратор, матрицю осередків формування топології досліджуваного графа, кожен осередок якої складається з тригера та елемента І, перший вхід якого підключений до виходу тригера, груп у елементів АБО за кількістю стовпців матриці осередків формування топології досліджуваного графа, реєстраційний блок, причому вихід генератора тактових імпульсів підключений до входу лічильника, вихід лічильника підключений до входу де шифратора, ви ходи елементів І осередків одного стовпця матриці формування топології досліджуваного графа підключені до входів відповідного стовпцю елемента АБО, вхід генератора тактових імпульсів є входом запуску пристрою, нульові входи тригерів всіх осередків матриці формування топології досліджуваного графа об'єднані та підключені до входу скинення пристрою в початковий стан, одиничні входи тригерів всіх осередківматриці формування топології досліджуваного графа є установочними входами пристрою, згідно винаходу додатково містить дворозрядний лічильник, груп у елементів І за кількістю стовпців матриці осередків формування топології досліджуваного графа, елемент АБО-НЕ, реєстраційний блок виконано у вигляді реєстраційного масиву осередків незалежної множини за кількістю стовпців матриці формування топології досліджуваного графа, кожен осередок якого складається з елементу НЕ, двох елементів І та тригера, нульовий та одичний входи якого підключені до виходів першого й 6 другого елементів І відповідно, а вихід елементу НЕ підключений до першого входу першого елемента І, причому виходи елементів АБО підключені до перших входів відповідних елементів І, ви ході елементів І підключені до входів елемента АБО-НЕ, ви хід елемента АБО-НЕ підключений до входів елементів НЕ всіх осередків реєстраційного масиву незалежної множини та перших входів других елементів І всіх осередків реєстраційного масиву незалежної множини, виходи тригерів осередків реєстраційного масиву незалежної множини підключені до други х входів відповідних елементів І, кожен вихід дешифратора підключений до други х входів елементів І всіх осередків відповідного рядка матриці формування топології досліджуваного графа та до др угих входів першого і другого елементів І відповідного осередку реєстраційного масиву незалежної множини, вихід дешифратора, що відповідає найбільшому значенню лічильника, також підключений до входу дворозрядного лічильника, вихід старшого розряду дворозрядного лічильника підключений до входу зупинки генератора тактових імпульсів. Ці елемента складаюсь суть винаходу, тому що необхідно забезпечити пошук незалежної множини і, згодом, максимальної незалежної множини. Суть винаходу пояснюється рисунком, де на Фіг.1 наведено функціональну схему пристрою для розв'язання задачі про максимальну незалежну множину графа. Пристрій для розв'язання задачі про максимальну незалежну множину графа містить генератор 1 тактових імпульсів, лічильник 2, дешифратор 3, дворозрядний лічильник 4, матрицю 5 осередків формування топології досліджуваного графа, кожний осередок якої складається з тригеру 6ij та елементу І 7ij (де ij=1, 2,..., n), гр упу елементів АБО 8i, реєстраційний блок 9, виконаний у вигляді реєстраційного масиву осередків незалежної множини, кожен осередок якого складається з елементу НЕ 10і, елементів І 11і та 12і, тригеру 13і, а також елементі I 14і-14n елемент АБО-НЕ 15, вхід 16 запуску пристрою, вхід 17 скинення пристрою в початковий стан і установочні входи 1811-18nn. Пристрій для розв'язання задачі про максимальну незалежну множину графа працює наступним чином. Необхідно знайти таку підмножину вершин заданого неорієнтованого графа без петель, щоб будь-які дві з них не були суміжними, і додавання будь-якої іншої вершини до цієї підмножини призводило б до порушення попередньої умови. Спочатку імпульс з входу 17 перемикає тригери 611-6nn в нульовий стан, що підготовлює пристрій до роботи. Потім в пристрій за допомогою установочних входів 211-2nn завантажується інформація про топологію неорієнтованого графа без петель - матриця суміжності. При цьому тригери 6ij та 6ji перемикаються до одиничного стану, якщо в графі є ребро між вершинами і та j. Стани тригерів 131-13n задають початкове наближення шуканої множини та є довільними, 7 82251 причому вважається, що якщо тригер 13m знаходиться в одиничному стані, вершина m (де m=1, 2,..., n) належить до початкового наближення шуканої множини, а якщо тригер 13m знаходиться в нульовому стані, вершина m не належить до початкового наближення шуканої множини. Коли інформацію про топологію графа завантажено, подається сигнал на вхід 16, і пристрій починає працювати за тактами. Впродовж кожного такту перевіряється можливість присутності однієї вершини в максимальній незалежній множині. Сигнал від генератора 1 тактових імпульсів через лічильник 2 потрапляє на вхід дешифратора. На виході дешифратора з номером, що відповідає значенню лічильника 2, встановлюється одиничний сигнал, на інших ви ходах - нульові сигнали. На такті і (де і=1, 2,..., n) на виході і дешифратора 3 встановлюється одиничний сигнал. Цей сигнал потрапляє на другі входи елементів І 7i1-7in, на виходах яких формуються сигнали, що дорівнюють станам відповідних тригерів 6i1-6in. На другі входи інших елементів І 7j1-7jn (де j=1, 2,..., n; j≠i) потрапляють нульові сигнали з інших ви ходів дешифратора 3, тому на виходах цих елементів з'являється нульовий сигнал. На входи кожного з елементів АБО 8 1-8n подаються вихідні сигнали всіх елементів 71k-7nk (де k=1, 2,..., n), причому вихідний сигнал елементу І 7ik дорівнює стану тригера 6ik, вихідні сигнали інших елементів І стовпця k матриці 5 осередків формування топології досліджуваного графа нульові, через це на виходах елементів АБО 81-8 n формуються сигнали, що дорівнюють вихідним сигналам тригерів 8i1-6in. Таким чином на виходах елементів АБО 81-8n з'являються сигнали, що відповідають рядку матриці 5 осередків формування топології досліджуваного графа, тобто рядку матриці суміжності графа. На входи елементів І 141-14n потрапляють сигнали з виходів елементів АБО 81-8n та ви ходів тригерів 131-13n реєстраційного масиву 9 осередків незалежної множини. На виході елемента І 14k з'являється одиничний сигнал, якщо вершина k належить до поточного наближення шуканої множини, тобто тригер 13k знаходиться в одиничному стані, та в графі є ребро між вершинами k та і, тобто тригер 6ik знаходиться в одиничному стані - на виході елемента АБО 8k одиничний сигнал, або нульовий сигнал, якщо вершина k не належить до поточного наближення шуканої множини, тобто тригер 13k знаходиться в нульовому стані, або в графі немає ребра між вершинами k та і, тобто тригер 6ik знаходиться в нульовому стані - на виході елемента АБО 8 k н ульовий сигнал. Виходи всіх елементів І 141-14n подаються на входи елементу АБО 15, на виході якого формується нульовий сигнал, якщо вершина і суміжна хоча б з одною вершиною, що належить до поточного наближення до шуканої множини, і одиничний сигнал, якщо вершина і не суміжна ні з одною вершиною, що належить до поточного наближення шуканої множини. 8 Вихідний сигнал елемента АБО-НЕ 15 потрапляє на входи кожного з елементів НЕ 10110n, які інвертують сигнал та відсилають його до перших входів елементів І 111-11n, та перши входи кожного з елементів І 121-12n. Сигнали від дешифратора 3 потрапляють на другі входи елементів І 111-11n та 121-12n. Тому, на виходах елементів І 111-11n та 121-12n, крім елементів І 11i та 12i формуються нульові сигнали, а вихідні сигнали елементів І 11i та 12i формуються наступним чином: якщо вихідний сигнал елементу АБО-НЕ 15 нульовий, на ви ході елемента І 11i з'являється одиничний сигнал, а на виході елемента I 12i з'являється нульовий сигнал, та якщо вихідний сигнал елементу АБО-НЕ 15 одиничний, на виході елемента І 11i з'являється нульовий сигнал, а на виході елемента І 12i з'являється одиничний сигнал. Виходи елементів І 111-11n потрапляють на нульові входи тригерів 131-13n, а виходи елементів І 121-12n потрапляють на одиничні входи тригерів 131-13n, тому тригер 13i перемикається в одиничний стан, якщо вершина і графа не суміжна з жодною вершиною, що належить до поточного наближення до шуканої множини, та в н ульовий стан, якщо вершина і графа суміжна хоча б з однією вершиною, що належить до поточного наближення до шуканої множини. Стани інших тригерів 131-13n, не змінюються. На такті n, крім описаних дій, одиничний сигнал з виходу n дешифратора 3 збільшить значення дворозрядного лічильника 4 на одиницю, й на його виході сформується код «01». На наступному такті значення лічильника 2 буде скинуто в 0, та цикл тактів повториться. Розглянемо стан пристрою після виконання ним n тактів. Тригер 13i було перемкнуто в нульовий або одиничний стан, та більше його стан не змінювався. Тригер 13i знаходиться в одиничному стані, якщо на такті і в поточному наближенні до шуканої множини не було вершин, суміжних з вершиною і. Таким чином, стани тригерів 131-13n відображають незалежну множину, але ця множина може не бути максимальною. Наступні n тактів виконуються аналогічно, але через те, що поточна множина незалежна, жоден з тригерів 131-13n не буде перемкнуто в н ульовий стан, але частина тригерів 131-13n, що вже є в одиничному стані, може бути перемкнута в одиничний стан, якщо відповідні їм вершини не суміжні зі всіма вершинами, що належать до поточного наближення до максимальної незалежної множини. Тому після виконання 2n тактів, стани тригерів 131-13n реєстраційного масиву 9 незалежної множини відображують максимальну незалежну множину вершин графа, що заданий за допомогою матриці 5 осередків формування топології досліджуваного графа. Крім того, на такті 2n одиничний сигнал з виходу n дешифратора 3 потрапить на вхід дворозрядного лічильника 4 та збільшить його значення на одиницю. На виході дворозрядного лічильника 4 сформується код «10». Одиничний сигнал з виходу старшого розряду дворозрядного 9 лічильника 4 потрапить на вхід з упинки генератора тактових імпульсів, та пристрій зупинить свою роботу. 82251 10