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

,1 1 9) 51)4 С 06 Е 15 ГОСУДАРСТ 8 ЕННЦЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР НИЕ ИЗОБРЕТЕНИ АВТОРСКОМУ С 8 ИДЕТЕЛВСТ РОЙСТВО ДЛ НИЯ ГР 24 ФОВ(57) Изтике ижет бызадачи 89. Бюл, М огский рад .В.Д.Калмь ушань, В.М и А.А.Калм 5 (088.8) кое свидет л. С 06 Е иотехническии ов Ку ик ) о СССР 1974. СССР 1982(56) Авторс 11 482751, к Авторско М 1059579, обретение относится к автомавычислительной технике и моть использовано для решениявыделения планарной части при автоматизированном проектини электронных схем. Цель изобия - сокращение аппаратурных т. Для этого в устройство, сощее генератор 1 тактовых импульключ 2, блок 3 формирования пере517036 С Ю 7 блока/К С /ЧФие 5 Составитель О.ГречухинаРедактор О,Юрковецкая Техред Л.Олийнык Корректор Л,11 атай Заказ 6391/51 Тираж 668 Подписное Производственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина,101 ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д, 4/51517036 51 П становок, блок 4 формирования сочетаний, группу 15 эЛементов И, дешифратор 17, первый 24 и второй 28 триггеры, блок 31 задания топологии графа, введены первый 4 и второй 9 регистры сдвига, с первого по шестойкоммутаторы 5,6,10,11,12,19, первый7 и второй 8 блоки памяти, с первогоцо шестой элементы И 25,26,29,30,13,Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения заддчц выделения планарной части схемы прц автомдтизированном проектировании электронных схем.Целью изобретения является сокращение аппаратурных затрат.Па фцг.1 приведена структурная схема устройства; на фиг,2 - вариант 25 выполнения функциональной схемы блока накопления планарных вершин; на фиг.3 и 4 - варианты выполнения функциональных схем узлов последовательного опроса разрядов по вертикали и горизонтали соответственно; на Фиг.5 - функциональная схема коммутаора выходов блока формирования сочетд 1 цц,Устройство содержит генератор 1-.актовых импульсов, ключ 2, блок 3формирования перестановок, первый регистр 4 сдвига, первый 5 и второй6 коммутаторы, первый 7 и второй 8блоки памяти, второй регистр 9 сдвигд, третий 1 О, четвертый 11 и пятый12 коммутдторы, пятый элемент И 13,блок 14 формирования сочетаний, первую группу 15 элементов И, блок 16цдкоцлецця плдцарцых вершин, дешифрдтор 17, вторую группу 18 элемоцтоы И, шестой коммутатор 19, узлы20 ц 21 последовательного опроса разрядов по вертикали и по горизонталигруцпу элементов ИЛИ 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,4142,46,первый 27 и второй 38 элементы задержки и элемент 33 сравнения5 ил. седьмой элемент ИЛИ 39, восьмой 40,девятый 41 и десятый 42 элементый 1 И, общий вход 43 установки исходного состояния устройства, вход 44сигнала логической "1", шестой элемент И 45 и одиннадцатый элементИЛИ 46,Каждый разряд блока 16 фиг.2),кроме первого и двух последних, содержит триггер 47, элемент ЗАПРЕТ 48ээлемент 49 задержки, элементы И 50 -52, триггер 53, элемент И 54, элементИЛИ 55 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 56.Первый разряд блока 16 содержит перечисленные элементы за исключениемэлемента задержки, элемента И 50 иэлемента ИЛИ. В предпоследнем разряде отсутствует элемент ИСКЛ 10 ЧАЮЩЕЕИЛИ, а последний разряд содержит триггер 47, элемент 49 задержки и элемент И 50. Кроме того, блок 16 содержит общие на всю схему элементыИ 57, задержки 58 и ИЛИ 59.Каждый разряд узла 20 содержитэлементы И 60 и 61, инвертор 62,элементы ИЛИ 63 и 64, триггеры 65и 66 и элемент ИЛИ 67.Каждый разряд узла 21 содержитэлементы И 68 и 69, элементы ИЛИ 7072, триггеры 73 и 74 и ицвертор 75.Коммутатор 1 9 содержит диагональные элементы ИЛИ 76, элементы ИНЕ 77, элементы ИЛИ 78 и 79.Принцип работы устройства основанна использовании теоремы ПонтрягинаКуратовского, которая формулируетсяследующим образом, Граф являетсяплоским тогда и только тогда, когдаон не содержит подграфа, изоморфногос точностью до вершин степени дваодному из графов Понтрягина-Куратовского. Из теоремы следует, что дляопределения планарности графа из него необходимо последовательно выби5 15170 рать всевозможные сочетания пяти- и .шестивершинных подграфов.и сравнивать их на изоморфизм с,полносвязным, пятивершинным и двудольным шестивершинным (граф Кенига) графами соответ 5 ственно.Для органиэации выбора из исследуемого графа пяти- и шести вершинных подграфов использован формирователь сочетаний булевых переменных с определенной закономерностью перехода от одного сочетания к другому, А для определения изоморфизма выбираемых пяти- и шестивершинных под графов с полносвязанным пятивершинным и двудольным шестивершинным графами предлагается испольэовать проце/дуру полного перебора с помощью формирования перестановок булевых пере менных (т.е.выдача перестановок осуществляется в пространственно-временной форме)В общем случае задача определения изоморфизма графов имеет экспоненциальную временную слож ность . Однако в данном случае исследованию на изоморфизм подвергаются только пяти- и шестивершинные графы, т.е, графы малой размерности.Дпя того, чтобы одновременно с исследованием графа на плднарность можно было выделять и его максимально планарную часть, используется такой формирователь последовательности сочетаний, сочетания на выходе которо 35 го представляют лексикографическую последовательность булевых пеоеменных. При этом под лексикографической последовательностью сочетаний булеВых пепеменных понимается такая В 40 которой сочетания позиционно упорядочены по возрастанию.Устройство работает следующим образом.Блоком 14 формирования сочетаний 45 генерируется лекситографическая по следовательность сочетаний булевых переменных, Каждое такое сочетание выбирает из блока 31 задания топологии графа с помощью коммутатора 19 и уз лов 20 и 21 соответствующую пятерку вершин. С помощью блока 3 формирования перестановок, регистров 4 и 9 сдвига, блоков 7 и 8 памяти, коммутаторов 5,6 и 10 - 12 и элемента 33 сравнения выполняется процедура про- верки на изоморфнзм выбранной пятерки вершин и полносвязного пяти- вершинного графа, информация о кото 36 6Ром хранится в блоке 7. Первая найденная неизоморфная пятивершинномуполносвязному графу, т.е. планарная,пятерка вершин переписывается вблок 16 накопления планарных вершин.Затем туда же добавляется новая вершина, и начинается процесс переборасочетаний, т.епятерки сочетаний ужевыбираются не из всего заданногомножества вершин исследуемого графа,а только иэ множества вершин помеченных единицами в блоке 16.При каждом таком сочетании выполняется процедура контроля на изоморфизм, Если изоморфизм полному пятивершинному графу ни одной из всехпятерок сонетаннй не обнаруживается,то осуществляется проверка на изоморфизм шестивершинного подграфа, вершины которого занесены в блок 16, идвудольного шестивершинного, информацияо котором хранится в блоке 8.Если и теперь изоморфизм не обнаруживается, то это означает, что выбранная шестерка вершин планарна. Поэтому дописанная к первоначальной .пятерке вершин в блок 16 шестая вершина блокироваться в нем не будети к этой шестерке вершин добавится новая седьмая вершина. В противном случае она заблокируетсяи кпервоначальной пятерке вершин выбирается новая шестая вершина,Добавление каждой новой вершиныв множество планарных вершин осуществляется только после проверки наизоморфизм всех сочетаний пятероквершин и всех сочетаний шестероквершин и при условии, что изоморфизмобнаружен не был.Использование формирователя лексикографической последовательности сочетаний позволяет исключить повторяющиеся сочетания.Для этого после добавления новой вершины в сочетаниявключается эта новая вершина и четыревершины или пять вершин из планарного множества вершин при формированиисоответствующих сочетаний.Для реализации приведенных положений в предлагаемом устройстве используется блок формирования лексикографической последовательности сочетаний,а также коммутатор 19 и узлы последовательного опроса разрешенных разрядов сочетаний.Перед пуском устройства осуществляется подготовка его к работе. 1 ляэтого на вход 43 подается сигналщачальной установки, по которомублок 3 формирования перестановок, регистры 4 и 9 блок 16 накопления плаЭ5нарных вершин, узел 20 и триггеры 24и 28 устанавливаются в нулевое состтояние, а в первый разряд узла 21 записывается единица. По этому же сиг-.налу в пеовые пять разрядов блока 14 10формирования сочетаний заносятсяединицы, что соответствует исходному сочетанию 111110О. По соответствующим входам в блок 31 заданиятопологии графа заносится информация 15о топологии исследуемого графа. Послеэтого замыкается ключ 2, и тактовыеимпульсы начинают поступать на схему.Поскольку до тех пор, пока в блок 16не перепишется первая пятерка планарных вершин, он находится в нулевомсостоянии, то единичный сигнал этогосостояния подключает к выходным элементам ИЛИ коммутатора 1 9 все диагональные элементы И-НЕ 77, Поэтому 25единичные сигналы с первых пятиразрядов блока 14 формирования сочеганий, поступая на первые пять нижних входов коммутатора 19, проходятна первые пять верхних его выходов 30н поступают на первые пять входовузла 20, Блок 3 формирования перестановок в исходном состоянии, т.е, принулевой перестановке, при поступлениина него тактовых импульсов выдает еди ничные сигналы последовательно на выходах: 1,2,3,4,5,Таким образом, по первому тактовому импульсу в блоке 3, в регистре 4 ив узле 20 возбуждаются их первые рязряды (т.е. единичные сигналы появляют-я на их первых разрядах). При этомни из блока 7 памяти, .ни из блока 31считывание информации не происходит,так как информация о связности двухвершин мОжет появиться только приодновременном их возбуждении. Второйтактовый импульс возбуждает в блоке3, в регистре 4 и в узле 20 вторыеих выходы. При этом единичный сигналпервого выхода узла 21 через первый(верхний) элемент ИЛИ 22 поступаетпа первый (верхний) вход блока 31,а с второго выхода узла 20 через второй элемент ИЛИ 22 - на второй входблока 31. Если вершины, соответствующие первому и второму входам блока 31,связаны, то на одном из его выходовпоявляется единичный сигнал, Одновременно с этим из блока 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 формирования перестановок готовит к форированию новой перестановки 2,1,3,4, 5. После этого по каждому тактовому импульсу из блока 7 памяти и из блока 31 вновь считывается информация о смежности соответствующих вершин и поступает для сравнения на элемент 33. Причем, если в регистрах 4 и 9 сдвига по каждому тактовому импульсу на их входах единица всегда последо= вательно переходит с предыдущего разряда на последующий, то йа коммутаторах 5 и 1 О единицы появляются на их выходах в последовательности, определяемой перестановкой, сформирован ной блоком 3. Так, сформированная вторая перестановка 2,1,3,4,5 приводит к тому, что единица с первого выхода регистра 4 проходит на второй выход коммутатора 5 и соответственно на второй вход блока 7 памяти. Еди9 1 г 170ница с второго выхода регцстрд 4 проходит на перный выход коммутатора 5)с третьего - нд третий с четвертогона четвертый и с пятого - на пятый,Единица с первого выхода регистра 95проходит на второй выход коммутатора1 О. Таким образом, из блока 7 памятипоследовательно считываются элементывторой строки матрицы смежности полного пятивершинного графа и сравниваются с первой строкой матрицы смежности пятинершиццого подграфа выбранного из исследуемогографа блоком 4 Формирования сочетаний. Будем считать, что нсе пятьэлементов второй строки полного пятивершинного графа и первой строки исследуемого подграфа оказываются равными. Тогда сигнал несрдвцения на выходе элемента 33 не вырабатывается,и очередной тактовый импульс, появившись на выходе регистра 4, переводитединицу с первого выхода регистра 9на его второй выход, которая появляется на первом выходе коммутатора 10,а также единицу с первого выходаузла 21 - на его второй выход,Таким образом, следующая пятеркатактовых импульсов последовательно 30считывает из блока 7 памяти элементы первой строки матрицы смежности,а из блока 31 - элементы второй строки и сравнивает их в элементе 33. Будем считать, что элементы этих строкравные. Тогда очередной тактовыйимпульс устанавливает единицы в третьих разрядах регистра 9 и узла 21,а очередная пятерка тактовых импульсов поэлементно аналогично описанному сравнивает третьи строки матриц смежности из блока 7 памяти и из блог:ка 31. Считают, что во всех последующих 45 строках происходит поэлементное сравнение. Тогда по очередному тактовому импульсу на выходе регистра 9 появляется сигнал свидетельствующий об изоморфизме пятивершинного подграфа выбранного из исследуемого графа блоком 14 формирования сочетаний, и полного пятивершинного графа. Поскольку полный пятивершинный граф непланарен, то непланарен и выбранный под-. граф. Сигнал изоморфизма с выхода регистра 9 устанавливает в исходное состояние блок 3 формирования перестановок, а в блоке 14 формирования соче 36 Отдций чере элементы 13,46 ц . ус гд.цднливает новое осчетдцце 111 О 00.После этого цдчццдето я и гй ци -цесс определения изом 1 рфи гмд ( цен и -морфизмд) полного пятинершцццого грд.фа и выбранного блоком 14 подгрдфд,состоящего в соответствии с сочетднием 1111010О из -й 2-й, З-й,4-й и 6-й вершин. Этот процесс цротгкает аналогично описанному с той липвразницей, что иэ-зд подачи единиц сныхода коммутатора 19 ца 1-й, 2-й,З-й, 4-й и 6-й входы узлов 20 и 21при последовательной поддче цд ихсинхровходы тактовых импульсов единицы появляются последовательно ца1-м, 2-м, З-м, 4-м и 6-м выходахт,е, именно нд тех выходах, которыеоднозначно соответствуют новому сформированному сочетанию 11110100.Предположим, что подгрдф, состоящий из указанных вершин (т.е.1,2,3,4,6) не изоморфен цолцому пятивершинному графу. Это озндчдет, что прикаждой перестановке в процессе поэлементного сравнения мдтриц смежностина выходе элемента 33 появляетсясигнал. несрдвнения (неизоморфцзмд),который устанавливает кдждый раэноную перестановку. ричем перебираются все перестановки, и сигнал окончания перебора всех перестановокпоявляется на выходе блока 3. Этотсигнал является призцдком плдцдрцостивыбранного с помощью блокд 14 пятивершинного подгрдфа. Этот сигнал через открытый элемент И 29 поступаетна первый управляющий вход блока 16накопления планарных вершин и переписывает содержимое блока 14 (т.е.11110100) в блок 16, д черезвремя задержки, достаточное для надежной переписи этой информации, добавляет в блок 16 шестую единицу,которая записывается в соседний разряд справа от крайней правой единицы планарной пятерки вершин. Поэтомув блоке 6 после этого записана информация 11110100. Причем такаяперепись в процессе работы устройства и добавление единицы нужны толькопри первом появлении сигнала на выходе блока 3, т,е. нужно из блока 14переписать в блок 16 только первуюпланарную пятерку вершин,Чтобы предотвратить такую переписьпри последующих появлениях сигнала навыходе блока 3, задний фронт первого36 12 15170 такого сигнала, поступая на единичный вход триггера 28 переводит его в единичное состояние. При этом закрывают- ся элементы И 29 и 13, а открываются элементы И 30,и 45. Поэтому в даль 5 нейшем смена сочетаний в блоке 14 происходит по сигналу с выхода блока 3, т.е. когда при данном сочетании переберутся все перестановки, но этот 10 сигнал в блок 16 уже не поступает, поскольку элемент И 29 закрыт.Кроме того, сигнал с выхода блока 3 о нахождении первой планарной пятерки вершин, пройдя открытый элемент И 29, поступает также через элеЮмент ИЛИ 35, на первый вход группы 15 элементов И, В результате этого от входа 44 в первые четыре разряда блока 14 записываются единицы. По-, 20 скольку теперь в блоке 16 находится ненулевая информация, то на выходе элемента И 57 (фиг,2) - нулевой пот тенциал, поэтому единицы снимаются с первых пяти диагональных элементов 25 И-НЕ коммутатора 19, С помощью элементов И 54 и ИЛИ 55 блока 16 происходит выделение единицы старшего разряда, т,е. на первой шине выходов блока 16 имеют в данном случае уни тарный код 000000100, Этот код поступает на первые входы узлов 20 и 21 и первые входы элемента ИСКЛЮЧАОЕЕ ИЛИ 56, на вторые входы которых поступает код 111101100. Поэтому на левые входы коммутатора 19поступает код 11110100, а на шес-, том выходе дешифратора 17 появляет,ся единица.Так как в первые четыре разряда 40 блока 14 записаны единицы, то он последовательно формирует сочетания из .5 по 4. Поскольку на левые входы коммутатора 19 с блока 16 подается код 11110100, то единицы пеРвого 45 сочетания 111100 с выхода блока 16, пройдя через коммутатор 19, оказываются на первых четырех его выходах. С учетом того, что в семи разрядах узлов 20 и 21 находятся единицы, общее сочетание, поданное на входы узлов 20 и 21 будет 111100100.Теперь при поступлении в схему тактовых импульсов начинается процесс установления планарности подграфа включающего 1,2,3,4 и 7 вершины. Аналогично описанному сначала при исходной перестановке в блоке 3 (т.е, при перестановке 1,2,3,4,5) по каждому тактовому импульсу происходитпоэлементное сравнение матриц смежности для полного пятивершинного графаи исследуемого подграфа, включающеговершины 1,2,3,4,7. Если в какой-томомент времени на выходе элемента33 вырабатывается сигнал несравнения,т,е, неизоморфизма, то по этому сигналу блок 3 формирует вторую перестановку 2,1,3,4,5 и начинается новый процесс сравнения матриц смежности,Предположим, что перебрав все перестановки, при каждой из них на выходе элемента 33 вырабатываетсясигнал несравнения (неизоморфизма).Тогда на выходе блока 3 появляетсясигнал окончания перебора всех перестановок при данном сочетании. Этотсигнал поступает через открытый элемент И 13 на вход блока 14, которыйформирует новое сочетание 1110100,единицы которого проходят на 1, 2,3и 6 выходы коммутатора 19. Однакоэтот сигнал уже не проходит черезэлемент И 29 на первый вход блока 16,так как элемент И 29 был открыт .дляпрохождения только первого сигналас выхода блока 3. Поэтому в блоке 16никаких изменений не происходит, а начинается новый процесс установленияизоморфизма полного пятивершинногографа и подграфа, включающего 1-ю,2-ю,З-ю и 7-ю вершины.Предположим, что и это, и все последующие сочетания пятерок вершин изшести исследуемых 1,2,3,4,6,7 оказываются неизоморфными полному пятивершинному графу. Тогда сигнал перебора всех перестановок с выхода блока 3 формирует новое сочетание, вданном случае 11100100, т,е. единица появляется в 6-м разряде. Нопоскольку на 6-м выходе дешифратора17 имеется единица, то на входах6-го элемента И группы 18 происходитсовпадение единичных сигналов. Сигнал с выхода 6-го элемента И группы18 через элемент ИЛИ 23 перебрасываеттриггер 24 в единичное состояние и,задержанный элементом 27 через открытый триггером 24 элемент И 25, поступает на второй вход группы 15 элементов И и на входы переключения емкости регистров 4 и 9, блока 3 и входкоммутатора 12, В результате этогопо входу 44 от источника единичныхсигналов в первые пять разрядов бло36 4хотя бы для одного сочетания сигнал изоморфизма, то 8-я вершина нарушает планарность подграфа и поэтому она блокируется на выходе блока 16, а новая единица записьвается в 9-й разряд блока 16. Если сигнал изоморфизма не появляется, то схема переходит к формированию всех сочетаний по 6 из всех вершин, записанных в блоке 16. Если и здесь нарушения планарности не обнаружено, то на третий вход блока 16 поступает сигнал планарности, по по которому в 9-йразряд записывается единица, а 8-я вершина не блокируется.Такой процесс продолжается до тех пор, пока единица не появится на выходе последнего разряда блока 16Это будет сигналом окончания процесса решения задачи. Номера планарных вершин снимаются с второй группы выходов блока 16. Формула изобретенияУстройство для исследования графов, содержащее блок задания топологии графа, блок формирования перестановок, дешифратор, блок формирования сочетаний, ключ, первый и второй триггеры, первую группу элементов И и генератор .тактовых импульсов, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит первый и второй регистры сдвига, с первого по шестой коммутаторы, первый и второй блоки памяти, с первого по шестой элементы И, блок накопления планарных вершин, вторую группу элементов И узлы последовательного опроса разрядов по вертикали и по горизонтали, группу элементов ИЛИ, с первого по одиннадцатый элементы ИЛИ, первый и второй элементы задержки, элемент сравнения, выход генератора тактовых импульсов соединен с входом ключа, выход которого соединен с первым входом блока формирования перестановок, входом сдвига первого регистра сдвига и входом синхронизации узла последовательного опроса разрядов по вертикали, первая группа входов которого соединена с первой группой входов узла последовательного опроса разрядов по горизонтали и третьей группой выходов блока накопления планярных вершин, первая группа яо;адов которого соединена с соответстиующи 13 15170ка 14 записьваются единицы, к регистрам 4 и 9 и блоку 3 подключаютсяшестые разряды, а коммутатор 2 подключается к выходам блока 8 памяти.Теперь при поступлении тактовых импульсов в схему поэлементно и синхронно считываются из блока 31 матрицасмежности исследуемого подграфа,включающего вершины 1,2,3,4,6 и 7, иматрица смежности двудольного шестивершинного графа из блока 8 памяти.Предположим, что эти графы неизоморфны, т.ев процессе считывания элемен.тов матриц смежности и сравнения ихэлементов на выходе элемента 33 прикаждой перестановке вырабатываетсясигнал несравнения. Таким образом,перебираются все перестановки и навыходе блока 3 появляется сигнал 20окончания перебора всех перестановок. Этот сигнал через элементы 13,45 и 46 поступает на вход блока 14,в котором формируется новое сочетание 11110100, Поскольку в этом сочетании появилась единица в шестомразряде, то на входах шестого элемента И группы 18 появляются единич-.ные сигналы. Поэтому единичный сигнал с выхода этого элемента И черезэлемент ИЛИ 23 поступает на счетныйвход триггера 24 и переводит его внулевое состояние. Этот же сигнал через элемент 27 задержки и открытыйэлемент И 26 поступает на третий входблока 16 и записывает единицу в его358-й разряд, а также через элементИЛИ 35 поступает на первый вход группы 15 элементов И и на входы переключения разрядности регистров 4 и 9, 40блока 3 и коммутатора 1 2. В результате этого по входу 44 от источникаединичных сигналов в первые четыреразряда блока 14 записываются единицы, от регистров 4 и 9 и блока 3 отключаются шестые разряды, коммутатор12 переключается к выходам блока 7памяти,После этого начинается новый процесс анализа на планарность семивер 50шинного подграфа, состоящего из вершин 1,2,3,4,6,7,8 аналогично описанному, т.е. сначала перебираются всесочения по 5 из всех вершин, записанных в блоке 1 6 при этом вершина 8фиксирована,а перебираются толькочетыре вершины из планарного подграфа, т.е. состоящего из вершин 1,2,3,4,6,7). Если при этом появляетсяЫ 7 ОЗ ми входами дешифратора, вторая группа выходов блока накопления планарних вершин, соединена с первой группой пЮормационных входов шестого комму 5 татора, а вторая группа информационных входов соединена с первыми входами соответствующих элементов И второй группы, группой информационных входов шестого коммутатора, группой выходов блока формирования сочетаний, первая группа входов которого соединена с входом установки начального состояния устройства, вторая группа вхо. дов соединена с выходами соответствующих элементов И первой группы,а счетный вход соединен с выходом одиннадцатого элемента И 5 П 1, первый и второй входы которого соединены соответственно с выходами пятого и шестого 20 элементов И, группа выхода блока формирования перестановок соединена с группами управляющих входов с первого о четвертый коммутаторов, инфораппонние выходы первого регистра 25 сдвига соединены с информационными входами первого и второго коммутаторов, информационные выходы второго регистра сдвига соединены с информационными входами третьего и четвертого коьиутаторов, выходи первого и третьего коммутаторов соединены соответственно с первыми и вторыми адреснымп входами первого блока памяти, информационные выходы которого соедипены с первыми информационными входами пятого коммутатора, вторые информационные входы которого соединены с информационными выходами второго блока памяти, первые и вторье адрес О ние входы которого соединены соответственно с выходами второго и четвертого коьс 1 утаторов, управляющий входпятого коммутатора соединен с вторымвходом блока Формирования перестановок, информационными входами шестогоразряда первого и второго регистровсдвига, первыми входами элементов Ипервой группы и выходом первого элемента И, выходы пятого коммутаторасоединены с соответствующими входамитретьего элемента ИЛИ, выход которогосоединен с первым входом элементасравнения, выход которого. соединенс перпьи ходами шестого, восьмого 55десятого элементов ИЛИ, входом второго элемента задержки, вторым входомшестого элемента И и третьим входомблока Формирования перестановок, входы установки в исходное состояние которого соединены с выходом девятогоэлемента И, первый вход которогосоединен с первыми входами четвертого и пятого элементов И, вторым входом десятого элемента И, первыми входами пятого и шестого элементов ИЛИ и выходом старшего разряда второго регистра сдвига, вход установки в начальное состояние которого соединен с входом установки в начальное состояние первого регистрасдвига и выходом восьмого элементаИ, второй вход которого соединен свходом установки начального состояния устройства и вторым входом девятого элемента ИЛИ, выход старшего разряда первого регистра сдвига соединенс входом сдвига второго регистрасдвига и вторым входом седьмого элемента ИЛИ, выход которого соединен со счетным входомузла последовательного опросаразрядов по горизонтали, вход сброса которого соединен с выходом десятого элемента ИЛИ, информационные выходы шестого коммутатора соединеныс вторыми группами выходов узловпоследовательного опроса разрядовпо вертикали и по горизонтали, выходы опросакоторых соединены соответственно с первым и вторым входамисоответствующего элемента ИЛИ группы,выходи которых соединены с соответствующими информационными входамиблока задания топологии графа, информационные выходы которого соединеныс соответствующеи входами второгоэлемента ИЛИ, выход которого соединенс вторым входом элемента сравнения,выход второго элемента задержки соединен с вторым входом седьмого элемента ИЛИ, выход окончания перебора перестановок блока формирования перестановок соединен с первыми входами третьего и шестого элементов И и входомустановки в "1" второго триггера, прямой выход которого соединен с вторыми входами шестого и четвертогоэлементов И, выход которого соединенс вторым входом четвертого элементаИЛИ и с вторым выходом блока накопления планарных вершин, первый и третий входы которого соединены соответственно с первым и третьим входамичетвертого элемента ИЛИ и выходамитретьего и второго элементов И, а четвертый вход блока накопления планар36 18динены с выходами соответствующих элементов И второй группы, вторые входы которых соединены с соответствующими выходами дешифратора, выход нулевого состояния блока накопления планарных вершин соединен с управляющим входом шестого коммутатора, инверсный выход второго триггера соединен с вторыми входами третьего и пятого элементов И, выход окончания решения задачи блока накопления планарных вершин является выходом окончания решения задачи устройства, входы задания топологии блока задания топологии графа являются входами задания тополо-. гии графа устройства, а выход четвертого элемента ИЛИ соединен с вторыми входами элементов И первой группы. 7 15170 ных вершин соединен с входом сброса второго триггера, с вторыми входами пятого и шестого элементов ИЛИФ третьим входом седьмого элемента ИЛИ и входом установки начального состоя 5Фния устройства,. выход шестого элемента ИЛИ соединен с входом синхронизации узла последовательного опроса разрядов по вертикали, выход пятого 1 О элемента ИЛИ соединен с входом сброса первого триггера, прямой и инверсный выходы которого соединены с первыми входами первого и второго элементов И соответственно, вторые 15 входы которых соединены с выходом первого элемента задержки, вход которого соединен с входом синхронизации первого триггера и выходом пер - вого элемента ИЛИ, входы которого сое