Устройство для исследования графов

 

УСТРОЙСТВО ДНЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее блок управления, генератор импульсов, группу элементов ШШ и матрицу NN моделей ребер, причем каждая модель ребра содержит триггер , отличающееся тем, что, с цепью расширения функциональных возможностей путем определения максимальных внутренне устойчивых подмножеств вершин, в него введена группа регистров, а в каждую модель ребра - элемент И, блок управления содержит регистр, счетчик, дешифратор , три элемента задержки, группы элементов ИЛИ и элементов И, выходы и первые входы которых соединены соответственно с первыми входами элементов И моделей ребер одноименных строк матрицы моделей ребер и с нулевыми выходами первых разрядов одноименных регистров, вторые входы элементов И группы блока управления подключены к выходам одноименных элементов ИЛИ блока управления, выходы регистра блока управления соединены с первыми входами одноименных элементов ИЛИ группы блока управления, N выходов дешифратора подключены к вторым входам одноименных элементов ИЛИ группы блока управления, (N +1 )-й выход дешифратора соединен с входом останова генератора импульсов, вход дешифратора подключен к выходу счетчика, N -и выход регистра блока управления через первый элемент задержки соединен с входами сдвига регистров, а через второй элемент задержки - со (Л счетным входом счетчика, установочный вход которого соединен с входом третьего элемента задержки, установочным входом регистра блока управления, S установочными входами регистров и .является установочным входом устройг , ства, выход третьего элемента задержки подключен к входу запуска генератора импульсов, выход которого соединен с входом сдвига регистра блока управления, выход триггера каждой модели ребра подключен к второму входу элемента И модели ребра, выходы элементов И моделей ребер каждого столбца матрицы моделей ребер соединены с входами одноименного элемента ШШ группы,выход которого соединен с входом первого разряда одноименного регистра.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

fl0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (l ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPGHOMY СВИДЕТЕЛЬСТВУ. (21) 3724705/24-24 (22) 13. 04.84 (46) 23.09.85. Вюл. N- 35 (72) С . В . Назаров, А. С . Омельченко, С. С ..Черенщиков, В.М. Крикунов и В.А.Титов (53) 681,333(088.8) (56) Авторское свидетельство СССР У 525954, кл. G 06 F 15/20, 1974.

Авторское свидетельство СССР

В 716043, кл. G 06 F 15/20, 1977 ° (54)(57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ, содержащее блок управления, генератор импульсов, группу элементов ИЛИ и матрицу и М моделей ребер, причем каждая модель ребра содержит триггер, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей путем определения максимальных внутренне устойчивых подмножеств вершин, в него введена группа регистров, а в каждую модель ребра — элемент И, блок управления содержит .регистр, счетчик, дешифратор, три элемента задержки, группы элементов ИЛИ и элементов И, выходы и первые входы которых соединены соответственно с первыми входами элементов И моделей ребер одноименных строк матрицы моделей ребер и . с нулевыми выходами первых разрядов одноименных регистров, вторые входы элементов И группы блока управ„„su„„ a ления подключены к выходам одноименных элементов ИЛИ блока управления, выходы регистра блока управления соединены с первыми входами одноименных элементов ИЛИ группы блока управления, М выходов дешифратора подключены к вторым входам одноименных элементов ИЛИ группы блока управления, (11 +1 )-й выход дешифратора соединен с входом останова генератора импульсов, вход дешифра-: тора подключен к выходу счетчика, N -й выход регистра блока управления через первый элемент задержки соеа дин ен с входами сдви ra р егистр ов, ® а через второй элемент задержки — со счетным входом счетчика, установочный вход которого соединен с входом третьего элемента задержки, установочным входом регистра блока управления, а установочными входами регистров и является установочным входом устрой, ства, выход третьего элемента задержки подключен к входу запуска генератора импульсов, выход которого соединен с входом сдвига регистра блока управления, выход трйггера каждой модели ребра подключен к второму входу элемента И модели ребра, выходы элементов И моделей ребер кажцого столбца матрицы моделей ребер соединены с входами одноименного элемента ИЛИ группы, выход которого фв соединен с входом первого разряда . одноименного регистра.

) 180921

Изобретение относится к вычислительной технике, в частности к решению на графах задач выделения максимальных внутренне устойчивых подмножеств, не являющихся собствен- з ным подмножеством никакого другого внутренне устойчивого подмножества, в котором никакая пара вершин не соединена ребром.

Цель изобретения — расширение функциональных воэможностей путем определения максимальных внутренне устойчивых подмножеств вершин.

На фиг. 1 приведена структурная схема устройства; на фиг. 2 — струк- 15 турная схема блока управления.

Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 N К моделей ребер, причем каждая модель содержит триггер 4 и элемент И 5, И элементов ИЛИ 6, N регистров 7. Блок 1 управления содержит регистр 8, счетчик 9, дешифратор 10, первый 11, второй 12 и третий 13 элементы задержки, N эле- 25 ментов ИЛИ 14 и N элементов И 15.

Устройство работает следующим образом.

В матрицу 3 моделей ребер заносится информация о топологии графа, 31) при этом триггеры 4 устанавливаются в единичное состояние согласно матрице смежности графа.

С поступлением сигнала на установочный вход устройства устанавливаются в нулевое состояние первые разряды всех регистров 7,устанавливаются в единичное состояние нулевой разряд и в нулевое состояние 4О остальные N разрядов регистра 8, сбрасывается в нулевое состояние счетчик 9, на первом выходе дешифра-. тора 10 вырабатывается сигнал, который через элементы ИЛИ 14, И 15, И 5 < — И 5р, ИЛИ 61 — ИЛИ 6,,1 обеспечивает занесение первой строки матрицы 3 моделей ребер в первые разряды регистров 7. Через третий элемент 13 задержки осуществляется запуск генератора 2.

Работа устройства состоит из N циклов, в каждом из которых определятся одно максимальное внутренне устойчивое подмножество, обя-, зательно содержащее вершину, номер которой определяется содержимым счетчика 9. Искомое множество формируется в первых разрядах регистров 7.

Сигналы с нулевых выходов первых разрядов регистров 7 поступают на первые входы соответствующих элементов И 15 и обеспечивают возможность дальнейшего анализа на связность только тех вершин которые не инцидентны с заданной в данном цикле вершиной.

Сигналы с выхода генератора 2 поступают на сдвигающий вход регистра 8 и производят цикличное перемещение единицы, обеспечивая выдачу последовательности N+1 сигналов с единичных выходов разрядов регистра 8, которая определяет цикл работы устройства по выделению одного максимального внутренне устойчивого подмножества вершин графа.

Сигналы с выходов регистра 8 через элементы ИЛИ 14 обеспечивают последовательный просмотр всех элементов

И 15 с целью определения необходимос-. ти анализа вершин графа, соответствующей данной строке матрицы 3 моделей ребер, на возможность ее включения и максимальное внутренне устойчивое подмножество- вершин графа, содержащее вершину, выбранную в данном цикле. Если соответствующий элемент И 15 открыт по первому входу от нулевого выхода первого разряда соответствующего регистра 7, то определяемая им вершина анализируется на предмет исключения из формируемого максимального внутренне устойчивого подмножества всех инцидентных ей вершин. В конце каждого очередного цикла работы устройства (по N"у импульсу генератора 2 в .данном цикле) на единичйом выходе

N-ro разряда регистра 8 вырабатывается сигнал, который, кроме обычных действий, через первый элемент 11 задержки осуществляет сдвиг на один разряд содержимого регистров 7 и через второй элемент 12 задержки увеличивает на единицу содержимое счетчика 9. Выходной сигнал с соответствующего выхода дешифратора

10 подготавливает схему устройства к очередному циклу аналогично тому, как это делается по выходному сигналу с первого выхода дешифратора 10 в первом цикле. Последний (N +1)-й импульс генератора 2 в кажр,ом цикле > работы устройства осуществляет цикз 1 лический сдвиг N — ro н нулевой разряд регистра 8, завершая тем самым подготовку устройства к следующему циклу выделения очередного максимального внутренне устойчивого подмножества вершин графа.

В конце каждого цикла информация о топологии исследуемого графа сохраняется в матрице 3 моделей ребер,в нулевом разряде регистра 8 записана единица, в остальных его разрядах— нули, содержимое счетчика 9 увеличено на единицу, информация о ранее сформированных максимальных внутренне устойчивых подмножествах вершин графа зафиксирована в одноименных разрядах регистров 7 и сдвинута в один разряд в сторону старших разрядов в первые разряды регистров

У

7 занесена строка матрицы 3 моделей ребер, которая обязательно включается в максимальное внутренне устойчивое подмножество вершин графа, формируемое в следующем цикле работы устройства.

В конце N-ro цикла работы устройства по N-у импульсу генератора 2 выполняются действия, аналогичные действиям по N-у импульсу генератора 2 в предыдущих циклах, за исклю180921 4 чением того, что увеличение на единицу содержимого счетчика 9 приводит к появлению сигнала на (М + 1) -м выходе дешифратора 10 который поступает на запрещающий вход генератора 2 и останавливает работу устройства.

После завершения работы устройст1О ва в одноименных N старших разрядах регистров 7 записывается информация о выделенных максимальных внутренне устойчивых подмножествах вершин, содержащих все вершины графа. При этом характеристика максимального внутренне устойчивого подмножества, содержащего первую вершину графа, записывается в (N + 1)-х разрядах регистров 7, содержащего вторую вер2п шину в N-х разрядах содержащего

N-ю вершину во вторых разрядах, а в первых разрядах записываются нули.

Вершина графа входит в максимальное внутренне устойчивое подмножество

25 вершин графа, если в регистре 7, соответствующем данной вершине, в разряде, соответствующем данному максимальному внутренне устойчивому подмножеству вершин, записан нуль, и не входит, если записана единица.

1180921

1 180921

Составитель А.Шеренков

Редактор P.Öèöèêà Техред А.Бабинец Корректор Е.Сирохман

Заказ 5928/49 Тиран 709 Подлисное

ВНИИПИ Государственного комитета СССР по делам изобретений и рткрытий

113035, Москва,Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ултород, ул . Проектная, 4