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

 

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

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

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

РЕСПУБЛИН

„„SU„„1363237

А1 в4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ - :-.

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2!) 4090583/24-24 (22) 18.07 ° 86 (46) 30.12.87.Бюл. У 48 (71) Ленинградский электротехничес:кий институт им.В.И.Ульянова (Ленина ) (72) Т.В.Волченская, В.С.Дудкин, В.С.Князьков и Д.П.Пуолокайнен (53) 681.325 (088.8) (56) Авторское свидетельство СССР

В 1133596, кл.G 06 F 15/20, 1985, Авторское свидетельство СССР

У 1180921, кл.G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ (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 кото-, 6 рого соединены с первым и вторым входами генератора 2 импульсов, выход которого соединен с входом 21 блока 1 управления, первая группа выходов 25 которого соединена со10 ответственно с вторыми входами элементов И 5 построчно, первые входы которых соединены с выходами соответ-. ствующих триггеров 4, а выходы каждого элемента И 5 столбца соединены с соответствующими входами элемента ИЛИ 6, расположенного в этом же столбце.

Выход каждого элемента ИПИ в группе 6 соединен с входом соответствующего элемента задержки группы 8 и первыми входами элементов И групп 13 и 12, выходы которых соединены соответственно с входами элемента за2 держки группы 9 и элемента ИЛИ 17 и вторым входом элемента ИЛИ группы 14, первый вход которого соединен с выходом соответствующего элемента И группы 11, а третьи входы всех элементов ИЛИ группы 14 соединены с входом 20 устройства.

Выходы элементов задержки группы

8 соединены с первыми входами элементов И групп 10 и 11, вторые и третьи входы которых соединены соответствен б но с выходами 27 и 26 блока 1 управления, выход 30 которого соединен с управляющими входами триггеров группы 16, входы установа в "0" которых соединены с выходом 31 блока 1 уп1363237 з равления, а входы установа в "1"— .! f с второй группой входов 19 устройства, выходы триггеров группы 16 соединены с вторыми входами соответствую5 щих элементов И группы 13.

Выходы элементов задержки группы

9 соединены с первыми входами соответствующих элементов ИЛИ группы 15, вторые входы которых подсоединены к единичным выходам первых разрядов регистров 7, а выходы подключены к четвертым входам соответствующих элементов И группы 10. Выход элемента ИЛИ 17 соединен с входом 35 бло- !5 ка 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 входами установа в "О" триггеров 38 и 39, входами элемента 40 задержки, сброса в "0" счетчика 37 и установочным входом регистра 36, и выходов которого соединены с первыми 30 входами соответствующих элементов

ИЛИ группы 53, вторые входы которых соединены с выходом элемента 41 задержки и входом элемента 42 задержки, Выход KGTopoI О соединен,c IIBp 35 выми входами элементов И 45 и 46, вторые входы которых соединены с выходом триггера 39, а выходы подключены соответственно к выходам 28 и 29 блока 1 управления.

N-й выход регистра 36.соединен с первым входом элемента ИЛИ 52, второй вход которого соединен с выходом счетчика 37, а выход подключен к выходу 23 блока 1 управления, вход 45

35 которого соединен с входом триггера 39, выход которого соединен с выходом 27 блока 1 управления, третьими входами элементов И групп 48 и .49 и вторым входом счетчика 37, первый В0 вход которого соединен с выходом элемента И 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 блока 1 управления.

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

Режим нахождения кратчайшего пу.ти (фиг.З ): подготовка устройства к работе заключается в замыкании контактов ключа 55 блока 1 управления.

Запуск устройства осуществляется сигналом начальной установки (Y ), подаваемым с входа 18, по которому осуществляется установка в "0 триггеров 38 и 39, счетчика 37, регистров группы 7, триггеров группы

16, с 1 по п- разрядов регисчра 36, нулевой разряд которого устанавливается в "1". Сигнал запуска Y пройдя элемент 40 задержки, запускает генератор 2, устанавливает триггер 38 в состояние "1 " и разрешает ввод в .первые разряды регистров группы 7, куда заносится информация о начальной вершине i пути графа, установкой данных разрядов в "1" и в триггеры группы 16, содержащие информацию о конечной (i <) вершине (соответствующий i -й вершине триггер устанавливается в "1").

Первый появившийся импульс генератора 2 (Yg) проходит через элемен1363237

55 ты И 44, ИЛИ 51, 41 задержки, ИЛИ

53 i и И 50 iä и через первую группу п выходов 25 блока 1 управления попадает на вторые входы элементов

И 5;,- 5,„ матрицы 3 моделирования.

Если некоторые триггеры в i-й строке находятся в состоянии "1", то через соответствующие им элементы

И 5 i-й строки сигналы проходят элементы ИЛИ группы 6, задерживаются элементами группы 8 и анализируются на достижение конечной заданной вершины „.

Появившийся в это время сигнал с выхода 28 блока 1 управления (Y ), который был задержан элементом 42., производит сдвиг вверх в регистрах группы 7, т.е. информация первого разряда переписывается во второй.

Сигналы с выходов элементов задержек группы 8 (Y ) проходят через элементы И группы 11, ИЛИ группы 14 и устанавливают первые разряды соответствующих регистров группы 7 в состояние "1", Таким образом, на данном шаге найдено подмножество вершин, в которых есть ребра (для неориентированных графов ) из вершины 1, С „(,) °

Сигналы с единичных выходов первых разрядов регистров группы 7 открывают элементы И группы 48 блока 1 управления. Второй тактовый Жчпульс в это время появляется на выходах элементов ИЛИ группы 53 и череУ открытые элементы И группы 50 проходит на соответствующие строки матрицы 3 моделирования. Происходит очередное считывание информации рассматриваемых строк и их запись в первые разряды регистров группы 7, содержимое которых было сдвинуто вверх. Таким образом, на данном шаге найдено множество вершин, достижимых из множества вершин C(i ), так называемой вершины второй волны..

Этот процесс продолжается до тех пор, пока не будет достигнута вершина конца пути i «. Сигнал (1) с выхода элемента И 13 i «через элемент ИЛИ 17 и вход 35 блока 1 управления устанавливает триггер 39 в состояние "1". Одновременно происходит сдвиг вверх в регистрах группы

7. Сигнал с выхода элемента И 13 задержанный элементом 9 i, пройдя элемент ИЛИ 15 i ïîÿâëÿåòñÿ на четвертом входе элемента И 10 i«, на первый вход которого поступает сигнал с выхода элемента 6 „ задержки, а второй и третий входы которого являются управляющими, соединенными с единичными выходами триггеров 38 и 39 через выходы 26 и 27 блока 1

10 управления. К данному моменту оба триггера установлены в состояние

1, следовательно, элемент И 10 « открыт и сигнал поступает на единичный вход и+1-ro разряда регистра, в

15 который заносится информация о конечной вершине.

Начинается второй цикл формирования и поиска кратчайших путей (обратная волна ). В этом цикле открыты

20 те элементы И 49, вторые и третьи входы которых связаны с единичными выходами триггеров 38 и 39, а первые входы подключены к единичным выходам (n+1)-х разрядов соответствующих регистров группы 7.

Кроме того, блокирован выход 28 блока 1 управления и открыт выход

29 для сигнала У сдвига вниз регистров группы 7. В этом цикле происходит поиск путей из вершин, которым соответствуют единичные состояния (и+1)-х разрядов регистров группы 7 (в первом случае "записана" одна вершина i ), и пересечение найденных

35 вершин с информацией о вершинах, хранящихся в 1-м разряде регистров группы 7.

Кроме того, во втором цикле обратной волны сигнал o(переводит счетчик

40 37 в реверсивный режим работы. По окончании его работы сигнал р с выхода счетчика 37 через элемент

ИЛИ 52, выход 23 блока 1 управления попадает в генератор 2 импульсов и

45 блокирует его. Во всем остальном второй цикл работы не отличается от первого.

Итак, все кратчайшие пути будут найдены за 2К тактов, где К вЂ” длина пути (все ребра в графе принимаются единичными ). Результирующая информация, начиная со старших разрядов, хранится в регистрах группы 7.

Режим выделения максимальных внутренне устойчивых подмножеств (фиг.4 ); с поступлением сигнала на установочный вход устройства (Y ) 1363237

20 устанавливаются в нулевое состояние первые разряды всех регистров 7, с первого по и-й разряды регистра 36, счетчик 37, триггеры 38 и 39, а нулевой разряд регистра 36 сдвига устанавливается в состояние "1".

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

Нулевые выходы первых разрядов регистров группы 7 через вход 33 блока 1 управления соединены с первыми входами соответствующих элементов И группы 47, вторые инверсные входы которых соединены с выходом триггера 38, что позволяет анализировать на связность только те вершины, которые не связаны с рассматриваемой вершиной в данном такте. Сигналы с выхода генератора 2 импульсов поступают через вход 21 блока 1 управления и элемент И 43 на вход сдвига регистра 36 и производят

I циклическое перемещение единицы, обеспечивая выдачу и сигналов с единичных выходов разрядов регистра 36.

N-й сигнал, кроме того, через элемент ИЛИ 52, выход 23 (р) поступает на вход генератора 2 ийяульсов и блокирует его работу.

Если элемент И группы 50 открыт по второму входу через элемент ИЛИ группы 54 и элемент И группы 47 от нулевого выхода первого разряда соответствующего регистра группы 7, то определяемая им вершина анализируется на предмет исключения из формируемого максимального внутренне устойчивого подмножеста всех инцидентных ей вершин (в соответствующем регистре группы 7 в первом разряде устанавливается,"1" по сигналу Yg). По сигналу Yg,задержанному элементом 42 задержки, регистры группы 7 сдвигаются вверх на один разрядe

После завершения работы (и так. тов) в одноименных и старших разрядах регистров группы 7 записана ин25

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

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

Формула изобретения

l,устройство для исследования графов, содержащее блок управления, генератор импульсов, матрицу ixj (l=l,n, j=l,n) моделей ребер, первую группу и элементов ИЛИ, группу и регистров сдвига,,каждая i j-я модель ребра матрицы содержит триггер и элемент И, первый вход которого соединен с выходом триггера модели ребра, вторые входы элементов И моделей ребер i-й строки матрицы объединены и соединены с х-м выходом первой группы и выходов блока управления, выходы элементов

И всех моделей ребер j-ro столбца . матрицы соединены с соответствующими входами j-го (j=l,n) элемента

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

1363237

10 выделения всех максимальных внутренне устойчивых подмножеств графа, в устройство введены первая и вторая группы элементов задержки, четыре группы по п элементов И, вторая и третья группы по и элементов ИЛИ, группа и триггеров, и-входовой эле.мент ИЛИ, выход i-ro элемента ИЛИ первой группы соединен с входом

i-ro элемента задержки первой группы и первыми входами i-x элементов

И первой и второй групп, выход i-ro элемента задержки первой группы соединен с первыми входами i-х элементов И третьей и четвертой групп, вторые входы которых соединены с пятым выходом блока управления и вторыми инверсными входами элементов И второй группы, третьи инверсные входы которьм объединены и соединены с третьими инверсными входами элементов И третьей группы, с третьими входами элементов И четвертой группы и с шестым выходом блока управления, четвертый вход i-ro элемента И четвертой группы соединены с выходом

i-ro элемента ИЛИ второй группы, первый вход которого соединен с прямым выходом первого разряда i-го регистра сдвига группы и с i-м входом второй группы и входов блока управления, второй вход i-го элемента ИЛИ второй группы соединен с выходом i-ro элемента задержки второй группы, вход которого соединен с выходом элемента И первой группы

1 и с соответствующим входом и-входового элемента ИЛИ, выход которого соединен с третьим входом блока управления, третья группа и входов которого соединена с прямыми выходами (n+1)-х разрядов соответствующих регистров сдвига групп, выход i-ro элемента И четвертой группы соединен с третьим входом i-ro регистра сдви.— га,,четвертый вход которого соединен с выходом i-ro элемента ИЛИ третьей группы, первый и второй входы которого соединены соответственно с выходами i-х элементов И второй и третьей групп, третьи входы элементов ИЛИ третьей группы являются первыми информационными входами устройства, вторые информационные входы устрой" с тва соединены с входами установки в "1" триггеров группы, информационные входы которых объединены и соединены с седьмым выходом блока управвывод которого соединен с выходом первого элемента задержки, второй вывод ключа соединен с седьмым выходом блока управления и с входом установки в "1" первого триггера, вход установки в "0" которого соединен с вторым входом блока управле40

fT II ния и входом установки в 0 второг о триггера, вход установки в " 1 " которого соединен с третьим входом блока управления, выход второго триггера соединен с шестым выходом

45 блока управления, вторым входом счетчика, первым входом первого и инверс ным входом второго элементов И, первыми входами элементов И второй

50 группы и первыми инверсными входами элементов И третьей группы, вторые входы которых соединены с второй группой и входов блока управления, вторые входы элементов И второй группы соединены с первой группой и входов блока управления, третья группа и входов блока управления соединена с прямыми входами элементов И четвертой группы, инверсные

30 ления и с пятыми входами регистров сдвига rруппы,,шестые входы которых объединенЬ и соединены с восьмым выходом блока управления и с объединенными входами установки в "0" триггеров группы, выход i-ro триггера соединен с вторым входом i-ro элемента И первой rруппы.

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что в блок управления, содержащий регистр сдвига, счетчик, три элемента задержки, группу элементов И и группу элементов ИЛИ, причем второй вход блока управления соединен с входами предварительной установки в "0" счетчика и регистра, восьмым выходом блока управления и через первый элемент задержки с вторым выходом блока управ" ления,. i-й выход регистра сдвига соединен с первым входом i-го элемента

ИЛИ первой группы, выход которого соединен с первым входом i"ãî элемента И первой группы, выходы которых соединены с первой группой и выходов блока управления, введены два триггера, четыре элемента И, вторая, третья и четвертая группы элементов

И, вторая группа элементов ИЛИ, (и+1)-входовой элемент ИЛИ, двухвходовой элемент ИЛИ и ключ, первый

1363237

Zf(Yy) 29(Yg) 23lPl Я ж ЗЗ входы которых объединены н соединены с третьими входами элементов И второй и третьей групп, с выходом первого триггера, с пятым выходом блока управления, с первым входом третьего элемента И и с инверсным входом четвертого элемента И, прямой вход которого соединен с первым входом блока управления и с вторым входом третьего элемента И, выход которого соединен с третьим входом счетчика, и с (и+1)-м входом (п+1)входового элемента ИЛИ, выход четвертого элемента И соединен с входом управления регистра сдвига, выходы которого соединены с соответствующими входами (и+1)-входового элемента ИЛИ, I1-A xo KoTaporo соединен с первым входрм двухвходоного элемента ИЛИ, второй вход которого соединен с выходом счетчика,,выход двухвходового элемента ИЛИ соединен с третьим выходом блока управления, выход (и+1)-входового элемента ИЛИ через второй элеМент задержки соединен с вторыми входами элементов ИЛИ первой группы и с входом третьего элемента задержки, вы1д ход которого соединен с вторым входом первого и с прямым входом второ-, го элементов И, выходы которых соединены с третьим и четвертым выхо" дами блока управления соответствен. но, выходы l õ элементов И второй, третьей и четвертой групп соединены с первым, вторым и третьим входа" ми i-го элемента ИЛИ второй группы соответственно, выход которого соеди" нен с вторым входом i-ro элемента

И первой rруппы.

1363237, %

Уа

Уз

Уц

Yg

Фиа 3

Yg

ГР 6

Уз

Составитель С.Кошелев

Редактор А.Маковская Техред М.Дидык Корректор C.Øåêìàð

Закаэ 6364/42 Тираж 671 Подписное

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

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

Ероиэводственно-полиграфическое предприятие,-г.ужгород, ул. Проектная, 4