Устройство для исследования графов Советский патент 1987 года по МПК G06F15/173 

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

1

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

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

На фиг.1 приведена структурная схема предлагаемого устройства; на фиг.2 - схема блока управления; на фиг.З и 4 - временные диаграммы работы устройства в режимах нахождения кратчайшего пути и максимальных устойчивых подмножеств соответственно.Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 моделей ребер, каждая модель которой состоит из триггера 4 и элемента И 5, группу 6 элементов ШШ, группу 7 регистров, группы 8 и 9 элементов задержки, группы 10-13 элементов И, группы 14 и 15 элементов ИЛИ, группу 16 триггеров, элемент 17 ИЛИ, вход 18 начальной установки

3237

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

5

0

5

0

5

0

5

0

входы 19 и 20 ввода информации, входы и выходы 21-35 блока 1 управления.

Вход 18 соединен с входом 24 блока 1 управления, выходы 22 и 23 котот рого соединены с первым и вторым входами генератора 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, входы установа в О которых соединены с выходом 31 блока 1 уп

равления, а входы установа в 1 - с второй группой входов 19 устройства, выходы триггеров группы 16 соединены с вторыми входами соответствующих элементов И группы 13.

Выходы элементов задержки группы 9 соединены с первьми входами соответствующих элементов ИЛИ группы 15, вторые входы которых подсоединены к единичным выходам первых разрядов регистров 7, а выходы подключены к четвертым входам соответствующих элементов И группы 10. Выход элемента ИЛИ 17 соединен с входом 35 блока 1 управления.

Блок 1 управления (фиг.2) содержит сдвигающий, регистр 36, реверсив- ньй счетчик 37, триггеры 38 и 39, . элементы 40-42 задержки, элементы И 43-46, элементы И групп 47,48,49 и 50, элементы ШШ 51 и 52, элементы ИЛИ групп 53 и 54 и ключ 55.

Вход 24 блока 1 управления соединен с выходом 31 блока 1 управления, входами установа в О триггеров 38 и 39, входами элемента 40 задержки, сброса в О счетчика 37 и установочным входом регистра 36, п выходов которого соединены с первыми входами соответствующих элементов ИЛИ группы 53, вторые входы которых соединены с выходом элемента 41 задержки и входом элемента 42 задержки, выход которого соединен с пер

выми входами элементов И 45 и 46, втрые входы которых соединены с вьпсо- дом триггера 39, а выходы подключены соответственно к выходам 28 и 29 блока 1 управления.

N-й выход регистра 36 соединен с первым входом элемента ИЛИ 52, второй вход которого соединен с выходом счетчика 37, а выход подключен к выходу 23 блока 1 управления, вход 35 которого.соединен с входом триггера 39, выход которого соединен с выходом 27 блока 1 управления, третьими входами элементов И групп 48 и .4 и вторым входом счетчика 37, первый вход которого соединен с выходом элемента И 44, первый вход которого соединен с выходом триггера 38 и вторым инверсным входом элемента И 43, а второй вход соединен с входом 21 блока 1 управления и первым входом элемента И 43, выход которого соединен с входом сдвига регистра 36 п выходов которого соединены с со

0

5

0

0

5

ответствующими входами элемента - ИЛИ 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.

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

0 подаваемым с входа 18, по которому осуществляется установка в О триггеров 38 и 39, счетчика 37, регистров группы 7, триггеров группы 16, с I по п-разрядов регистра 36,

5 нулевой разряд которого .устанавливается в 1. Сигнал запуска Y;.,, пройдя элемент 40 задержки,запускает генератор 2, устанавливает триггер 38 в состояние 1 и разрешает

0 ввод в .первые разряды регистров

группы 7, куда заносится информация

о начальной вершине i пути графа , установкой данных разрядов в 1 и в триггеры группы 16, содержащие ин- формацию о конечной (i ,) вершине (соответствующий 1( вершине триггер устанавливается в I).

Первый появившийся импульс генератора 2 (Yj) проходит через элементы И 44, ИЛИ 51, 41 задержки, ИЛИ 53 LO и И 50 i и через первую группу п выходов 25 блока 1 управления попадает на вторые входы элементов И 5;ц,- 5 ( р матрицы 3 моделирования.

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

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

Сигналы с выходов элементов задержек группы 8 (Y) проходят через элементы И группы I1, ИЛИ группы 14 и устанавливают первые разряды соответствующих регистров группы 7 в состояние 1.

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

вверх. Таким образом, на данном шаге 5 блокирует его. Во всем остальном втонайдено множество вершин, достижи-рой цикл работы не отличается от пермых из множества вершин С(1), таквого. называемой вершины второй волны.

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

к

элемент ИЛИ 15 i.,появляется на четвертом входе элемента И 10 i|, на первый вход которого поступает сигнал с выхода элемента 6 i, задержки, а второй и третий входы которого являются управляющими, соединенными с единичными выходами триггеров 38 и 39 через выходы 26 и 27 блока I

0 управления. К данному моменту оба триггера установлены в состояние 1, следовательно, элемент И 10 i открыт и сигнал поступает на единичный вход П+1-ГО разряда регистра, в

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

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

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

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

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

Кроме того, во втором цикле обратной волны сигнал d переводит счетчик 37 в реверсивный режим работы. По окончании его работы сигнал /ь с выхода счетчика 37 через элемент ИЛИ 52, выход 23 блока 1 управления попадает в генератор 2 импульсов и

0

0

50

55

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

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

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

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

Нулевые выходы первых разрядов регистров группы 7 через вход 33 блока 1 управления соединены с , первыми входами соответствующих элементов И группы 47, вторые инверсные входы которых соединены с выходом триггера 38, что позволяет анализировать на связность только те верщины, которые не связаны с рассматриваемой вершиной в данном такте. Сигналы с выхода генератора 2 импульсов поступают через вход 21 блока 1 управления и элемент И 43 на вход сдвига регистра 36 и производят циклическое перемещение единицы, обеспечивая выдачу п сигналов с единичных выходов разрядов регистра 36. N-й сигнал, кроме того, через элемент ИЛИ 52, выход 23 (/}) поступает на вход reHepatopa 2 йййульсов и блокирует его работу.

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

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

63237В

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

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

20

5

0

5

0

5

0

5

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

1.Устройство для исследования графов, содержащее блок управления, генератор импульсов, матрицу ixj, (,п, ,п) моделей ребер, первую группу п элементов ИЛИ, группу п регистров сдвига, каждая 1,з-я модель ребра матрицы содержит триггер и элемент И, первый вход которого соединен с выходом триггера мо- дели ребра, вторые входы элементов И моделей ребер i-й строки матрицы объединены и соединены с i-м выходом первой группы п выходов блока управления, выходы элементов И всех моделей ребер j-ro столбца . матрицы соединены с соответствующими входами j-ro (,п) элемента РШИ первой группы, первый и второй выходы блока управления соединены соответственно с первым и вторым входами генератора импульсов,, выход которого соединен с первым входом блока управления, второй вход которого является входом предварительной установки устройства,, третий и четвертый выходы блока управления соединены соответственно с первыми и вторыми входами всех регистров сдви-- га группы, инверсные выходы первых разрядов которых соединены с первой группой п входов блока управления, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем решения задачи нахождения кратчайших путей между двумя любыми вершинами графа и

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

5

0

5

0

5

0

5

0

5

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

2. Устройство по п.1, о т л и - чающееся тем, что в блок управления, содержащий регистр сдвига, счетчик, три элемента задержки, группу элементов И и группу элементов ИДИ, причем второй вход блока управления соединен с входами Предварительной установки в О счетчика и регистра, восьмым выходом блока управления и через первый элемент задержки с вторым выходом блока управ- лени,. i-й вькод регистра сдвига сое динен с первым входом i-ro элемента ИЛИ первой группы, выход которого соединен с первым входом i-ro элемента И первой группы, выходы которых соединены с первой группой п выходов блока управления, введены два триг.- гера, четыре элемента И, вторая, третья и четвертая группы элементов И, вторая группа элементов ИЛИ, (п+1)-входовой элемент ИЛИ, двух- входовой элемент ИЛИ и ключ, первый вывод которого соединен с выходом первого элемента задержки, второй вьшод ключа соединен с седьмым выходом блока управления и с входом установки в 1 первого триггера, вход установки в О которого соединен с вторым входом блока управления и входом установки в О второго триггера, вход установки в 1 которого соединен с третьим входом блока управления, выход второго триггера соединен с шестым выходом блока управления, вторым входом счетчика, первым входом первого и инверсным входом второго элементов И, первыми входами элементов И второй группы и первыми инверсными входами элементов И третьей группы, вторые входы которых соединены с второй группой п входов блока управления, вторые входы элементов И второй группы соединены с первой группой п входов блока управления, третья группа п входов блока управления соединена с прямьми входами элементов И четвертой группы, инверсные

входа которых объединены и соединены с третьими входами элементов И второй и третьей групп, с выходом первого триггера, с пятым выходом блока управления, с первым входом Третьего элемента И и с инверсным входом четвертого элемента И, прямой вход которого соединен с первым входом блока управления и с вторым входом третьего элемента И, выход которого соединен с третьим входом счетчика, и с (п+1)-м входом (п+1)- входового элемента ИЛИ, выход четвертого элемента И соединен с входом управления регистра сдвига, выходы которого соединены с соответствующими входами (п+1)- входового элемента ИЛИ, п-й вход которого соединен с первым входрм двухвходо- вого элемента ИЛИ, второй вход кото2(Уз) узаз) W

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

ФигМ

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