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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы при автоматизированном проектировании электронных схем. Цель изобретения - сокращение аппаратурных затрат. Для этого в устройство, содержащее генератор 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 ил.

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

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

РЕСПУБЛИК

„„SU„„1517036 А 1 (51)4 С 06 Е 15/20

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Оч 3

Ю

С Э

ГОСУДАРСТ8ЕННЦЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР (21) 425о400/24 24 (22) 09.06.87 (46) 23.10.89. Бюл. М 39 (71) Тапанрогский радиотехнический институт им.В.Д.Калмыкова (72) В.М.Глушань, В.М.Курейчик, С,У,Ермаков и А.А.Калмычек (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М - 482751, кл. G 06 F 15/20, 1974.

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

М 1059579, кл. G 06 F 15/20, 1982.

2 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы при автоматизированном проектировании электронных схем. Цель изобретения — сокращение аппаратурных затрат. Для этого в устройство, содержащее генератор 1 тактовых импульсов, ключ 2, блок 3 формирования пере1517036

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

7 и второй 8 блоки памяти, с первого по шестой элементы И 25,26,29,30,13, Изобретение относится к автоматике» вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы при автоматизированном проектирован»и электронных схем.

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

1!а ф»г.1 приведена структурная схема устройства; на фиг.2 — вариант 25 выполнения функциональной схемы блока накопления планарных вершин; на ) иг.3 и 4 — варианты выполнения функциональных схем узлов послеповательного опроса разрядов по вертика— л» » горизонтали соответственно, на фиг.5 — функциональная схема коммута..ора выходов блока формирования сочетан»Й.

Устройство содержит генератор 1

-.актовых импульсов, ключ 2, блок 3 форм»рования перестановок, первый регистр 4 сдвига, первый 5 и второй

6 коммутаторы, первый 7 и второй 8 блоки памяти, второй регистр 9 сдви- 40 га, третий 10, четвертый 11 и пятый !

2 коммутаторы, пятый элемент И 13, блок 14 формирования сочетаний, первую группу 15 элементов И, блок 16 накоплен»я планарных вершин, дешиф- 45 ратор 17, вторую группу 18 элементов И, шестой коммутатор 19, узлы

20 » 2! последовательного опроса раз— рядов по вертикали и по горизонтали, .-ру»пу элементов ИЛИ 22, первый элемент ИЛИ 23, первый триггер 24, первый

25 » второй 26 элементы И, первый элемент 27 задержки, второй триггер

28, третий 29 и четвертый 30 элеменгы И, блок 31 задания топологии гра55 фа, второй элемент ИЛИ 32, элемент

33 с.рав»е»ия, третий 34, четвертый

35, »яты» 36 и шестой 37 элементы

И:П1, второй элемент 38 задержки, 45, блок 16 накопления планарных вершин, вторая группа 18 элементов И, узлы последовательного опроса разрядов по вертикали 20 и по горизонтали 21, группа элементов ИЛИ 22, с первого по одиннадцатый элементы ИЛИ

23,32,34,35,36,37,39,40,41>42,46, первый 27 и второй 38 элементы задержки и элемент 33 сравнения ° 5 ил. седьмой элемент ИЛИ 39, восьмой 40, девятый 41 и десятый 42 элементы

HJIH, общий вход 43 установки исходного состояния устройства, вход 44 сигнала логической "1", шестой элемент И 45 и одиннадцатый элемент

ИЛИ 46.

Каждый разряд блока 16 (фиг.2), кроме первого и двух последних, содержит триггер 47, элемент ЗАПРЕТ 48 э элемент 49 задержки, элементы И 50—

52, триггер 53, элемент И 54, элемент

ИЛИ 55 и элемент ИСКЛ10ЧА!0ЩЕЕ ИЛИ 56.

Первый разряд блока 16 содержит перечисленные элементы за исключением элемента задержки, элемента И 50 и элемента ИЛИ. В предпоследнем разряде отсутствует элемент ИСКЛ!ОЧА!0ЩЕЕ

ИЛИ, а последний разряд содержит триггер 47, элемент 49 задержки и элемент И 50. Кроме того, блок 16 содержит общие на всю схему элементы

И 57, задержки 58 и ИЛИ 59.

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

Каждый разряд узла 21 содержит элементы И 68 и 69, элементы ИЛИ 70

72, триггеры 73 и 74 и инвертор 75.

Коммутатор 1 9 содержит диагональные элементы ИЛИ 76, элементы И—

НЕ 77, элементы ИЛИ 78 и 79.

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

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

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

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

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

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

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

Ром хранится в блоке 7, Первая найденная неизоморфная пятивершинному полносвязному графу, т.е. планарная, пятерка вершин переписывается в блок 16 накопления планарных вершин.

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

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

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

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

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

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

1517036 этого на вход 43 подается сигнал мачальной установки, по которому блок 3 формирования перестановок, регистры 4 и 9 блок 16 накопления плаЭ

5 нарных вершин, узел 20 и триггеры 24 и 28 устанавливаются в нулевое сост тояние, а в первый разряд узла 21 записывается единица. По этому же сиг-. налу в певвые пять разрядов блока 14 IQ формирования сочетаний заносятся единицы, что соответствует исходному сочетанию 111110. ° ° О. По соответствующим входам в блок 31 задания топологии графа заносится информация 11 о топологии исследуемого графа. После этого замыкается ключ 2, и тактовые импульсы начинают поступать на схему.

Поскольку до тех пор, пока в блок 16 не перепишется первая пятерка планар- 20 ных вершин, он находится в нулевом состоянии, то единичный сигнал этого состояния подключает к выходным элементам ИЛИ коммутатора 1 9 все диагональные элементы И-НЕ 77, Поэтому 25 единичные сигналы с первых пяти разрядов блока 14 формирования сочеганий, поступая на первые пять нижних входов коммутатора 19, проходят на первые пять верхних его выходов 30 н поступают на первые пять входов .узла 20. Блок 3 формирования перестановок в исходном состоянии, т.е. при нулевой перестановке, при поступлении на него тактовых импульсов выдает еди-35 ничные сигналы последовательно на выходах: 1,2,3,4,5 °

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

3, в регистре 4 и в узле 20 вторые их выходы. При этом единичный сигнал

< первого выхода узла 21 через первый (верхний) элемент ИЛИ 22 поступает па первый (верхний) вход блока 31, а с второго выхода узла 20 через второй элемент ИЛИ 22 — на второй вход блока 31. Если вершины, соответствующие первому и второму входам блока 31, связаны, то на одном из его выходов появляется единичный сигнал. Одновременно с этим из блока 7 памяти считывается единица (так как в полном пятивершинном графе все вершины связаны), которая через коммутатор 12 и элемент ИЛИ 34 поступает на элемент

33 сравнения. Поэтому элемент 33 сравнения на своем выходе сигнал не вырабатывает. Если первая и вторая вершины исследуемого графа оказываются несвязанными, то на выходе элемента

HJIH 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 фор мирования перестановок готовит к форированию новой перестановки 2,1,3,4, 5. После этого по каждому тактовому импульсу из блока 7 памяти и из блока 31 вновь считывается информация о смежности соответствующих вершин и поступает для сравнения на элемент 33.

Причем, если в регистрах 4 и 9 сдвига по каждому тактовому импульсу на их входах единица всегда последо= вательно переходит с предыдущего разряда на последующий, то йа коммутаторах 5 и 10 единицы появляются на их выходах в последовательности, определяемой перестановкой, сформирован» ной блоком 3. Так, сформированная . вторая перестановка 2,1,3,4,5 приводит к тому, что единица с первого выхода регистра 4 проходит на второй выход коммутатора 5 и соответственно на второй вход блока 7 памяти. Еди9 1г170 ница с второго выхода регистра 4 проходит на иерный выход коммутатора 5

) с третьего — на третий, с четвертого на четвертый и с пятого — на пятый, Единица с первого выхода регистра 9

5 проходит на второй выход коммутатора

10. Таким образом, из блока 7 памяти последовательно считываются элементы второй строки матрицы смежности полного пятивершинного графа и сравниваются с первой строкой матрицы смежности пятинершинного иодграфа> выбранного из исследуемого графа блоком 14 формирования сочетаний. Будем считать, что нсе пять элементов второй строки полного иятивершинного графа и первой строки исследуемого иодграфа оказываются равными. Тогда сигнал несравнения на выходе элемента 33 не вырабатывается, и очередной тактовый импульс, появившись на выходе регистра 4, переводит единицу с первого выхода регистра 9 на его второй выход, которая иоявля-i 25 ется на первом выходе коммутатора IO, а также единицу с первого выхода узла 21 — на его второй выход.

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

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

После этого начиня» тс я вонь О и И<— цесс определения изом рфи мз (иеи и в морфизма ) полного и ятине ршинного гри-фа и выбранного блоком 14 иодграфа, состоящего в соответствии с сочетанием 1111010 ° ..0 из I-й, 2-й, 3-й, 4-й и 6-й вершин. Этот процесс иротгкает аналогично описанному с той лгпи. разницей, что иэ-за подачи единиц с ныхода коммутатора 19 на I -й, 2-й, 3-й, 4-й и 6-й входы узлов 20 и 21 при последовательной подаче на их синхровходы тактовых импульсов единицы появляются последовательно на

l-м, 2-м, З-м, 4-м и 6-м выходах, т,е, именно на тех выходах, которые однозначно соответствуют новому сформированному сочетанию 1111010...0.

Предположим, что иодграф, состоящий из указанных вершин (т.е.l,2,3, 4,6) не изоморфен полному иятивершинному графу. Это означает, что при каждой перестановке в процессе иоэлементного сравнения матриц смежности на выходе элемента 33 появляется сигнал. несравнения (неизоморфизма), который устанавливает каждый раэ ноную перестановку. Причем перебира:ются все перестановки, и сигнал окон» чания перебора всех перестановок появляется на выходе блока 3. Этот сигнал является признаком илаиарности выбранного с помощью блока 14 пятивершинного подграфа. Этот сигнал через открытый элемент И 29 поступает на первый управляющий вход блока 16 накопления планарных вершин и переписывает содержимое блока 14 (т.е.

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

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

3, т.е. когда при данном сочетании переберутся все перестановки, но этот Ið сигнал в блок 16 уже не поступает, поскольку элемент И 29 закрыт.

Кроме того, сигнал с выхода блока 3 о нахождении первой планарной пятерки вершин, пройдя открытый элемент И 29, поступает также через элеO мент ИЛИ 35, на первый вход группы 15 элементов И, В результате этого от входа 44 в первые четыре разряда блока 14 записываются единицы. По-. 20 скольку теперь в блоке 16 находится ненулевая информация, то на выходе элемента И 57 (фиг,2) — нулевой по-, тенциал, поэтому единицы снимаются с первых пяти диагональных элементов 25

И-НЕ коммутатора 19, С помощью элементов И 54 и ИЛИ 55 блока 16 происходит выделение единицы старшего разряда, т,е. на первой шине выходов блока 16 имеют в данном случае уни- 30 тарный код 00000010...0, Этот код поступает на первые входы узлов 20 и 21 и первые входы элемента HCKJIIOЧА10ЩЕЕ ИЛИ 56, на вторые входы которых поступает код 11110110...0. Поэтому на левые входы коммутатора 19 поступает код 1111010...0, а на шес-, том выходе дешифратора 17 появляет ся единица.

Так как в первые четыре разряда 40 блока 14 записаны единицы, то он последовательно формирует сочетания из

5 по 4. Поскольку на левые входы коммутатора 19 с блока 16 подается код 1111010...0, то единицы первого 45 сочетания 11110...0 с выхода блока

16, пройдя через коммутатор 19, оказываются на первых четырех его выходах. С учетом того, что в семи разрядах узлов 20 и 21 находятся единицы, общее сочетание, поданное на входы узлов 20 и 21 будет 11110010...0.

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

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

33 вырабатывается сигнал несравнения, т,е, неизоморфизма, то по этому сигналу блок 3 формирует вторую перестановку 2,1,3,4,5 и начинается новый процесс сравнения матриц смежности, Предположим, что перебрав все перестановки, при каждой из них на выходе элемента 33 вырабатывается сигнал несравнения (неизоморфизма).

Тогда на выходе блока 3 появляется сигнал окончания перебора всех перестановок при данном сочетании. Этот сигнал поступает через открытый элемент И 13 на вход блока 14, который формирует новое сочетание 111010...0, единицы которого проходят на 1, 2,3 и 6 выходы коммутатора 19. Однако этот сигнал уже не проходит через элемент И 29 на первый вход блока 16, так как элемент И 29 был открыт .для прохождения только первого сигнала с выхода блока 3. Поэтому в блоке 16 никаких изменений не происходит, а начинается новый процесс установления изоморфизма полного пятивершинного графа и подграфа, включающего l-ю, 2-ю,3-ю и 7-ю вершины.

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

17 имеется единица, то на входах

6-го элемента И группы 18 происходит совпадение единичных сигналов. Сигнал с выхода 6-го элемента И группы

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

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

Такой процесс продолжается до тех пор, пока единица не появится на выходе последнего разряда блока 16 °

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

Устройство для исследования графов, содержащее блок задания тополог ии графа, блок формирования перестановок, дешифратор, блок формирования сочетаний, ключ, первый и второй триггеры, первую группу элементов И и генератор .тактовых импульсов, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит первый и второй регистры сдвига, с первого по шестой коммутаторы, первый и второй блоки памяти, с первого по шестой элементы И, блок накопления планарных вершин, вторую группу элементов И, узлы последовательного опроса разрядов по вертикали и по горизонтали, группу элементов ИЛИ, с первого по одиннадцатый элементы ИЛИ, первый и второй элементы задержки, элемент сравнения, выход генератора тактовых импульсов соединен с входом ключа, выход которого соединен с первым входом блока формирования перестановок, входом сдвига первого регистра сдвига и входом синхронизации узла последовательного опроса разрядов по вертикали, первая группа входов которого соединена с первой группой входов узла последовательного опроса разрядов по горизонтали и третьей группой выходов блока накопления планарных вершин, первая группа адьо;адов которого соединена с соответстяующи13 l 5l 70 ка 14 записываются единицы, к ре гистрам 4 и 9 и блоку 3 подключаются шестые разряды, а коммутатор 12 подключается к выходам блока 8 памяти.

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

Предположим, что эти графы неизоморфны, т.е ° в процессе считывания элементов матриц смежности и сравнения их элементов на выходе элемента 33 при каждой перестановке вырабатывается сигнал несравнения. Таким образом, перебираются все перестановки и ня выходе блока 3 появляется сигнал 20 окончания перебора всех перестановок. Этот сигнал через элементы 13, 45 и 46 поступает на вход блока 14, в котором формируется новое сочетание 1111010...0. Поскольку в этом со- 25 четании появилась единица в шестом разряде, то на входах шестого элемента И группы 18 появляются единич-. ные сигналы. Поэтому единичный сигнал с выхода этого элемента И через элемент ИЛИ 23 поступает на счетный вход триггера 24 и переводит его в нулевое состояние. Этот же сигнал через элемент 27 задержки и открытый элемент И 26 поступает на третий вход блока 16 и записывает единицу в его

8-й разряд, а также через элемент

ИЛИ 35 поступает на первый вход группы 15 элементов И и на входы переключения разрядности регистров 4 и 9, 40 блока 3 и коммутатора 1 2. В результате этого по входу 44 от источника единичных сигналов в первые четыре разряда блока 14 записываются единицы, от регистров 4 и 9 и блока 3 отключаются шестые разряды, коммутатор

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

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

ist>os ми входами дешифратора, вторая группа вьгходов блока накопления планарных вершин, соединена с первой группой гп111ормационных входов шестого комму1

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

Выходов блока формирования сочетаний, первая группа входов которого соединена с входом установки начального состояния устройства, вторая группа вхо. дов соединена с Выходами соответствующих элементов И первой группы,а счетный вход соединен с выходом одиннадцатого элемента ИГПИ, первый и второй входы которого соединены соответственно с выходами пятого и шестого 20 элементов И, группа выхода блока формирования перестановок соединена с группами управляющих входов с первого Во четвертый коммутаторов, инфор..апионные выходы первого регистра 25 сдвига соединены с информациогпгыми входами первого и второго коммутаторов, информационные выходы второго регистра сдвига соединены с информацггонными входами третьего и четвер- gp того коммутаторов, выходы первого и третьего коммутаторов соединень1 соотВетственно с первыми и вторыми адреснымп Входами первого блока памяти, информационные Выходы которого соедипены с первыми информационными входами пятого коммутатора, вторые информационные входы которого. соединены с информационными Выходами второго блока памяти, первые и вторь!е адрес- 4О ные входы которого соединены соответственно с выходами второго и четвертого коьс1утаторов, управляющий вход пятого коммутатора соединен с вторым входом блока формирования перестано- 45 вок, информационными входами шестого разряда первого и второго регистров сдвига, первыми входами элементов И первой группы и выходом первого элемента И, выходы пятого коммутатора 5р соединены с соответствующими входами третьего элемента ИЛИ, выход которого соединен с первым входом элемента сравнения, выход которого. соединен с перпь 111 ВХОдами шестОГО ВОсьмОГО 55 десятого элементов ИЛИ, входом второго элемента задержки, вторым входом шестого элемента И и третьим входом блока формирования перестановок, вхо- . ды установки в исходное состояние которого соединены с выходом девятого элемента И, первый вход которого соединен с первыми входами четвертого и пятого элементов И, вторым входом десятого элемента И, первыми входами пятого и шестого элементов ИЛИ и выходом старшего разряда второго регистра сдвига, вход установки в начальное состояние которого соединен с входом установки в начальное состояние первого регистра сдвига и выходом восьмого элемента

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

ИЛИ и с вторым выходом блока накопления планарных BppU!HH, первый и третий входы которого соединены соответственно с первым и третьим входами четвертого элемента ИЛИ и выходами третьего и второго элементов И, а четвертьгй вход блока накопления планар36 18 динены с выходами соответствующих элементов И второй группы, вторые входы которых соединены с соответствующими выходами дешифратора, выход нулевого состояния блока накопления планарных вершин соединен с управляющим входом шестого коммутатора, инверсный выход второго триггера соединен с вторыми входами третьего и пятого элементов

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

17 15170 ных вершин соединен с входом сброса второго триггера, с вторыми входами,, пятого и шестого элементов ИЛИ

Э третьим входом седьмого элемента ИЛИ и входом установки начального состоя5

Ф ния устройства,. выход шестого элемента ИЛИ соединен с входом синхрониз а ции узла по следо в а тель íî ro оп ро с а разрядов по вертикали, выход пятого 10 элемента ИЛИ соединен с входом сброса первого триггера, прямой и инверсный выходы которого соединены с первыми входами первого и второго элементов И соответственно, вторые 15 входы которых соединены с выходом первого элемента задержки, вход которого соединен с входом синхронизации первого триггера и выходом пер— вого элемента ИЛИ, входы которого сое-20

/(19

Фие . 2

l517036 к 72

Фиг. У к 22! 517036

С $7 блока/в с)Ч

Фие 5

Составитель О.Гречухина

Редактор О,Юрковецкая Техред Л.Олийнык Корректор J1.11à Tÿé

Заказ 6391/51 -Тираж 668 Подписное

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

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

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