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

(71) Ленинградский электротехнический институт им.В.И,Ульянова(56) Авторское свидетельство СССРВ 1133596, кл.С 06 Р 15/20, 1985,Авторское свидетельство СССРУ 1180921, кл.С 06 Р 15/20, 1985. ЙСТВ ЛЕДОВАН носится к вычи етениетехникия лог х, в С.Дудкин,окайнен аиши инамальных ожес твеннь ругого ества,ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ(57) Изобрлительнойдля решендач на градения кратлюбыми вервсех максимчивых подм.щихся собсникакого дго подмнож и предназначено ико-комбинаторных зачастности для нахож" путей между двумя графа и выделениявнутренне устой- графа, не являю- и подмножествами внутренне устойчиво в котором никакая1363237 пара вершин не соединена ребром.Целью изобретения является расширениефункциональных возможностей устройства путем решения задачи нахождениякратчайших путей между двумя любымивершинами графа и выделения всех мак"симальных внутренне устойчивых подмножеств графа. Поставленная цельдостигается тем, что в устройстводля исследования графов, содержащее Изобретение относится .к цифровой вычислительной технике и предназначено для решения логико-комбина,торных задач,на графах, в частностинахождения кратчайших путей междудвумя любыми вершинами графа и выде-,ления всех максимальных внутреннеустойчивых подмножеств графа, неявляющихся собственными подмножествами никакого другого внутренне устойчивого подмножества, в которомникакая пара вершин не соединенаребром.Целью изобретения является расши-,рение функциональных возможностейустройства путем решения задачи нахождения кратчайших путей междудвумя любыми вершинами графа и выделения всех максимальных внутреннеустойчивых подмножеств графа.На фиг.1 приведена структурнаясхема предлагаемого устройства; нафиг.2 - схема бпока управления; на.фиг.З и 4 - временные диаграммыработы устройства в режимах нахождения кратчайшего пути и максимальных устойчивых подмножеств соответственно. Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 моделей ребер, каждая модель .которой состоит из триггера 4 и элемента И 5, группу 6 элементов ИЛИ, группу 7 регистров, группы 8 и 9 элементов задержки, группы 10-13 элементов И, группы 14 и 15 элементов ИЛИ, группу 16 триггеров, элемент 17 ИЛИ, вход 18 начальной установки,блок 1 управления, генератор 2 импульсов, матрицу 3 НхБ Моделей ребер,группу 6 элементов ИЛИ, группу 7регистров сдвига, дополнительно введены группы 14 и 15 элементов ИЛИ,группы 8 и 9 элементов задержки,четыре группы 10,11,12, 13 элементовИ, группа 16 триггеров, элементИЛИ 17. 1 з.п. Ф-лы, 4 ил. входы 19 и 20 ввода информации, входы и выходы 21-35 блока 1 управления.Вход 18 соединен с входом 24 блока 1 управления, выходы 22 и 23 кото-, 5 рого соединены с первым и вторымвходами генератора 2 импульсов, выход которого соединен с входом 21блока 1 управления, первая группавыходов 25 которого соединена соответственно с вторыми входами элементов И 5 построчно, первые входыкоторых соединены с выходами соответ-,ствующих триггеров 4, а выходы каждого элемента И 5 столбца соединеныс соответствующими входами элемента ИЛИ 6, расположенного в этом жестолбце.Выход каждого элемента ИПИ в группе 6 соединен с входом соответствующего элемента задержки группы 8 ипервыми входами элементов И групп 13и 12, выходы которых соединены соответственно с входами элемента за В держки группы 9 и элемента ИЛИ 17 ивторым входом элемента ИЛИ группы 14,первый вход которого соединен с выходом соответствующего элемента Игруппы 11, а третьи входы всех элементов ИЛИ группы 14 соединены свходом 20 устройства.Выходы элементов задержки группы8 соединены с первыми входами элементов И групп 10 и 11, вторые и третьивходы которых соединены соответственб но с выходами 27 и 26 блока 1 управления, выход 30 которого соединен суправляющими входами триггеров группы 16, входы установа в "0" которыхсоединены с выходом 31 блока 1 уп.с второй группой входов 19 устройства, выходы триггеров группы 16 соединены с вторыми входами соответствую 5щих элементов И группы 13.Выходы элементов задержки группы9 соединены с первыми входами соответствующих элементов ИЛИ группы 15,вторые входы которых подсоединены кединичным выходам первых разрядоврегистров 7, а выходы подключены кчетвертым входам соответствующихэлементов И группы 1 О. Выход элемента ИЛИ 17 соединен с входом 35 блока 1 управления,Блок 1 управления (фиг.2) содержит сдвигающий. регистр 36, реверсивный счетчик 37, триггеры 38 и 39,элементы 40-42 задержки, элементы 20И 43-46, элементы И групп 47,48,49 и50, элементы ИЛИ 51 и 52, элементыИЛИ групп 53 и 54 и ключ 55.Вход 24 блока 1 управления соединен с выходом 31 блока 1 управления, 25входами установа в "0" триггеров 38и 39, входами элемента 40 задержки, сброса в "0" счетчика 37 и установочным входом регистра 36, и выходов которого соединены с первыми 30входами соответствующих элементовИЛИ группы 53, вторые входы которыхсоединены с выходом элемента 41 задержки и входом элемента 42 задержки, выход которого соединен,с первыми входами элементов И 45 и 46, вторые входы которых соединены с выходом триггера 39, а выходы подключенысоответственно к выходам 28 и 29блока 1 управления.Б-й выход регистра 36.соединен спервым входом элемента ИЛИ 52, второй вход которого соединен с выходом счетчика 37, а выход подключен квыходу 23 блока 1 управления, вход 4535 которого соединен с входом триггера 39, выход которого соединен свыходом 27 блока 1 управления, третьими входами элементов И групп 48 и .49и вторым входом счетчика 37, первый 50вход которого соединен с выходомэлемента И 44, первый вход которогосоединен с выходом триггера 38 ивторым инверсным входом элементаИ 43, а второй вход соединен с входом 21 блока 1 управления и первымвходом элемента И 43, выход которогосоединен с входом сдвига регистра 36,и выходов которого соединены с соответствующими входами элемента -ИЛИ 51, (и+1)-й вход которого соединен с выходом элемента И 44, а выходсоединен с элементом 41 задержки.Выход элемента 40 задержки соединен с выходом 22 блока 1 управленияи с одним из контактов ключа 55,второй контакт которого соединен свыходом 30 блока 1 управления и входом триггера 38, выход которого соединен с выходом 26 блока 1 управления и вторыми входами элементов Игрупп 47-49,Первая 34, вторая 32 и третья 33группы входов блока 1 управления соединены с первыми входами элементовИ соответственно групп 47-49, выходыкоторых соединены с соответствующимивходами соответствующих элементовИЛИ группы 54, выходы которых соединены с вторыми входами элементов Игруппы 50, выходы которых соединеныс первой группой выхсдов 25 блокауправления.Устройствс может работать в режиме нахождения кратчайшего пути (илинескольких путей )между двумя вершинами графа и в режиме вьщеления максимальных внутренне устойчивых подмножеств в множестве вершин графа,матрица смежности которого смоделирована матрицей 3.Режим нахождения кратчайшего пу.ти (фиг.З ): подготовка устройства кработе заключается в замыкании контактов ключа 55 блока 1 управления.Запуск устройства осуществляетсясигналом начальной установки (У ),подаваемым с входа 18, по которому осуществляется установка в 0триггеров 38 и 39, счетчика 37, регистров группы 7, триггеров группы16, с 1 по п- разрядов регистра 36,нулевой разряд которого .устанавливается в "1". Сигнал запуска 7пройдя элемент 40 задержки, запускает генератор 2, устанавливает триггер 38 в состояние "1 " и разрешаетввод в .первые разряды регистровгруппы 7, куда заносится информацияо начальной вершине д пути графа,установкой данных разрядов в "1 " ив триггеры группы 16, содержащие ин.формацию о конечной (1.) вершине(соответствующий -й вершине триггер устанавливается в "1"),Первый появившийся импульс генератора 2 (У) проходит через элемен1363237 50 55 ты И 44, ИЛИ 51, 41 задержки, ИЛИ53 д и И 50и через первую группу п выходов 25 блока 1 управленияпопадает на вторые входы элементовИ 5; ,- 5 , матрицы 3 моделирования.Если некоторые триггеры в х-йстроке находятся в состоянии "1", точерез соответствующие им элементыИ 5 ь-й строки сигналы проходятэлементы ИЛИ группы 6, задерживаются элементами группы 8 и анализируются на достижение конечной заданнойвершины .Появившийся в это время сигналс выхода 28 блока 1 управления (У ),который был задержан элементом 42.,производит сдвиг вверх в регистрахгруппы 7, т.е. информация первогоразряда переписывается во второй.Сигналы с выходов элементов задержек группы 8 (У ) проходят через элементы И группы 11, ИЛИ группы 14 иустанавливают первые разряды соответствующих регистров группы 7 в состояние "1",Таким образом, на данном шагенайдено подмножество вершин, в которых есть ребра (для неориентированных графов ) из вершины, С (,).Сигналы с единичных выходов первыхразрядов регистров группы 7 открывают элементы И группы 48 блока 1управления. Второй тактовый импульсв это время появляется на выходахэлементов ИЛИ группы 53 и череУоткрытые элементы И группы 50 проходит на соответствующие строки матрицы 3 моделирования. Происходиточередное считывание информациирассматриваемых строк и их запись впервые разряды регистров группы 7,содержимое которых было сдвинутовверх. Таким образом, на данном шагенайдено множество вершин, достижимых из множества вершин С( ), такназываемой вершины второй волны. Этот процесс продолжается до тех пор, пока не будет достигнута вершина конца пути. Сигнал (1) с выхода элемента И 13 ьчерез элемент ИЛИ 17 и вход 35 блока 1 управления устанавливает триггер 39 в сос аояние "1". Одновременно происходит сдвиг вверх в регистрах группы 7, Сигнал с выхода элемента И 13 д , задержанный элементом 9, пройдя элемент ИЛИ 15 ,появляется на четвертом входе элемента И 10 д, напервый вход которого поступает сигнал с выхода элемента 6задержки, а второй и третий входы которогоявляются управляющими, соединеннымис единичными выходами триггеров 38и 39 через выходы 26 и 27 блока 1 10 управления. К данному моменту обатриггера установлены в состояние1 следовательно, элемент И 10 доткрыт и сигнал поступает на единичный вход и+1-го разряда регистра, в 15 который заносится информация о конечной вершине.Начинается второй цикл формирования и поиска кратчайших путей (обратная волна ). В этом цикле открыты 20 те элементы И 49, вторые и третьивходы которых связаны с единичнымивыходами триггеров 38 и 39, а первыевходы подключены к единичным выходам(и+1)"х разрядов соответствующих регистров группы 7.Кроме того, блокирован выход 28блока 1 управления и открыт выход29 для сигнала У сдвига вниз регистров группы 7. В этом цикле происходит поиск путей из вершин, которымсоответствуют единичные состояния(и+1)-х разрядов регистров группы 7(в первом случае "записана" однавершина х ), й пересечение найденных 35 вершин с информацией о вершинах, хранящихся в 1-м разряде регистровгруппы 7,Кроме того, во втором цикле обратной волны сигнал Ы переводит счетчик 40 37 в реверсивный режим работы. Поокончании его работы сигнал р свыхода счетчика 37 через элементИЛИ 52, выход 23 блока 1 управленияпопадает в генератор 2 импульсов и 45 блокирует его. Во всем остальном второй цикл работы не отличается от первого. Итак, все кратчайшие пути будут найдены за 2 К тактов, где К - длина пути (все ребра в графе принимаются единичными ). Результирующая информация, начиная со старших разрядов, хранится в регистрах группы 7.Режим выделения максимальных внутренне устойчивых подмножеств (фиг.4 ; с поступлением сигнала на установочный вход устройства (У )устанавливаются в нулевое состояние первые разряды всех регистров 7, с первого по и-й разряды регистра 36, счетчик 37, триггеры 38 и 39, а нулевой разряд регистра 36 сдвига устанавливается в состояние "1".За и тактов из трех шагов формируются все п максимальных внутренне устойчивых подмножеств, обязательно содержащих вершину, номер которой соответствует номеру такта. Искомое максимальное внутренне устойчивое подмножество, не являющееся собственным подмножеством никакого другого внутренне устойчивого подмножест ва, в котором никакая пара вершин не соединена ребром, формируется в первых разрядах регистров группы 7.Нулевые выходы первых разрядов регистров группы 7 через вход 33 блока 1 управления соединены с первыми входами соответствующих элементов И группы 47, вторые инверсные входы которых соединены с выходом триггера 38, что позволяет анализировать на связность только те вершины, которые не связаны с рассматриваемой вершиной в данном такте. Сигналы с выхода генератора 2 импульсов поступают через вход 21 блока 1 управления и элемент И 43 на вход сдвига регистра 36 и производят/ циклическое перемещение единицы, обеспечивая выдачу п сигналов с единичных выходов разрядов регистра 36. Б-й сигнал, кроме того, через элемент ИЛИ 52, выход 23 (р) поступает на вход генератора 2 ийвульсов и блокирует его работу.Если элемент И группы 50 открыт по второму входу через элемент ИЛИ группы 54 и элемент И группы 47 от нулевого выхода первого разряда соответствующего регистра группы 7, то определяемая им вершина анализируется на предмет исключения из формируемого максимального внутренне устойчивого подмножеста всех инцидентных ей вершин (в соответствующем регистре группы 7 в первом разряде устанавливается,"1 " по сигна- лу У). По сигналу У,задержанному элементом 42 задержки, регистры группы 7 сдвигаются вверх на один разрядеПосле завершения работы (п так. тов) в одноименных и старших разрядах регистров группы 7 записана ин 10 15 20 25 30 35 40 45 50 55 формация о выделенных максимальныхвнутренне устойчивых подмножествахвершин, содержащих.все вершины графа.При этом характеристика максимального внутренне устойчивого подмножества, содержащего первую вершину,записывается в (и+1)-х разрядахрегистров группы 7, содержащего вторую вершину - в и разрядах и т.д.,содержащего и-ю вершину - во вторыхразрядах. Вершина графавходит вмаксимальное внутренне устойчивоеподмножество вершин графа, если в регистрах группы 7, соответствующихданной вершине, в разряде, соответствующем данному максимальному внутренне устойчивому подмножеству вершин, записан нуль, и не входит, еслизаписана 1,Формула изобретения 1,устройство для исследования графов, содержащее блок управления, генератор импульсов, матрицу дх 1, (1=1,п, 1=1,п) моделей ребер, первую группу и элементов ИЛИ, группу п регистров сдвига, каждая д,1-я модель ребра матрицы содержит триггер и элемент И, первый вход которого соединен с выходом триггера модели ребра, вторые входы элементов И моделей ребер 1.-й строки матрицы объединены и соединены с х-м выходом первой группы и выходов блока управления, выходы элементов И всех моделей ребер 1-го столбца . матрицы соединены с соответствующими входами 1-го Я=1,п) элемента ИЛИ первой группы, первый и второй выходы блока управления соединены соответственно с первым и вторым входами генератора импульсов выход которого соединен с первым входом блока управления, второй вход которого является входом предварительной установки устройства, третий и четвертый выходы блока управления соединены соответственно с первыми и вторыми входами всех регистров сдвига группы, инверсные выходы первых разрядов которых соединены с первой группой и входов блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем решения задачи нахождения кратчайших путей между двумя любыми вершинами графа ивыделения всех максимальных внутренне устойчивых подмножеств графа, в устройство введены первая и вторая группы элементов задержки, четыре группы по и элементов И, вторая и третья группы по и элементов ИЛИ, группа и триггеров, и-входовой элемент ИЛИ, выход д-го элемента ИЛИ первой группы соединен с входом -го элемента задержки первой группы и первыми входами -х элементов И первой и второй групп, выход -го элемента задержки первой группы соединен с первыми входами -х элементов И третьей и четвертой групп, вто- рые входы которых соединены с пятым выходом блока управления и вторыми инверсными входами элементов И второй группы, третьи инверсные входы которьм объединены и соединены с третьими инверсными входами элементов И третьей группы, с третьими входами элементов И четвертой группы и с шестым выходом блока управления, четвертый вход -го элемента И четвертой группы соединены с выходом д-го элемента ИЛИ второй группы, первый вход которого соединен с прямым выходом первого разряда х-го регистра сдвига группы и с -м входом второй группы и входов блока управления, второй вход д-го эле" мента ИЛИ второй группы соединен с выходом -го элемента задержки второй группы, вход которого соединенс выходом элемента И первой группы 1и с соответствующим входом и-входового элемента ИЛИ, выход которого соединен с третьим входом блока управления, третья группа и входов которого соединена с прямыми выходами (и+1)-х разрядов соответствующих регистров сдвига групп, выход -го элемента И четвертой группы соединен с третьим входом -го регистра сдви. - гачетвертый вход которого соединен с выходом х-го элемента ИЛИ третьей группы, первый и второй входы которого соединены соответственио с выходами х-х элементов И второй и третьей групп, третьи входы элементов ИЛИ третьей группы являются первыми информационными входами устройства, вторые информационные входы устрой" с тва соединены с входами установки в "1" триггеров группы, информационные входы которых объединены и соединены с седьмым выходом блока управ вывод которого соединен с выходомпервого элемента задержки, второйвывод ключа соединен с седьмым выходом блока управления и с входомустановки в "1" первого триггера,вход установки в "О" которого соединен с вторым входом блока управле11 11ния и входом установки в О второг о триггера , вход установки в " 1 "которого соединен с третьим входомблока управления , выход второготриггера соединен с шестым выходом 45блока управления, вторым входом счетчика, первым входом первого и инверсным входом второго элементов И, первыми входами элементов И второй 50группы и первыми инверсными входамиэлементов И третьей группы, вторыевходы которых соединены с второйгруппой и входов блока управления,вторые входы элементов И второйгруппы соединены с первой группойи входов блока управления, третьягруппа и входов блока управлениясоединена с прямыми входами элементов И четвертой группы, инверсные 10 15 20 25 30 ления и с пятыми входами регистровсдвига группы, шестые входы которыхобъединенМ и соединены с восьмымвыходом блока управления и с объединенными входами установки в "О"триггеров группы, выход д-го триггера соединен с вторым входом 1.-гоэлемента И первой группы. 2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что в блок управления, содержащий регистр сдвига, счетчик, три элемента задержки, группу элементов И и группу элементов ИЛИ, причем второй вход блока управления соединен с входами предварительной установки в "О" счетчика и регистра, восьмым выходом блока управления и через первый элемент задержки с вторым выходом блока управ" ления,. -й выход регистра сдвига соединен с первым входом -го элемента ИЛИ первой группы, выход которого соединен с первым входом "го элемента И первой группы, выходы которых соединены с первой группой и выходов блока управления, введены два триггера, четыре элемента И, вторая, третья и четвертая группы элементов И, вторая группа элементов ИЛИ, (и+1)-входовой элемент ИЛИ, двухвходовой элемент ИЛИ и ключ, первыйвходы которых объединены н соединены с третьими входами элементов Ивторой и третьей групп, с выходомпервого триггера, с пятым выходомблока управления, с первым входомтретьего элемента И и с инверснымвходом четвертого элемента И, прямой вход которого соединен с первымвходом блока управления и с вторым входом третьего элемента И, выход которого соединен с третьим входомсчетчика, и с (и+1)-м входом (и+1)входового элемента ИЛИ, выход четвертого элемента И соединен с входом управления регистра сдвига, выходы которого соединены с соответствующими входами (и+1)-входовогоэлемента ИЛИ, и-й вход которогосоединен с первым входрм двухвходоного элемента ИЛИ, второй вход которого соединен с выходом счетчика, ,выход двухвходового элемента ИЛИ соединен с третьим выходом блока управления, выход (и+1)- входового элемента ИЛИ через второй элеМент задержки соединен с вторыми входами элементов ИЛИ первой группы и с входом третьего элемента задержки, выход которого соединен с вторым входом первого и с прямым входом второ-, го элементов И, выходы которых соединены с третьим и четвертым выхо" дами блока управления соответствен 15 но, выходы -х элементов И второй,третьей и четвертой групп соединены с первым, вторым и третьим входа" ми -го элемента ИЛИ второй группы соответственно, выход которого соеди" нен с вторым входом -го элемента И первой группы.363237,Фиа 3 г,4 Редактор А.Маковск Тираж 671 ПодписиГосударственного комитета СССРелам иэобретений и открытийМосква, Ж, Раушская наб., д.4/5 Закаэ 6364/42 ВНИИПИ по 113035, Броиэводственно-полиграфическое предприятие,.г.ужгород, ул. Проектн 6 з Составитель С.Кошелевехред М.Дидык Корректор С.Шекма