Устройство для решения комбинаторнологических задач на графах

.И. МаКОМБ ГРАФ 6 ся к автоматике и и может быть исзадач выделения ри автоматизироии электронных ОСУДАРСТВЕННЫЙ КОМИТЕТ0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР(56) Авторское свидетельство СССВ 482751, кл, 6 06 Е 15/20, 1973,Авторское свидетельство СССМ 1517036,.кл. 6 06.Р 15/20, 1987.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯНАТОРЕЛО-ЛОГИЧЕСКИХ ЗАДАЧ НА Изобретение относит вычислительной технике пользовано для решения планарной части схемы п ванном проектирован схем. Известно устройство для решения комбинаторно-логических задач, содержащее блоки управления, ввода информации, моделирования матрицы смежности, анализа и вывода информации, при этом блок управ, ления соединен с входами всех остальных блоков, а его единственный вход соединен с выходом блока анализа, первым входом соединенного с первым входом блока вывода, а вторым выходом - с вторым входом блока моделирования мат, рицы смежности.Недостатком устройства является не возможность с его помощью решать задачу выделения планарной части графа.Известно также устройство для решения комбинаторно-логических задач при(57) Изобрете ной технике и выделения пл томатизирова ронных схем. уменьшение а выделения и нарной части бора возмо, проверки их бора сочетани ратурные затр устройством и . мо неподходя ние относится к вычислитель- может быть использовано для анарной части схемы при авнном проектировании электЦелью изобретения является ппаратурных затрат, Задача ланарной части графа (пласхемы) решается путем пережных сочетаний вершин и планарности, Алгоритм перей позволяет уменьшить аппааты по сравнению с известным исключить некоторые заведощие сочетания. 4 ил. проектировании печатных плат, содержащее блок памяти, блок формирования схемных ограничений, блок определения перестановок, блок вывода информации, блок управления, дешифратор и блок кодированрия размера планарной части графа, выходом соединенный с первым входом блока формирования схемных ограничений, вторым входом соединенного с выходом блока памяти, а выходом - с входом блока определения перестановок, первый выход которого соединен с входом блока управления, а второй выход - с первым входом блока вывода, второй вход которого соединен с первым выходом блока управления, вторым входом соединенного с входом дешифратора, выходом соединенного с входа блока кодирования размера планарной части.Недостатком известного устройства являются большие аппаратурные затраты, необходимые для его реализации,Наиболее близким к предлагаемому является устройство для решения комбина 1709349 2010 15 навливаются (в) левых разрядов. Если имеется п разрядов, а необходимо сформи 20 30 40 45 50 Функции коммутатора в предлагаемом устройстве выполняет блок перебора сочетаний,Кроме того, предлагаемое устройствоболее функционально надежно, так как в55 нем используется более надежная схема узлов последовательного опроса разрядов,, блок перебора сочетаний.Формул а из о б рете н ияУстройство для решения комбинаторнологических задач на графах, содержащее геруется новое сочетание. Поскольку первоначально в блоке 4 разрешены пять разрядов (1-й,2-й,З-й,4-й,б-й) и во все этиразряды записаны "1", то это сочетание,, является единственным, т.е. С 55, Поэтомупри поступлении очередного сигнала в,блок 4 с блока 3 на выходе блока 4 появляется сигнал об. окончании формированиявсех сочетаний. Этот сигнал поступает насчетный вход триггера 24 и переводит егов нулевое состояние. Этот же сигнал черезэлемент 27 задержки и открытый элементИ 26 поступает на третий вход блока 6 изаписывает единицу в его 8-й разряд, атакже через элемент ИЛИ 35 поступает напервый вход блока элементов И 15. В результате этого по входу 12 от,источника единичных сигналов в первые четыре разрядаблока 4 записываются единицы. Так кактриггер 24 находится в нулевом состоянии,на его единичном выходе установлен нулевой потенциал иот регистров 14,41 и блока3 отключены шестые разряды, а коммутатор 46 переключен к выходам блока 44памяти. После этого начинается новый 2процесс анализа на планарность семивершинного графа, состоящего из вершин1,2,3,4,6,7,8 аналогично описанному, т.е.сначала перебирают все сочетания по "5"из всехвершин, записанных в блоке 6(приэтом вершина 8 Фиксируетсяа перебираются только четыре вершины из планарного подграфа, состоящего из вершин1,2,3,4,6;7). Если при этом появляется хотябы для одного сочетания сигнал изоморфизма, то 8-я вершина нарушает планар-ность подграфа, поэтому она блокируетсяна выходе блока 6, а новая единица записывается в 9-й разряд блока 6. Если сигнализоморфизма не появляется, то схема переходит к формированию всех сочетаний по"6" из всех вершин, записанных в блоке 6,Если нарушений планарности не обнаружено,.-то на. третий вход блока 6 поступаетсигнал планарности, по которому в 9-й разряд записывается единица, а 8-я вершинане блокируется,Такой процесс продолжается до техпор, пока единица не появится на выходе 10последнего разряда блока 6, что являетсясигналом окончания процесса решения задачи. Номера планарных вершин снимаются с второй группы выходов блока 6.На фиг.З приведен вариант выполненияфункциональной схемы блока формирования сочетаний на произвольно выбранных Мразрядах (к п), причем последовательностьразрядов является произвольной.Устройство работает по следующемупринципу. Каждое очередное сочетание получается из предыдущего путем перевода е левых следующих подряд единичных разрядов в "0", а первого правого нулевого разряда - в "1" и последующего восстановления в (в)-х крайних левых разрядах единиц, Если в р левых разрядах стоят нули, то осуществляется обход этих разрядов и в "0" переводятся а подряд следующих единичных разрядов начиная с (р+1)-го разряда, а (р+п+1)-й разряд переводится в "1". При этом независимо от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстароватьсочетания из 1 разрядов (1 п), то вводится запрет на использование ненужных разрядов, и происходит обход запрещенных разрядов, Запрещенными могут быть любые разряды.Перевод в единицу нулевого разряда, которому предшествует группа из подряд следующих единичных разрядов, происходит в триггерах 54. Восстановление единиц обеспечивается триггерами 59 с элементами И 60,61 и 69, формирователями 69 и элементами ИЛИ 67 и 68. Элементы ИЛИ 51, И 56-58 и регистр 47 обеспечивают обход запрещенных разрядов, Элементы И 64 и 65 и ИЛИ 53 обеспечивают окончание работы устройства после Формирования всех сочетаний. На выходе 50 элементов И 63 снимаются сочетания после окончания переходных процессов.Перед началом работы в регистр 47 заносится комбинация участия разрядов в формировании сочетаний. Если разряд участвует в формировании сочетаний, в сооответствующий разряд регистра 47 записывается "1", в противном. случае - "0".Технико-экономическая эффективность предлагаемого устройства состоит в значительном уменьшении аппаратурных затрат,что возмежно благодаря исключению из схемы некоторых узлов, аппаратурная сложность которых нелинейно растет от числа вершин исследуемых графов, и замене их линейно зависимыми узлами. В частности,нератор тактовых импульсов, ключ, блок управления формированием сочетаний, блок формирования перестановок, блок накоп-, ления планарных вершин, блок управления накоплением планарных вершин, блок селекции и задания топологии графа и блок записи и считывания информации, причем выход генератора тактовых импульсов подключен через ключ к счетным входам блока формир,.ээния перестановок, блока селекции и задания топологии графа и блока записи и считывания информации, информационные выходы блока формирования перестанов х г адключены к информационным входам блока записи и считывания информации, выход окончания перебора всех перестановок блока формирования перестановок подключен к входу формирования нового сочетания блока управления формированием сочетаний и входу записи первОй пленарной пятерки блока управления накоплением планарных вершин, информационные выходы блока формирования сочетаний подключены к информационным входам блока накопления планарных вершин, первые информационные выходы которого подключены к первым информационным входам блока селекции и задания топологии графа, первый выход изоморфизма полному пятивершинному графу блока записи и считывания информа, ции подключен к входам установки в исходное состояние блока формирования перестановок и блока селекции и задания топологии графа, входу формирования нового сочетания блока управления формированием сочетаний и входу блокировки непланарной вершины блока управления накоплением планарных вершин, выход смежности блока записи и считывания информации подключен к входу сравнения блока селекции и задания топологии графа, выход несравнения которогоподключен к входу формирования новой перестановки блока формирования перестановок и входу установки в исходное состояние блока записи и считывания информации, выход записи первой планарной вершины блока управления накоплением планарных вершин подключен к входу записи первой планарной пятерки блока накопления планарных вершин, выход блокировки непланарной вершины блока управления накоплением планарных вершин подключен к одноименному входу блока накопления планарных вершин, выход добавления новой вершины блока управления накоплением планарных вершин - кодноименному входу блока накопленияпланарных вершин, выход записи четырехединиц блока управления накоплением пла 5 нарных вершин - к одноименному входублока управления формированием сочетаний, выход проверки изоморфизма шестивершинйому двудольному графу Кенигаблока управления накоплением пленарных,10 вершин подключен к входу записи пяти единиц блока управления формированием сочетаний, входу йодключения шестогоразряда блока формирования перестановок й входу подключения шестого разряда15 и переключения коммутатора блока записи и считывания информации, выход переключения блока управления накоплениемпланарных вершин подключен к входу формирования нового сочетания блока управле 20 ния формированием сочетаний, выходформирования нового сочетания которогополключен к одноименному входу блокаформирования сочетаний, первые информационные входы которого подключены к25 информационным выходам блока управления формированием сочетаний, управляющий выход блока накопления планарныхвершин является выходом признака окончания работы устройства, общий вход ус 30 тановки исходного состояния устройстваподключен к одноименным входам блокаформирования перестановок, блока записи и считывания информации, блокаселекции и задания топологии графа, блока35 управления накоплением планарных вершин, блока накопления планарных вершини вторым информационным входам блокаформирования сочетаний, вход единичных .сигналов блока управления формированием40 сочетаний является входом для подключения источника единичных сигналов устройства, о т л и ч а ю щ е е с я тем, что, с цельюуменьшения аппаратурных затрат, вторыеинформационные выходы блока накопления45 планарных вершин подключены к вторыминформационным входам блока формирования сочетаний, информационные выходы. которого подключены к вторым информационным входам блока селекции.и задания50 топологии графа, выход записи четырех еди ниц блока управления накоплением планарных вершин подключен к входу разрешениязаписи блока формирования сочетаний, управляющий выход которого подключен к од 55 ноименному входу блока управлениянакоплением планарных вершин,1709349 гактор Л, Пчолинская Техред М,Моргентал Корректор М. Демчик аз 428 Тираж Подписное ВНИИХИ Государственного комйтета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 ственно-издательский комбин тент", г. Ужгород, ул, Гагарина, 101 Пр ще фф юпйвбрао10 15 20 25 30 35 управления блоком накопления планарных вершин соединен с вторым входом 40 45 50 55 торно-логических задач на графах, содержащее генератор тактовых импульсов, блок формирования перестановок, блок формирования сочетаний, ключ, коммутатор выходов блока формирования сочетаний; блок 5 накопления планарных вершин, дешифратор, устройство управления блоком формирования сочетаний (состоящее из блоков элементов И и элемента 2 И-ИЛИ), блок совпадения (состояший из группы двухвходовых элементов И и и-входового элемента ИЛИ), устройство управления блоком накопления планарных вершин (состоящее из двух триггеров, четырех элементов И, двух элементов ИЛИ и элемента задержки), блок записи и считывания информации (состоящий из двух запоминающих устройств (ПЗУ), четырех коммутаторов для опроса ПЗУ, коммутатора выходов ПЗУ, двух регистров сдвига и двух элементов ИЛИ) и блок селекции и задания топологии графа (состоящий из двух узлов последовательного опроса разрядов по горизонтали и вертикали, блок задания топологии графа, группы двухвходовых элементов ИЛИ, и-входого элемента ИЛИ, схемы сравнения, трех элементов ИЛИ, элемента задержки), при этом выход генератора тактовых импульсов. через ключ соединен с первым входом блока формирования перестановок (нумерация входов-выходов сверху вниз), первым входом блока селекции и задания топологии графа и первым входом блока записи и считывания информации, информационные входы блока формирования перестановок соединены с информационными входами блока записй и считывания информации, выход блока формирования перестановок соединен с пятым входом устройства управления блоком формирования сочетаний и вторым входом устройства управления блоком накопления планарных вершин, информационные входы блока формирования сочетаний соединены с информационными входами блока накопления планарных вершин, вторыми информационными входами коммутатора выходов блока формирования сочетаний и вторыми информационными входами блока совпадения, первые информационные вы- ходы блока накопления планарных вершин соединены с информационными входами блока селекции и задания топологии графа, вторые информационные выходы блока накопления планарйых вершин соединены с информационными входами дешифратора, информационными выходами соединенного с первыми информационными входами блока совпадения, третьи информационные выходы блока накопления планарных вершин соединены с первыми информационными выходами коммутатора выходов блок формирования сочетаний, информационные выходы которого соединены с информационными входами блока селекции и задания топологии графа, первый вь 1 ход блока записи и считывания информации соединен с четвертым входом блока формирования перестановок, вторым входом блока селекции и задания топологииграфа,четвертым входом устройства управления блоком формирования сочетаний и первым входом устройства управления блоком накопления планарных вершин, второй выход блока записи и считывания информации соединен с третьим входом блока селекции и задания топологии графа, выход блока селекции и задания топологии графа соединен с третьим входом блока записи и считывания информации и третьим входом блока формирования перестановок, выход блока совпадения соединен с третьим входом устройства управления блоком управления планарных вершин, первый, второй и третий выходы устройства управления блоком накопления планарных вершин соединены с первым, вторым и третьим входами блока накопления планарных вершин, четвертый выход устройства управления блоком накопления планарных вершин соединен с первым входом устройства управления блоком формирования сочетаний, информационные входы которого соединены с информационными входами блока формирования сочетаний, пятый выход устройства устройства управления блоком формирования сочетаний, вторым входом блока формирования перестановок и вторым входом блока записи и считывания информации, шестой выходустройства управления блоком накопления планарных вершин соединен с третьим входом устройства управления блоком формирования сочетаний, седьмой выход устройства управления блоком накопления планарных вершин соединен с шестым входом устройства управления блоком формирования сочетаний, выход которого соединен с входом блока формирования сочетаний, первый выход блока накопления планарных вершин соединен с входом коммутатора выходов блока формирования сочетаний, а второй выход блока накопления планарных вершин является выходоМ окончания работы устройства.Недостатком известного устройства являются большие аппаратурные затраты, необходимые для его реализации.Цель изобретения - уменьшение аппаратурных затрат устройства.45 5055 Поставленная цель достигается тем, что в устройство, содержащее генератор тактовых импульсов, ключ, блок формирования сочетаний (БФС), устройство управления блоком формирования сочетаний(УУ 1), блок 5 формирования перестановок (БФП), блок , накопления планарных вершин (БНПВ), устройство управления блоком накопления планарных вершин (УУ 2), блок селекции и задания топологии графа (БС и ЭТГ) и блок 10 записи и считывания информации(БЗ и СИ), причем выход генератора тактовых импульсов через ключ соединен с первым входом (счетный вход) БФП, первым входом (счетный вход) БС и ЗТГ и первым входом (счет ный вход) БЗ и СИ, информационные выходы БФП соединены с информационными входами БЗ и СИ, выход окончания перебора всех перестановок БФП соединен с пятым входом формирования нового саче танйя УУ 1 и вторым входом записи первой планарной пятерки вершин УУ 2, информационные выходы БФС соединены с информационными входами БНПВ, первые информационные выходы БНПВ соединены 25 с первыми информационными входами БС и ЗТГ, первый выход изоморфизма полному пятивершинному графу БЗ и СИ соединен с четвертым входом установки в исходное состояние БФП, вторым входом установки в 30 исходное состояние БС и ЗТГ, четвертым .входом формирования нового сочетания УУ 1 и первым входом блокировки непланарной вершины УУ 2, второй выход смежности БЗ и СИ соединен с третьим входом сравне ния БС и ЗТГ, выход несравнения БС и ЗТГ соединен с третьим входом формирования новой перестановки БФП и третьим входом установки в исходное состояние БЭ и СИ, первый выход записи первой планарной 40 вершины УУ 2 соединен с первым входом записи первой планарной пятерки вершин БНПВ, второй выход блокировки непланарной вершины УУ 2 соединен с вторым входом блокировки непланарной вершины БНПВ, третий выход добавления новой вер-. шины УУ 2 соединен с третьим входом добавления новой вершины БНПВ, четвертый выход записи четырех единиц УУ 2 соединен с первым входом записи четырех единиц УУ 1, пятый выход проверки изоморфизма шестивершинному двупольному графу Кенига УУ 2 соединен с вторым входом записи пяти единиц УУ 1, вторым входом подключения шестого разряда БФП и вторым входом подключения шестого разряда и переключе-. ния коммутатора БЗ и СИ, шестой выход переключения УУ 2 соединен с третьим входом формирователя нового сочетания УУ 1,седьмой выход переключения УУ 2 - с шестым входом формирования нового сочетания УУ 1, выход формирования нового сочетания которого соединенр с первым входом формирования нового сочетания БФС, информационные выходы УУ 1 соединены с первыми информационными входами БФС, выход БНПВ является выходом окончания работы устройства, общий вход установки исходного состояния устройства соединен с пятым входом БФП, четвертым входом БЗ и СИ, четвертым входом БС и ЗТГ, четвертым входом УУ 2, четвертым входом БНПВ и вторыми информационными входами БФС, источнйк единичных сигналоЬ соединен с седьмым входом УУ 1, вторые информацион,ные выходы БНПВ соединены с вторыми информационными входами БФС, информационные выходы-БФС - с вторыми информационными входами БС и ЗТГ, четвертый выход УУ 2 - с вторым входом разрешения записи БФС, выход БФС - с третьим входом УУ 2.На фиг.1 приведена структурная схема устройства; на фиг.2 - функциональная схема устройства; на фиг,3 - функциональная схема блока формирования сочетаний; на фиг.4 - функциональная схема узлов последовательного опроса разрядов по вертикали и горизонтали.Устройство для решения комбинаторнологических задач на графах содержит генератор 1 тактовых импульсов, ключ 2, блок 3 формирования перестановок, блок 4 формирования сочетаний, устройство 5 управления блоком формирования сочетаний, блок 6 накопления планарных вершин, устройство 7 управления блоком накопления планарных вершин, блок 8 селекции и задания топологии графа, блок 9 записи и считывания информации, выход 10 окончания работы устройства, вход 11 установки исходного состояния, вход 12 источника единичных сигналов и входы 13 задания топологии графа. Генератор 1 через ключ 2 соединен с первым входом блока 3, первым входом блока 8 и первым входам блока 9. Информаци-, онные выходы блока 3 подключены к информационным входам блока 9. Выход окончания перебора перестановок блока 3- соединен с пятым входом устройства 5 управления и вторым входом устройства 7 управления. информационные выходы блока 4 связаны с информационными входами блока 6 и вторыми информационными входами блока 8. Первые информационные выходы блока 6 соединены с первыми информационными входами блока 8, вторые информационные выходы блока 6-с информационными входами блока 4, Первый выход блока 9 подключен к четвертому входууправления. Выход 10 блока 6 является выходом. окончания работы устройства. Общий35 45 50 55 установки в исходное состояние блока 3, второму входу установки в исходное состояние блока 8, четвертому входу устройства 5 управления и первому входу блокировки устройства 7 управления. Второй выход блока 9 соединен с третьим входом сравнения блока 8. Выход блока 8 подсоединен к третьему входу формирования новой перестановки блока 3 и третьему входу установки в исходное состояние блока 9, Первый выход устройства 7 управления связан с первым входом записи первой планарной пятерки вершин блока 6, второй выход - с вторым входом блокировки непланарной вершины блока 6, третий выход - с третьим входом добавления новой вершины блока 6, четвертый выход - с первым входом записи четырех единиц устройства 5 управления и вторым входом разрешения записи блока 4, пятый выход- с вторым входом записи пяти единиц устройства 5 управления, вторым входом подключения шестого разряда блока 3 и вторым входом подключения шестого разряда и переключения коммутатора блока 9, шестой выход - с третьим входом устройства 5 управления, седьмой выход - с шестым входом устройства 5 управления, выход которого. соединен с первым входом формирования нового сочетания блока 4. Информационные выходы устройства 5 управления подключены к первым информационным входам блока 4. Выход блока 4 соединен с третьим входом устройства 7 вход 11 установки исходного состояния устройства соединен с пятым входом блока 3, четвертым входом блока 9, четвертым входом блока 8, четвертым входом устройства 7 управления, четвертым входом блока 6 и вторыми информационными входамиблока 4.Функциональная схема устройства содержит генератор 1 тактовых импульсов, ключ 2, блок 3 формирования перестановок, блок 4 формирования сочетаний; блок 6 накопления планарных вершин, регистры 14 и 41 сдвига, блок элементов И 15, коммутатора 16,17,42,43 и 46, элемент 2 И-ИЛИ 18, элементы ИЛИ 19,23,32,34-37,39 и 40, группу элементов ИЛИ 22, элементы И 26;29 и 30, элементы 25,27 и 38 задержки; узел 20 последовательного опроса разрядов по вертикали, узел 21 последовательного опроса разрядов по горизонтали, триггеры 24 и 28,блок 31 задания топологии графа, схему 33 сравнения, ПЗУ 44 и 45, выход 10 является выходом окончания работы устройства, вход 11 - входом установки исходного состояния, вход 12 - вхо 5 10 15 20 25 30 дом источника единичных сигналов, входы 13 - входами задания топологии графа,Блок 4 содержит регистр 47, элементы ИЛИ 48,53 и 73, регистр 49 сдвига, элементы 70 и 72 задержки, переключатель 74; Каж дый разряд блока 4, кроме первого и последнего, содержит триггеры 54 и 59, элементы ИЛИ 55,67 и 68, элементы И 56,57,58,60,61,63 и 69 и формирователь 62 импульсов, Первый разряд блока 4 содержит укаэанные элементы, за исключением элементов ИЛИ 55,67 и 68 и элементов И 56,57 и 69. В последнем разряде отсутствуют элементы ИЛИ 67 и 68, элемент И 69 и формирователь 62 импульсов. Кроме того, с первого по четвертый разряды блока 4 содержат элемент ИЛИ 51, а все разряды с пятого по и-й содержат элемент И 66. Кроме того, разряды с третьего по п-й блока 4 содержат элементы И 64 и 65. Второй разряд содержит только элемент И 65. При этом один вход элемента ИЛИ 73 соединен с кнопкой 74 "Пуск", а второй вход через элемент задержки 72 - с выходом переключателя 71 и первыми входами элементов И 63. Один вход переключателя 71 подключен к входу 75 подачи тактовых импульсов, а второй вход через элемент 70 задержки - к кнопке 74 "Пуск", Выход элемента ИЛИ 73 связан с входами синхронизации триггеров 59 и входами установки исходного состояния регистра 71 сдвига. Каждый выход регистра сдвига (третий, четвертый, пятый, шестой) подключен к первому входу элемента И 58. Выходы элементов И 58 (с первого по четвертый разряды) соединены с первыми входами элементов ИЛИ 51, выходы остальных элементов И 58 - свходами установки единичного состояния триггеров 54. Единичный выход первого триггера 59 подключен к первому входу первого элемента И 60, Единичные выходы остальных триггеров 59 (кроме последнего) соединены с первыми входами элементов ИЛИ 67, вторыми входами элементов И 60 и вторыми входами элементов И 65. Единичный выход последнего триггера 59 связан с первыми входами элементов И 60 и 61. Нулевой выход триггеров 59 (кроме последнего триггера) соединен с первыми входами элементов И 61, Выход переключателя 71 подключен к входам первых элементов И 60 и 61. Выход 1-го элемента И 61 О = 1, и) соединен с входами соответствующих (1+1)-х элементов И 60 и 61. Выход последнего элемента И 61 связан с входом элемента ИЛИ 53. Выход 1-го элемента И 60 (1 = 2, и) соединен с первым входом 1-го элемента ИЛИ 68 и вторым входом 1-го элемента ИЛИ,55. Выход первого элемента Ивыход которого подключен к синхровходу регистра 49 сдвига. Второй вход Г-го элемента ИЛИ 51 (Г.= 1,4) и вторые входы элементов И 58 и 66 соединены с информационнымивходами устройства, Выход Г-го элемента И 66 связан с вторыми входами (Г+1)-х элементов И 58 и 66,Каждый оазряд узлов 20 и 21 (кроме первого) содержит триггер 76, элементы ИЛИ 77 и 79 и элементы И 78 и 80, Первый 55 60 подключен к входу формирователя импульсоа.62, второму входу элемента ИЛИ 68 и счетному входу первого триггера 54. Вы= .ход последнегоэлемента И 60 соединен с вторым входом элемента ИЛИ 55. Первый 5 выход регистра 47 связан с вторым входомэлемента И 58, Второй, третий, четвертый регистра 47 соединены с вторыми входами элементов И 57 и 58 и вторыми инверсными входами элементов. И 56 и 64. Остальные 10 выходы регистра 47, кроме того, связаны с первыми инверсными входами элементов И 66. Единичный выход триггеров 54 сое динен с вторым входом элементов И 63 и информационным входом триггеров 59. 15 ,Выходы 50 элементов И 63 являются информационными выходами устройства.Нулевой выход первого триггера 54 подключен к второму входу элемента И 55, нулевой выход Г-го триггера 54 (Г = 2,п) - .20 к второму входу элемента ИЛИ 55 и первому входу элемента И 65, нулевой выход последнего триггера 54 - первому входу и-го элемента И 61, Выход элемента ИЛИ 55 соединен с входами элементов И 56 и 57. 25 Выход элемента И 57 связан со счетным входом триггера 54. Выход Г-го элемента И 56 (Г =1,п) соединен с третьим входом (Г+1)-го элемента ИЛИ 55 и вторым входом элемента ИЛИ 67. Выход последнего эле мента И 56 подсоединен к входам элементов И 64 и 65. Выходь элементов И 65 соединены с входами элемента ИЛИ 53, выход 52 которого является выходом окон чания перебора всех сочетаний. Выход Г-го 35 элемента И 64 (Г = З,п) соединен с вхоДами (Г)-х элементов И 64 и 65. Выход второго элемента И 64 соединен с входом первого элемента И 65. Выход элемента ИЛИ 68 соединен с первым входом соответствую щих элементов И 69. Выход элемента ИЛИ 67 связан с вторым входом соответствующего элемента И 69, Выход Г-го элемента И 69 (Г = 1,п) соединен с входом соответствующего формирователя 62 и вторым 45 входом (Г+1)-го элемента ИЛИ 68. Выход ,последнего элемента И 69 подсоединен к входу соответствующего формирователя 62, Выход Г-го формирователя 62 (Г =. 1,п) соединен с Г-м входом элемента ИЛИ 48, 50 разряд выполнен только на триггере 76, При этом выход триггера 76 соединен с входом Г-го элемента ИЛИ 77 (Г - 1,п), второй вход которого связан с (Г)-м элементом И 80, выход элемента ИЛИ 77 соединен с первым входом элемента И 78 и первымвходом элемента И 80, второй инверсный вход которого подключен к выходу элемента ИЛИ 79, выход элемента ИЛИ 79 соединен также с . вторым входом соответствующего элемента И 78, выход которого подключен к О-входу Г-го триггера 76 (Г = 2,п). Синхровход триггера 76 соединнен с входом 81, й-вход Г-го триггера (Г - 2, и) и 8-вход первого триггера связаны с входом 82, На О-вход первого триггера подается "0". Первые входы элеменртов ИЛИ 9 соединены с входом 83, а вторые входы - с входом 84. Выходы 85 являются информационными выходами устройства.Принцип работы устройства основан на использовании теоремы Пектрягина-Куратовского, которая формулируется следующим образом. Граф является плоским тогда и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени два одному из графов Пектрягина-Куратовского. Из теоремы следует что для определения планарности графа из него необходимо последовательно выбирать всевозможные сочетания пяти и шестивершинных подграфов и сравнивать их на изоморфизм с полносвязным пяти- вершинным (65) и двудольным шестивершинным (граф Кенига бз,з) графами соответственно.Для организации выбора из исследуе- мого графа 5- и 6-вершинных подграфов предлагается использовать формирователь сочетаний булевых переменных с лексикографической последовательностью сочетаний на выходе. Под лексикографической последовательностью сочетаний булевых переменных понимается такая последовательность, в которой сочетания позиционно упорядочены по возрастанию. Кроме того, предлагается в данном формирователе сочетаний предусмотреть возможность формирования сочетаний.на произвольно выбранных М разрядах из п разрядов (Ки). Это позволит проводить формирование сочетаний не на всех разрядах, а только на тех, которые соответствуют рассматриваемым вершинам.Дляопределения изоморфизма выбираемых 5- и 6-вершинных подграфов с полно- связным 5-вершинйым и двудольным б-вершинным графами предлагается ис-. пользовать процедуру полного перебора с помощью формирователя перестановок бу 1709349 12левых переменных (т.е. выдача перестановок осуществляется в пространственно-временной форме). Целесообразно использоватьнаиболее простой алгоритм полного переборакоторый. аппаратно реализуется исключительно просто и требует всего 5 = 120тактов при исследовании на изоморфизм5-вершинных графов и 61 = 720 тактов приисследовании Е-вершинных графов.Устройство определения планарности ивыделения максимально планарНой частиграфа работает следующим образом,1.Подготовка устройства к работе. Дляэтого на вход 11 подается си и" л начальнойустановки, По этому же сигналу в БФС 4 врегистр 47 участия разрядов записываютсявсе "1" и в первые пять разрядов такжезаписываются "1". По входам 13 в БС и ЗТГ8 заносится информация о топологии исследуемого графа,2.Нахождение первой пятерки планарных вершин. Для этого в БФС 4 формируетсясочетания пяти вершин, которое выделяетв БС и ЗТГ 8 из исходного графа пятивершинный подграф. С помощью БФП 3 и БЗи С 4 происходит сравнение этого подграфа с графом Ов.Если произойдет поэлементное сравнение, то выбранный.подграф непланарен, в противном случаепять вершин данного подграфа планарны.Если подграф непланарен, то формируется новое сочетание и работа продолжаетсяаналогично.З,Перепись информации из БФС 4 вБНПВ 6 и добавления в БНВП 6 новой вершины.4.Запись в регистр 47 БФС 4 из БНПВ 6информации. Разрешенными разрядамистановятся разряды, определяемые информацией с БНПВ 6,5,Запись по входу 12 четырех единиц вБФС 4, формирование в нем множества сочетаний С и определения с помощью БФП3 и БЗ и СИ 9 для каждого сочетания вершинграфа изоморфизма графу Ов (к - число вершин в БНПВ 6 на данном шаге).6.Если обнаруживается непланарностькакого-либо сочетания (т.е. изоморфизм вп.5), то в БНПВ 6 добавляется новая "1", апредыдущая блокируется, осуществляетсяпереход к 4. Если выбранное сочетаниевершин планарно, то берется следующеесочетание. По окончании перебора всех сочетаний происходит переход к 7.7. В БФС 4 по входу 12 записываетсяпять единиц в первые пять разрешенныхразрядов, БФС 4 формирует сочетания вершин С 1(. С помощью БФП 3 и БЗ и СИ 9 длякаждого сочетания вершин графа определяется изоморфизм графу Оз,з.50 рого занесены в блок 6, и графа Оз,з, информация о котором хранится в ПЗУ 45, Если и теперь изоморфизм не обнаружен, то этоозначает, что выбранная пятерка вершин планарна. Поэтому дописанная к первоначальной пятерке вершин в блок 6 шестаявершина в нем не блокируется и к этой шестерке вершин добавляется новая седьмаявершина, В противном случае Она блокируется; к первоначальной пятерке вершин вы.бирается новая шестая вершина,5 10 15204045 8. Если обнаруживается непланарность какого-либо сочетания (т.е. изоморфизм в п.7), то в БНПВ 6 добавляется новая "1", а предыдущая блокируется, осуществляется переход к 4, Если выбранное сочетание вершин планарно (т.е, изоморфизм в п.7 не обнаружен), то формируется следующее сочетание. По окончании перебора всех сочетаний происходит переход к п.9,9. Если все вершины перебраны, то Осуществляется переход к п,10, шаг к п.4.10. Конец работы устройства, На выходе 10 БНПВ 6 появляется сигнал окончания работы устройства,Более подробно работу устройства рассмотрим по функциональной схеме (на фиг.2).Блоком 4 формирования сочетаний генерируется лексикографическая последовательность сочетаний булевых переменныхПри этой сначала формируются сочетанияСп, где и - число вершин исследуемаго5графа, Каждое такое сочетание выбираетиз блока 31 с помощью узлов 20 и 21 соответствующую пятерку вершин, С помощью блока 3 формирования перестановок, регистров 14 и 41 сдвига, ПЗУ 44 и 45, коммутаторов 16,17,42,43 и 46 и схемы 33 сравнения выполняется процедура проверки на изоморфизм выбранной пятерки вершин и графа Ов, информация о котором хранится в ПЗУ 44. Первая найденная неизоморфная графу Оь, т.е, планарная, пятерка вершин переписывается в блок 6 накопления планарных вершин, Затем туда же добавляется новая вершина, и начинается процесс перебора сочетаний С 6, причем перебор произ 5водится не по всем разрядам, а только по тем, которые соответствуют выбраннымвершинам (благодаря переписи из блока б комбинации рассматриваемых вершин в регистр 74, участия разрядов блока формирования сочетаний).При каждом таком сочетании выполняется процедура контроля на изоморфизм, Если изоморфизм графу О 5 ни В Одной из всех пятерок сочетания С 6 не обнаружится, то осуществляется проверка на изоморфизм шестивершинного подграфа, вершины котоДобавление каждой новой вершины в множество,планарных вершин осуществляется только после проверки на изоморфизм всех сочетаний пятерок вершин и всех соче.- таний шестерок вершин и при условии, что 5 изоморфиэм не обнаружен.Для исключения заведомо лишних сочетаний необходимо организовать их перебор только по тем вершинам, которые на предыдущих этапах были включены в пла нарное множество вершин. Кроме того, при добавлении каждой новой вершины нет смысла рассматривать сочетания, в которые не входит новая вершина, поскольку они повторяются и их анализ ничего нового в 15 процесс исследований, кроме его задержки, не вносит.Для реализации приведенных положений в предлагаемом устройстве используется блок 4 формирования лексикографи ческой последовательности сочетаний и узлы 20 и 21 последовательного опроса разрешенных разрядов сочетаний.Для худшего случая (когда исследуемый граф полностью планарный) числов всевоз можных сочетаний пятерок и шестерок вершин соответственно составит:М 1= С и 5й 2= С п.Учитывая всевозможные перестановки 30 при каждом сочетании, общее число тактов, которое необходимо затратить на решение задачи исследования планарности и выделения максимально планарной части графа, определяется выражением, 35И = 120(С п+ 6 С п).Рассмотрим в деталях динамику работы устройства для решения комбинаторно-логических задач.Перед пуском устройства осуществляет ся подготовка его к работе. Для этого на вход 11 подается сигнал начальной установки, по которому блок 3 формирования перестановок, регистры 14 и 41, блок 6 накопления планарных вершин, узел 20, триг геры 24 и 28,устанавливаются в нулевое состояние, а в первый разряд узла 21 записывается единица. По этому же сигналу во все разряды регистра 47 блока 4 записываются "1" (т,е. первоначально все разряды 50 формирователя сочетаний являются разрешенными) и в первые пять разрядов блока 4 формирования сочетаний заносятся "1", что соответствует исходному сочетанию 1111100, По входам 13 в блок 31 задания 55 топологии графа заносится информация о топологии исследуемого графа. После этого замыкается контакт 2 и тактовые импульсы (ТИ) начинают поступать на схему, Блок 3 формирования перестановок находится з исходном состоянии и при поступлении на него ТИ выдает единичные сигналы последовательно на входах 1,2,3,4,5.Таким образом, по первому ТИ в блоке 3, регистре 14 и в узле 20 возбуждаются их первые разряды т.е, единичные сигналы появляются на их первых разрядах). При этом ни из блока 44 памяти, ни из блока 31 считывания информации не происходит так как информация о связности двух вершин может появиться только при одновременном их возбуждении. Второй ТИ возбуждает в блоке 3, в регистре 14 и в узле 20 вторые их выходы, При этом единичный сигнал с первого выхода узла 21 через первый (верхний) элемент ИЛИ 22 поступает на первый верхний) вход блока 31, а с второго выхода узла 20 через второй элемент ИЛИ 22 - на второй вход блока 31. Если вершины, соответствующие первому и второму входам блока 31 связаны, то на одном из его выходов появляется единичный сигнал. Одновременно с этим из блока 44 памяти считывается "1" (так как в графе 05 все вершины связаны), которая через коммутатор 46 и элемент ИЛИ 34 поступает на схему 33 сравнения. Поэтому схема 33 сравнения на своем выходе сигнал не вырабатывает. Если первая и вторая вер- шины исследуемого графа не связаны, то на выходе элемента ИЛИ 32 присутствует нулевой сигнал, схема ЗЗ выдает на своем выходе сигнал несравнения, по которому происходит установка в исходное состояние узла 20 через элементИЛИ 37 и узла 21 сначала через элемент ИЛИ 23 в нулевое состояние, а через элемент 38 задержки и элемент ИЛИ 39 в исходное состояние (т.е. в первое). Этот же сигнал несравнения с вьхода схемы 33 сравнения, поступая на вход блока 3, устанавливает(а точнее подготавливает его к формированию) вторую перестановку 2,1,3,4,5,Положим, что сигнал несравнения по второму ТИ на выходе схемы 33 не выработался, Поэтому по третьему ТИ аналогично описанному из блока 44 памяти и блока 31 считывается информация о смежности соответствующих вершин и подается в схему ЗЗ сравнения, Предположим, что при этом схема 33 выдает на своем выходе сигнал несравнения, который устанавливает в исходное состояние регистры 14 и 41, узлы 20 и 21, а блок 3 формирования перестановок подготавливает к формированию новой перестановки 2,1,3,4,5. После этого по каждому ТИ из блока памяти 44 и иэ блока 31 вновь считывается информация о смежности соответствующих вершин и поступает для сравнения на схему 33, Если в регистрах14 и 41 сдвига по каждому ТИ на их входах "1" всегда последовательно переходит с предыдущего разряда на последующий, то нэ выходах коммутаторов 16 и 17 единицы появляются на их выходах в последовательности, определяемой перестановкой, сформированной блоком 3, Так, вторая перестановка 2,1,3,4,5 приводит к тому, что единица с первого выхода регистра 14 проходит на второй выход коммутатора 16 и, соответственно, на второй вход блока 44 памяти. Единица с второго выхода регистра 14 проходит на первый выход коммутатора 16, с третьего - на третий, с четвертого - на четвертый и с пятого - на пятый, Единица с первого выхода регистра 41 проходит на второй выход коммутатора 17. Таким образом, из блока 44 памяти последовательно считываются элементы второй строки матрицы смежности графа О 5 и сравниваются с первой строкой матрицы смежности пятивершинного подграфа, выбранного из исследуемого. графа блоком 4 формирования сочетаний,Допустим, что все пять элементов второй строки графа и первой строки исследуемого подграфа равны, Тогда сигнал несравнения на выходе схемы 33 не выра.- батывается и очередной.ТИ, появившись на выходе регистра 14, переводит "1", которая появляется на первом выходе коммутатора 17 с первого выхода регистра 41 на его второй выход, а также единицу с первого выхода узла 21 на его второй выход (через элемент ИЛИ 39).Таким образом, следующая пятерка ТИ последовательно считывает из блока памяти 44 элементы первой строки матрицы смежности графа Оь а иэ блока 31- элементы второй строки исследуемого пятивершинного подграфа и сравнивать их в схеме 33, Положим, что элементы этих строк равны. Тогда очередной ТИ устанавливает "1" в.третьих разрядах регистра 41 и узла 21, а очередная пятерка ТИ коэлементно аналогично описанному сравнивает третьи строки матриц смежности из блока 44 и из блока 31.Допустим, что во всех последующих строках также происходит поэлементное сравнение. Тогда по очередному ТИ на выходе регистра 41 появляется сигнал, свидетельствующий об изоморфизме пятивершинного подграфа, выбранного из исследуемого графа блоком 14 формирования,сочетаний, и графа О 5. Поскольку граф О 5 непланарен, то непланарен и выбранный подграф. Сигнал изоморфизма с выхода регистра 41 устанавливает в исходное состояние блок 3 формирования перестано вок (через элемент ИЛИ 19), а в блоке 4 формирования сочетаний через логический элемент 2 И-ИЛИ 18 устанавливает новое сочетание 11110100, Кроме того, по этому сигналу узел 20 устанавливается в нулевое состояние. После этого начинается новый процесс определения изоморфизма (неизоморфизма) графа О 5 и выбранного блоком 4 подграфа, состоящего в соответствии с сочетанием 1111010.0 из 1-й,2-й,З-й, 4-й и 6-й вершин. Этот процесс протекает аналогично описанному с той разницей, что иэ-за подачи единиц с 10 синхровходы ТИ единицы появляются последовательно на 1-м,2-м,З-м,4-м и 6-м выходах, т.е. именно на тех выходах, которые однозначно соответствуют сформированно 20 му сочетанию 1111010,0.Предположим, что подграф, состоящий из указанных выше вершин (т.е. 1,2,3,4,6) не изоморфен графу85. Это означает, что при каждои перестановке в процессе поэлементного сравнения матриц смежности 25 на выходе схемы 33 появляется сигнал не- сравнения (неизоморфизма), который. устанавливает каждый раз новую перестановку. При этом перебирают все перестановки. Сигнал. окончания перебора всех перестановок появляется на выходе блока 3. Этот сигнал является признаком планарности выбранного с помощью блока 4 пятивершинного подграфа, Этот сигнал 30 через открытый элемент И 29 поступает на первый управляющий вход блока 6 накопления планарных вершин и переписывает 35 содержимое блока 4 (т.е. 11110100) в блок б. Кроме того, сигнал с выхода блока 3, пройдя открытый элемент И 29, поступа 40 ет также через элемент ИЛИ 35 на первый вход блока элементов И 15 (в результате этого от источника 12 единичных сигналов в первые четыре разряда блока 4 записываются "1"). Через время задержки, достаточное для надежной переписи информации в блоке 6 (элемент 25 задержки), сигнал поступает на вход разрешения записи регистра блока 4 и переписывает в него записанное в блоке 6 сочетание 1111010.0 (таким образом, разрешенными разрядами, по которым производится перебор сочетаний, являются 1-й,2-й,З- й,4-й,б-й разряды), После этого в блок 6 45 50 добавляется шестая единица, которая записывается в соседний разряд справа от крайней правой единицьь планарной пятерки вершин. Поэтому после этого в блоке 6 записана информация 111101100. Причем такая перепись в процессе работы и добавБФС 4 на 1-й,2-й,З-й,4-й и б-й входы узлов15 20 и 21 при последовательной подаче на их181709349173 ления единицы нужна только при первом 11100100(а не 111010,0, поскольку раз-и яво лении сигнала на выходе блока 3 (т,е. решенными являются 1-й,2-й,З-й,4-й,б-йч таний). нужно из лока иЬ к 4 переписать вблокбтолько разряды для формирования сочета ). первую пленарную пятерку вершин). Этот сигнал уже не проходит черЧтобы предотвратить такую перепись 5 И 29 на.первый входбйока 6, так как элемент при последующих появлениях сигнала на И 29 был открыт для прохождения только выходе блока 3, задний фронт первого ТИ, первого сигнала с выхода блока 3. Поэтому поступая на единичный вход. триггера 28, вблокебникакихизмененийнепроисходит, переводит его в единичное состояние. а начинается новый процесс установления, При этом закрываются элементы И 29 и 10 изоморфизма графа О 5 и подграфа, включапервый (т,е. верхний) элемент И узла 18, ющего 1,2,3,6,7 вершины. а открываются элемент ИЗОи второй(т.е. Если выбранный подграф изоморфенй) элемент И узла 18. Поэтому в графу О 5.(или впоследствии графу Оз,з), то дальнейшем смена сочетаний в блоке 4сигнал изоморфизма с выхода ре ргист а 41 происходит по сигналу с выхода блока 3 15 поступаетчереэоткрытыйэлементИЗО(так (т.е. когда при данном сочетании перебраны как после записи первой пленарной пятерки все перестановки), Но этот сигнал в блок 6, вершин триггер 21 постоянно находится в уже не поступает, поскольку элемент И 29, единичном состоянии) на БНПВ 6, заблокиуже закрыт. рует на его выходе последнюю уставленнуюоба-,В блоке 6 выделяются единицы старше вершину и в соседний разряд справа до а-, го разряда и на йервой шине выходов блока вит новую единицу.6 имеется в данном случае унитарный код Предположим, что и это, и все последу. - 000000100. Этот код поступает на первые ющие сочетания пятерок вершин из шести. входы узлов и исследуемых, вплоть до сочетания 011101Так как в первые четыре разряда блока 25 неизоморфны графу О 5. Так как пятый раз нь единицы то он последовательно ряд является запрещенным, то это сочетазаписаию 01111. формирует сочетанияиз "5" по "4". Посколь- ние равносильно сочетанию ку налевые входы блоков 20 и 21 с блока 6 В данном случае, так как сочетание подается код 11110100, то единицы перво, поскольку 5-й разряд запрещен, явго сочетания 111100 с выхода блока 4, 30 ляется последним, то при переднем импульоказываются на первых четырех входах уз-се на выходе блока 4 появляется сигнал об ,лов и20 21.Сучетомтого чтов 7-хразрядах окончании формирования, всех сочетаний.24 в20 и 21 находятся единицы, то общее Этот сигнал перебрасывает триггер в узлов исочетание, поданное на входы узлов 20 и 21 единичное состояние, На единично ом выхследующее 111100100. 35 де триггера 2 появляется сигнал, которыйТеперь при поступлении в схему такто- поступает на второй вход блока элементов выхимпульсов начинается процессустанов- И 15 и на входы переключения емкости реления ланапланарности подграфа, включающегогистров 14 и 41 блока 3 и на вход коммута-.вхо 12 от 1,2,3,4 и 7 вершины, Аналогичные описанно- тора 46. В результате этого по входу от му сначала при исходной перестановке в 40 источника единичных сигналов,в первые блоке 3 (т.е. при перестановке 1,2,3,4,5) по пять разрядов блока 4 записываются единикаждому ТИ происходит поэлементное цы, к регистрам 14,41 и блоку 3 подключаютт .то .46 сравнениние матриц смежности для графа О 5 ся шестые разряды, коммутатор .к 45 памяти. и исследуемого подграфа, включающего подключается к выходам блока и вершины 1,2,3,4,7. 45 Теперь при поступлении ТИ в схему поэлеЕсли в какой-то момент времени на вы- ментно и синхронно считывается из блока ходе схемы вемы 33 вырабатывается сигнал не матрица смежности исследуемого подсравнения (т.е, неиэоморфизма), то по этому графа, включающего вершины сигналу блок 3 формирует вторую переста- а матрица смежности графа Оз,з - из блока новку 2,1,3,4,5 и начинается новый процесс 50 45 памяти.сравнения матрицсмежности. Предположим, что эти графы неизоПредположим, что, перебрав все 5 пере- морфны, т.е. в процессе считывания элестановок; при каждой из них на выходе схе- ментов матриц смежности и сравнения их мы 33 вырабатывался сигнал несравнения элементов на выходе схемы 33 при каждой (неизоморфизма). Тогда на выходе блока 3 55 перестановке вырабатывался сигнал не- появляется сигнал окончания перебора сравнения, Таким образом, перебирают всех перестановок при данйом сочетании. все перестановки й на выходе лока по- Э л поступает через открытый является сигнал окончания перебора всехтот сигнал по тигнал че еэ зел 18верхний элемент узла 18 на вход блока 4, перестановок. Этот сигнал через узел который формирует новое сочетание поступитнавходблока 4, вкоторомформи