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

(Л

СП

о

ОО

о

3151703

становок, блок 14 формирования сочетаний, группу 13 элементов И, дешифратор 17, первый 24 и второй 28 триггеры, блок 31 задания топологии графа, введены первый 4 и второй 9 регистры сдвига, с первого по шестой коммутаторы 5,6,10,11,12,19, первый 7 и второй 8 блоки памяти, с первого по шестой элементы И 25,26,29,30,13, Q

45, блок I6 накопления пленарных вершин, вторая группа 18 элементов И, узлы последовательного опроса раэря- дов по вертикали 20 и по горизонтали 21 , группа элементов ИЛИ 22, с первого по одиннадцатый элементы ИЛИ 23,32,34,33,36,37,39,40,41,42,46, первый 27 и второй 38 элементы задержки и элемент 33 сравнения. 5 ил.

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы при автоматизированном проектировании электронных схем. Цель изобретения - сокращение аппаратурных затрат. Для этого в устройство, содержащее генератор 1 тактовых импульсов, ключ 2, блок 3 формирования перестановок, блок 14 формирования сочетаний, группу 15 элементов И, дешифратор 17, первый 24 и второй 28 триггеры, блок 31 задания топологии графа, введены первый 4 и второй 9 регистры сдвига, с первого по шестой коммутаторы 5, 6, 10, 11, 12, 19, первый 7 и второй 8 блоки памяти, с первого по шестой элементы И 25, 26, 29, 30, 13, 45, блок 16 накопления планарных вершин, вторая группа 18 элементов И, узлы последовательного опроса разрядов по вертикали 20 и по горизонтали 21, группа 22 элементов ИЛИ, с первого по одиннадцатый элементы ИЛИ 23, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 46, первый 27 и второй 38 элементы задержки и элемент 33 сравнения. 5 ил.

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы при автоматизированном проектиро- вании электронных схем.

Целью изобретения является сокращение аппаратурных затрат.

На фиг.1 Приведена структурная схема устройства; на фиг.2 - вариант вьтолнения функциональной схемы блока накопления планарных вершин; на фиг. 3 и 4 - варианты в ыполнения функ1Ц1ональных схем узлов послепова- тельного опроса разрядов по вертикали и горизонтали соответственно; на фиг.5 - функциональная схема коммутатора выходов блока формирования сочетани 1.

Устройство содержит генератор 1 тактовых импульсов, ключ 2, блок 3 формирования перестановок, первый регистр 4 сдвига, первьй 5 и второй 6 коммутаторы, первый 7 и второй 8 блоки памяти, второй регистр 9 сдвига, третий 10, четвертый 11 и пятый 12 коммутатор,1, пятый элемент И 13, блок 14 формирования сочетаний, первую группу 15 элементов И, блок 16 накопления плянарных вершин, дешиф- 5атор 17, вторую группу 18 элементов И, шестой коммутатор 19, узлы 20 и 21 последовательного опроса разрядов по вертикали и по горизонтали группу элементов ИЛИ 22, первый эле- i-ieHT ИЛИ 23, первый триггер 24, перв 25 и пторой 26 элементы И, первый :элемент 27 задержки, второй триггер 28, третий 29 и четвертый 30 элементы И, блок 31 задания топологии графа, второй элемент ИЛИ 32, элемент 33 сравнения, третий 34, четвертый 35, пятый 36 и шестой 37 элементы ИЛИ, BTOpoi i элемент 38 задержки.

0

5

0

5

0

седьмой элемент ИЛИ 39, восьмой 40, девятый 41 и десятый 42 элементы ИЛИ, общий вход 43 установки исходного состояния устройства, вход 44 сигнала логической I, шестой элемент И 45 и одиннадцатый элемент ИЛИ 46.

Каждый разряд блока 16 (фиг.2), кроме первого и двух последних, содержит триггер 47, элемент ЗАПРЕТ 48 элемент 49 задержки, элементы И 50 - 52, триггер 53, элемент И 54, элемент ИЛИ 55 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 56. Первый разряд блока 16 содержит перечисленные элементы за исключением элемента задержки, элемента И 50 и элемента ИЛИ. В предпоследнем разряде отсутствует элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, а последний разряд содержит триггер 47, элемент 49 задержки и элемент И 50. Кроме того, блок 16 содержит общие на всю схему элементы И 57, задержки 58 и ИЛИ 59.

Каждый разряд узла 20 содержит элементы И 60 и 61, инвертор 62, элементы ИЛИ 63 и 64, триггеры 65 и 66 и элемент ИЛИ 67.

Каждый разряд узла 21 содержит элементы И 68 и 69, элементы ИЛИ 70 - 72, триггеры 73 и 74 и инвертор 75.

Коммутатор 19 содержит диагональные элементы ИЛИ 76, элементы И- НЕ 77, элементы ИЛИ 78 и 79.

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

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

Дпя того, чтобы одновременно с исследованием графа на плянарность можно было выделять и его максимально планарную часть, используется такой формирователь последовательности

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

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

Блоком 14 формирования сочетаний генерируется лекситографическая по - следовательность сочетаний булевых переменных. Каждое такое сочетание выбирает иэ блока 31 задания топологии графа с помощью коммутатора 19 и узлов 20 и 21 соответствующую пятерку вершин. С помощью блока 3 формирования перестановок, регистров 4 и 9 сдвига, блоков 7 и 8 памяти, коммутаторов 5,6 и 10 - 12 и элемента 33 сравнения вьтолняется процедура про-, верки на изоморфизм выбранной пятерки вершин и полносвязного пяти- вершинного графа, информация о кото5 0 5

0

5

0

5

0

5

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

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

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

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

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

Перед пуском устройстпа осуществляется подготовка его к работе. Дни

э-

этого на вход 43 подается сигнал начальной установки, по которому блок 3 формирования перестановок, регистры 4 и 9, блок 16 накопления пла- нарньк вершин, узел 20 и триггеры 24 и 28 устанавливаются в нулевое сост тояиие, а в первый разряд узла 21 за- письгоается единица. По этому же сигналу в первые пять разрядов блока 14 формирования сочетаний заносятся единицы, что соответствует исходному сочетанию 111110...О. По соответствующим входам в блок 31 задания топологии графа заносится информация о топологии исследуемого графа. После этого замыкается ключ 2, и тактовые импульсы начинают поступать на схему. Поскольку до тех пор, пока в блок 16 не перепишется первая пятерка планар ных вершин, он находится в нулевом состоянии. То единичный сигнал этого состояния подключает к выходным элементам ШШ коммутатора 1 9 все диаго- Р1альные элементы И-НЕ 77. Поэтому единичные сигналы с первых пяти разрядов блока 14 формирования сочетаний, поступая на первые пять нижних входов коммутатора 19, проходят на первые пять верхних его выходов и поступают на первые пять входов узла 20. Блок 3 формирования перестановок в исходном состоянии, т.е. при 1гулевой перестановке, при поступлении на него тактовых импульсов выдает еди яичные сигналы последовательно на выходах : 1,2,3,4,5.

Таким образом, по первому тактовому импульсу в блоке 3, в регистре 4 и в узле 20 возбуждаются их первые ряз- ряды (т.е. единичные сигналы появляют ся на их первых разрядах). При этом ни из блока 7 памяти ,..ни из блока 31 считывание информации не происходит, так как информация о связности двух в ершин .может появиться только при одновременном их возбуждении. Второй тактовый импульс возбуждает в блоке 3, в регистре 4 и в узле 20 вторые их выходы. При этом единичный сигнал с первого выхода узла 21 через первый (верхний) элемент ИЛИ 22 поступает на первый (верхний) вход блока 31, а с второго выхода узла 20 через второй элемент ИЛИ 22 - на второй вход блока 31. Если вершины, соответствующие первому и второму входам блока 31 связаны, то на одном из его выходов появляется единичный сигнал. Одно

10

15

20

25

30

. - 1,

Ш

45

50

55

временно с этим из блока 7 памяти считывается единица (так как в полном пятивершинном графе все вершины связаны), которая через коммутатор 12 и элемент ИЛИ 34 поступает на элемент 33 сравнения. Поэтому элемент 33 сравнения на своем выходе сигнал не выра- батьшает. Если первая и вторая вершины исследуемого графа оказываются несвязанными, то на выходе элемента ИЛИ 32 - нулевой сигнал, и элемент 33 выдает на своем выходе сигнал несравнения, по которому происходит установка в исходное состояние узла 20 через элемент ИЛИ 37 и узла 21 сначала через элемент ИЛИ 42 в нулевое состояние, а через элемент 38 задержки и элемент ИЛИ 39 - в исходное состояние (т.е. в первое). Этот же сигнал несравнения с выхода элемента 33 сравнения, поступая на вход блока 3, устанавливает (а точнее готовит его к формированию) вторую перестановку 2,1,3,4,5.

Полагают, что сигнал несраннения по второму тактовому импульсу на выходе элемента 33 не выработался. Поэтому по третьему тактовому импульсу аналогично описанному из блока 7 памяти и блока 31 будет считана информация о смежности соответствующих вершин и подана на элемент 33 сравнения. Предположим, что при этом элемент 33 вьщает на своем выходе сигнал несравнения, который устанавливает в исходное состояние регистры |4 и 9, и узлы 20 и 21 , а блок 3 фор- 1мирования перестановок готовит к формированию новой перестановки 2,1,3,4, 5. После этого по каждому тактовому импульсу из блока 7 памяти и из блока 31 вновь считывается информация о смежности соответствующих вершин и поступает для сравнения на элемент 33. Причем, если в регистрах 4 и 9 сдвига по каждому тактовому импульсу на их входах единица всегда последовательно переходит с предыдущего разряда на последующий, то йа коммута торах 5 и 10 единицы появляются на их выходах в последовательности, определяемой перестановкой, сформирован ной блоком 3. Так, сформированная- вторая перестановка 2,1,3,4,5 приводит к тому, что единица с первого выхода регистра 4 проходит на второй выход коммутатора 5 и соответственно на второй вход блока 7 памяти. Единица с второго выхода регистра f проходит на первый выход коммутатора 5, с третьего - на третшЧ, с четвертого- на четвертый и с нятог о - на пятый. Единица с первого выхода регистра 9 проходит на второй выход коммутатора 10. Таким образом, ия блока 7 памяти последовательно считьшаются элементы второй строки матрицы смежности полного пятивершинного графа и сравниваются с первой строкой матрицы смежности пятивepшинt oгo подграфа, выбранного из исследуемого графа блоком 14 формирования сочетаний. Будем считать, что все пять элементов второй строки полного пятивершинного графа и первой строки исследуемого подграфа оказываются равными. Тогда сигнал несравнения на выходе элемента 33 не вырабатывается, и очередной тактовый импульс, появившись на выходе регистра 4, переводит единицу с первого выхода регистра 9 на его второй выход, которая появля-ч ется на первом выходе коммутатора 10, а также единицу с первого выхода узла 21 - на его второй выход.

Таким образом, следующая пятерка тактовых импульсов последовательно считьтает из блока 7 памяти элементы первой строки матрицы смежности,а из блока 31 - элементы второй строки и сравнивает их в элементе 33. Будем считать, что элементы этих строк равные. Тогда очередной тактовый импульс устанавливает единицы в третьих разрядах регистра 9 и узла 21, а очередная пятерка тактовых импульсов поэлементно аналогично описанному сравнивает третьи строки матриц смежности из блока 7 памяти и из блог ка 31 .

Считают, что во всех последующих строках происходит поэлементное сравнение. Тогда по очередному тактовому импульсу на выходе регистра 9 появляется сигнал, свидетельствующий об изоморфизме пятивершинного подграфа выбранного из исследуемого графа блоком 14 формирования сочетаний, и полного пятивершинного графа. Поскольку полный пятивершинный граф неплана- рен, то непланарен и выбранный подг граф. Сигнал изоморфизма с выхода регистра 9 устанавливает в исходное состояние блок 3 формирования перестановок, а в блоке 14 формирования соче36

таний череп элемо.иты rj, i i и .) угг. навливает новое осчг тчиие 1 I I 1010. . .о.

После этого начинай тс я Fioni.n i itpc- цесс определения изом рфии-1а (це.ичо- морфизма) 1ТОЛНОГС1 пяптершинного г ра- фа и выбранного блоком 14 подграфа, состоящего в соответстпии с сочетанием 1111010...О из 1-й, 2-й, 3-й,

4-й и 6-й вершин. Этот процесс протекает аналогично описанному с той лишь разницей, что из-за подачи единиц с выхода коммутатора 19 на 1-ii, 2-й, 3-й, 4-й и 6-й входы узлоп 20 и 21

при последовательной подаче на их синхровходы тактовых импульсов единицы появляются последовательно на 1-м, 2-м, 3-м, 4-м и 6-м выходах, т.е. именно на тех выходах, которые

однозначно соответствуют новому сформированному сочетанию 1I11010...0.

Предположим, что подграф, состоящий из указанных вершин (т.е.1,2,3, 4,6) не изоморфен полному пятивершинному графу. Это означает, что при

каждой перестановке в процессе поэлементного сравнения матриц смежности на выходе элемента 33 появляется сигнал несравнения (неизоморфизма),

который устанавливает каждый раз новую перестановку. Пркчем перебира- ются все перестановки, и сигнал окон чания перебора всех перестановок появляется на выходе блока 3. Этот

сигнал является признаком планарности выбранного с помощью блока 14 пятивершинного подграфа. Этот сигнал через открытый элемент И 29 поступает на первый управляющий вход блока I6

накопления планарных вершин и перепи- сьтает содержимое блока 14 (т.е. 1111010...0) в блок 16, а через время задержки, достаточное для надежной переписи этой информации , добавляет в блок 16 шестую единицу, которая записывается в соседний разряд справа от крайней правой единицы планарной пятерки вершин. Поэтому в блоке I6 после этого записана ин

формация 11110110...0. Причем такая перепись в процессе работы устройства и добавление единицы нужны только при первом появлении сигнала на выходе блока 3, т.е. нужно из блока 14

переписать в блок I6 только первую Планерную пятерку вершин.

Чтобы предотвратить такую перепись при последующих появлениях сигнала на выходе блока 3, задний фронт первого

11

такого сигнала, поступая на единичный вход триггера 28, .переводит его в единичное состояние. При этом закрываютг ся элементы И 29 и 13, а открываются элементы И 30,и 45. Поэтому в дальнейшем смена сочетаний в блоке 14 происходит по сигналу с выхода блока 3, т.е. когда при данном сочетании переберутся все перестановки, но этот сигнал в блок 16 уже не поступает, поскольку элемент И 29 закрыт.

Кроме того, сигнал с выхода блока 3 о нахождении первой планарной пятерки вершин, пройдя-открытый элемент И 29, поступает также через элемент ИЛИ 35, на первый вход группы 15 элементов И. В результате этого от входа 44 в первые четыре разряда блока 14 записьшаются единицы. Пог скольку теперь в блоке 16 находится ненулевая информация, то на выходе элемента И 57 (фиг.2) - нулевой пот тенциал, поэтому единицы снимаются с первых пяти диагональных элементов И-НЕ коммутатора 19. С помощью элементов И 54 и ИЛИ 55 блока 16 происходит выделение единицы старшего разряда, т.е. на первой шине вькодов блока 16 имеют в данном случае уни- тарньш код 00000010...0. Этот код поступает на первые входы узлов 20 и 21 и первые входы элемента ИСКЛЮ- ЧА101ЦЕЕ ИЛИ 56, на вторые входы которых поступает код 11110110...0. Поэтому на левые входы коммутатора I 9 поступает код II11010...О, а на шее-, том выходе дешифратора 1 7 появляет ся единица.

Так как в первые четыре разряда олока 14 записаны единицы, то он последовательно формирует сочетания из 5 по 4. Поскольку на левые входы коммутатора 19 с блока 16 подается код 1111010...О, то единицы первого сочетания 11110...О с выхода блока 16, пройдя через коммутатор 19, ока- зьшаются на первых четырех его выходах. С учетом того, что в семи разрядах узлов 20 и 21 находятся единицы, общее сочетание, поданное на входы узлов 20 и 21 будет 11110010...0.

Теперь при поступлении в схему тактовых импульсов начинается процесс установления планарности подграфа, включающего 1,2,3,4 и 7 вершины. Аналогично описанному сначала при исходной перестановке в блоке 3 (т.е. при перестановке 1,2,3,4,5) по каж-

й итгя а от

е15т в з-,

,

к. .

51703612дому тактовому импульсу происходит поэлементное сравнение матриц смежности для полного пятивершинного графа и исследуемого подграфа, включающего вершины 1,2,3,4,7. Если в какой-то момент времени на выходе элемента 33 вырабатывается сигнал несравнения, т.е. неизоморфизма, то по этому сиг1Q налу блок 3 формирует вторую перестановку 2,1,3,4,5 и начинается новый процесс сравнения матриц смежности.

Предположим, что перебрав все ре15 рестановки, при каждой из них на выходе элемента 33 вырабатывается сигнал несравнения (неизоморфизма). Тогда на выходе блока 3 появляется сигнал окончания перебора всех пере20 становок при данном сочетании. Этот сигнал поступает через открытый элемент И 13 на вход блока 14, который формирует новое сочетание II1010...О, единицы которого проходят на 1, 2,3

25 и 6 выходы коммутатора 19. Однако этот сигнал уже не проходит через элемент И 29 на первый вход блока 16, так как элемент И 29 был открыт для прохождения только первого сигнала

30 с выхода блока 3. Поэтому в блоке 16 Никаких изменений не происходит, а начинается новый процесс установления изоморфизма полного пятивершинного графа и подграфа, включающего 1-ю, 2-ю,3-ю и 7-ю вершины.

Предположим, что и это, и все последующие сочетания пятерок вершин из шести исследуемых 1,2,3,4,6,7 ока- зьшаются неизоморфными полному пяти40 вершинному графу. Тогда сигнал перебора всех перестановок с выхода блока 3 формирует новое сочетание, в данном случае 1110010...О, т.е. единица появляется в 6-м разряде. Но

д5 поскольку на 6-м выходе дешифратора 17 имеется единица, то на входах 6-го элемента И группы 18 происходит совпадение единичных сигналов. Сигнал с выхода 6-го элемента И группы

50 18 через элемент ИЛИ 23 п еребрасьшает триггер 24 в единичное состояние и, задержанный элементом 27 через открытый триггером 24 элемент И 25, поступает на второй вход группы 15 элементе тов И и на входы переключения емкости регистров 4 и 9, блока 3 и вход коммутатора 12. В результате этого по входу 44 от источника единичных сигналов в первые пять разрядов бло35

13

ка 14 эаписьшаются единицы, к ре - гистрам 4 и 9 и блоку 3 подключаются шестые разряды, а коммутатор 12 подключается к выходам блока 8 памяти. Теперь при поступлении тактовых импульсов в схему поэлементно и синхрон но считьшаются из блока 31 матрица смежности исследуемого подграфа, включающего вершины 1,2,3,4,6 и 7, и матрица смежности двудольного шести- вершинного графа из блока 8 памяти. Предположим, что эти графы неизоморфны, т.е. в процессе считывания элемен15

тов матриц смежности и сравнения их элементов на выходе элемента 33 при каждой перестановке вырабатьтается сигнал несравнения. Таким образом, перебираются все перестановки и на выходе блока 3 появляется сигнал окончания перебора всех перестановок. Этот сигнал через элементы 13, 45 и 46 поступает на вход блока 14, в котором формируется новое сочетание I111010...0. Поскольку в этом со четании появилась единица в шестом разряде, то на входах шестого элемента И группы 18 появляются единичные сигналы. Поэтому единичный сигнал с выхода этого элемента И через элемент ИЛИ 23 поступает на счетный вход триггера 24 и перево дит его в нулевое состояние. Этот же сигнал через элемент 27 задержки и открытый элемент И 26 поступает на третий вхо блока 16 и записывает единицу в его 8-й разряд, а также через элемент ИЛИ 35 поступает на первый вход группы 15 элементов И и на входы переключения разрядности регистров 4 и 9, блока 3 и коммутатора 12, В результате этого по входу 44 от источника единичных сигналов в первые четыре разряда блока 14 записываются едини- 4 и 9 и блока 3 от- разряды, коммутатор 7

цы, от регистров

ключаются шестые

12 переключается к выходам блока

памяти.

После этого начинается новый процесс анализа на планарность семивер- шинного подграфа, состоящего из вершин 1,2,3,4,6,7,8 аналогично описанному, т.е. сначала перебираются все сочения по 5 из всех вершин, записанных в блоке 16 (при этом вершина 8 фиксирована,а перебираются только четьфе вершины из планарного подгра- фа, т.е. состоящего из вершин 1,2, 3,4,6,7). Если при этом появляется

15

20

25 170361

хотя бы для одного сочетания сигнал изоморфизма, то 8-я вершина нарушает планарность подграфа и поэтому она , блокируется на выходе блока 16, а новая единица записьшается в 9-й разряд блока 16. Если сигнал изоморфизма не появляется, то схема переходит к формированию всех сочетаний по 6 из 10 всех вершин, записанных в блоке 16. Если и здесь нарушения планарности не обнаружено, то на третий вход блока 16 поступает сигнал планарности, по по которому в 9-й разряд записывается единица, а 8-я вершина не блокируется.

Такой процесс продолжается до тех пор, пока единица не появится на выходе последнего разряда блока 16. Это будет сигналом окончания процесса решения задачи. Номера планарных вершин снимаются с второй группы выходов блока 16.

0

5

5

0

5

0

5

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

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

мн пходами дешифратора, вторая груп па выходов блока накопления пленарных вершин , соединена с первой группой 1П1формационных входов шестого коммутатора, а вторая группа информационных входов соединена с первыми входами соответствующих элементов И второй группы, группой информационных входов шестого коммутатора, группой выходов блока формирования сочетаний первая группа входов которого соединена с входом установки начального состояния устройства, вторая группа вхо дов соединена с выходами соответствующих элементов И первой группы, а счетный вход соединен с выходом одиннадцатого элемента HJDl, первый и второй входы которого соединены соответственно с выходами пятого и шестого элементов И, группа выхода блока формирования перестановок соединена с группами управляющих входов с первого по четвертый KONMyTaTopoB, инфор- папионные выходы первого регистра сдвига соединены с информационными входами первого и второго коммутаторов, информационные выходы второго регистра сдвига соединены с информа- Ц}юнными входами третьего и четвертого :--.оммутаторов, выходы первого и третьего коммутаторов соединены соответственно с первьми и вторыми адресными входами первого блока памяти , информационные вьгходы которого соединены с первыми информационными входами пятого коммутатора, вторые информационные входы которого, соединены с информационными выходами второго блока памяти, первые и вторые адресные входы которого соединены соответственно с выходами второго и четвертого коммутаторов, управляющий вход пятого коммутатора соединен с вторым входом блока формирования перестановок, информационными входами шестого разряда первого и второго регистров сдвига, первыми входами элементов И первой группы и выходом первого элемента II, выходь пятого коммутатора соединены с соответствуюш,ими входами третьего элемента ИЛИ, выход которого соединен с первым входом элемента сравнения, выход которого.соединен с первьми входами шестого, восьмого десятого элементов I-UIH, входом второго элемента задержки, вторым входом шестого элемента И и третьим входом блока формирования перестановок, вхо

, 703616

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

с соединен с первыми входами четвертого и пятого элементов Pi, вторым входом десятого элемента И, первыми входами пятого и шестого элементов ИЛИ и выходом старшего разря-

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

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

20 с входом сдвига второго регистра , сдвига и вторым входом седьмого элемента ИЛИ, выход которого соединен со счетным входом узла последовательного опроса

25 разрядов по горизонтали, вход сброса которого соединен с выходом десятого элемента ИЛИ, информационные выходы шестого коммутатора соединены с вторыми группами выходов узлов

30 последовательного опроса разрядов по вертикали и по горизо}1тали, выходы onpocaiкоторых соедипены соответственно с первым и вторым входами соответствующего элемента ИЛИ группы,

эс выходы которых соединены с соответствующими информационными входами блока задания топологии графа, информационные выходы которого соединены с соответствующими входами второго

40 элемента ИЛИ, выход которого соединен с вторым входом элемента сравнения, выход второго элемента задержки соединен с вторым входом седьмого элемента ИЛИ, выход окончания перебора перед5 становок блока формирования перестановок соединен с первыми входами третьего и шестого элементов И и входом установки в 1 второго триггера, прямой выход которого соединен с вто50 рыми входами шестого и четвертого элементов И, выход которого соединен с вторым входом четвертого элемента ИЛИ и с вторым выходом блока накопления планарных вершин, первый и тре55 тий входы которого соединены соответственно с первым и третьим входами четвертого элемента ИЛИ и выходами третьего и второго элементов И, а четвертый вход блока накопления планар1715

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

К 25,2/

703618

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

0 входами третьего и пятого элементов И, выход окончания решения задачи блока накопления планарных вершин является выходом окончания решения задачи устройства, входы задания то15 пологий блока задания топологии графа являются входами задания тополог ; гии графа устройства, а выход четвертого элемента ИЛИ соединен с вторыми входами элементов И первой группы. 20

t6

Ч/

С/5

I7Z

/

CIS

т

2/

/5I

й ,.

Фиг.З

i:±

2/

С 57 блока. If

Составитель О.Гречухина Редактор О.Юрковецкая Техред Л.Олийнык

Заказ 6391/51

Тираж 668

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарин,-), 101

Корректор Л.Патлй

Подписное