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

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