Устройство для решения комбинаторнологических задач на графах Советский патент 1992 года по МПК G06F15/173 

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

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

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

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

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

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

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

задания топологии графа, первый выход блока записи и считывания информации соединен с четвертым входом блока формирования перестановок, вторым входом блока Ьелекции и задания топологииграфа,

0 четвертым входом устройства управления блоком формирования сочетаний и первым входом уЬтройства управления блоком накопления планарных вершин, второй выход блока записи и считывания

5 информации соединен с третьим входом блока селекции и задания топологии графа, выход блока селекции и задания топологии графа соединен с третьим входом блока записи и считывания информации и третьим

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

0 первым входом устройства уп равления блоком формирования сочетаний, информационные входы которого соединены с информационными входами блока формирования сочетаний, пятый выход устройства

5 управления блоком накопления планарных вершин соединен с вторым входом устройства управления блоком формирования сочетаний, вторым входом блока формирования перестановок м вторым входом

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

0 сочетаний,первый выход блока накопления планарных вершин соединен с входом коммутатора выходов блока формирования сочетаний, а второй выход блока накопления планарных вершин является выходом окон5 чания работы устройства.

Недостатком известного устройства являк тся большие аппаратурные затраты, необходимые для его реализации.

Цель изобретения - уменьшение аппа-ратурных затрат устройства.

Поставленная цель достигается тем, что в устройство, содержащее генератор тактовых импульсов, ключ, блок формирования сочетаний (БФС), устройство управления блоком формирования сочетаний (УУ1), блок формирования перестановок (БФП), блок , накопления планарных вершин (БНПВ), устройство управления блоком накопления планарных вершин (УУ2), блок селекции и задания топологии графа (ЕС и ЭТГ) и блок записи и считывания информации (БЗ и СИ), выход генератора тактовых импульсов через ключ соединен с первым входом (счетный вход) БФП, первым входом (счетный вход) БС и ЗТГ и первым входом (счетный вход) БЗ и СИ, информационные выходы БФП соединены с информационными входами БЗ и СИ, выход окончания перебора всех перестановок БФП соединен с пять1м входом формирования нового сочетания УУ1 и вторым входом записи первой планарной пятерки вершин УУ2, информационные выходы БФС соединены с информационными входами БНПВ, первые информационные выходы БНПВ соединены с первыми информационными входами БС и ЗТГ, первый выход изоморфизма полному пятивершинному графу БЗ и СИ соединен с четвертым входом установки в исходное состояние БФП, вторым входом установки в исходное состояние БС и ЗТГ, четвертым .входом формирования нового сочетания УУ1 и первым входом блокировки неппанарной вершины УУ2, второй выход смежности БЗ и СИ соединен с третьим входом сравнения БС и ЗТГ, выход несравнения БС и ЗТГ соединен с третьим входом формирования новой перестановки БФП и третьим входом установки в исходное состояние БЗ и СИ, первый выход записи первой планарной вершины УУ2 соединен с первым входом записи первой планарной пятерки вершин БНПВ, второй выход блокировки непланарной вершины УУ2 соединен с вторым входом блокировки непланарной вершины БНПВ, третий выход добавления новой вершины УУ2 соединен с третьим входом добавления новой вершины БНПВ, четвертый выход записи четырех единиц УУ2 соединен с первым входом записи четырех единиц УУ1, пятый выход проверки изоморфизма шестивершинному двупольному графу Кенига УУ2 соединен с вторым входом записи пяти единиц УУ1, вторым входом подключения шестого разряда БФП и вторым входом подключения шестого разряда и переключения коммутатора БЗ и СИ, шестой выход переключения УУ2 соединен с третьим входом формирователя нового сочетания УУ1, седьмой выход переключения УУ2 - с шестым входом формирования нового сочета- ния УУ1. выход формирования нового сочетания которого соединенр с первым входом формирования нового сочетания БФС, информационные выходы УУ1 соединены с первыми информационными входами БФС, выход БНПВ является выходом окончания работы устройства, общий вход установки исходного состояния устройства соединен с ,

0 пятым входом БФП, четвертым входом БЗ и СИ, четвертым входом БС и ЗТГ, четвертым входом УУ2, четвертым входом БНПВ и вторыми информационными входами БФС, источник единичных сигналов соединен с

5 седьмым входом УУ1, вторые информацион.ные выходы БНПВ соединены с вторыми информационными входами БФС, информационные выходы БФС - с вторыми информационными входами БС и ЗТГ,

0 четвертый выход УУ2 - с вторым входом разрешения записи БФС, выход БФС - с третьим входом УУ2.

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

0 Устройство для решения комбинаторнологических задач на графах содержит генератор 1 тактовых импульсов, ключ 2, блок 3 формирования перестановок, блок 4 формирования сочетаний, устройство 5 управле5 ния блоком формирования сочетаний, блок 6 накопления планарных вершин, устрОйствоТуправления блоком накопления планарных вершин, блок 8 селекции и задания топологии графа, блок 9 записи и считывания информации, выход 10 окончания работы устройства, вход 11 установки исходного состояния, вход 12 источника единичных сигналов и входы 13 задания топологии графа. Генератор 1 через ключ 2 соединен с

5 первым входом блока 3, первым входом блока 8 и первым входом блока 9. Информаци- , онные выходы блока 3 подключены к информационным входам блока 9. Выход окончания перебора перестановок блока 3

0 соединен с пятым входом устройства 5 управления и вторым входом устройства 7 управления, Информационные выходы блока 4 связаны с информационными входами блока 6 и вторыми информационными входами блока 8. Первые информационные выходы блока 6 соединены с первыми информационными входами блока 8, вторые информационные выходы блока 6-синформационными входами блока 4. Первый выход блока 9 подключен к четвертому входу

установки в исходное состояние блока 3, второму входу установки в исходное состояние блока 8, четвертому входу устройства

5управления и первому входу блокировки устройства 7 управления. Второй выход блока 9 соединён с третьим входом сравнения блока 8. Выход блока 8 подсоединен к третьему входу формирования новой перестановки блока 3 и третьему входу установки в исходное состояние блока 9. Первый выход устройства 7 управления связан с первым входом записи первой планарной пятерки вершин блока 6, второй выход - с вторым входом блокировки непланарной вершины блока 6, третий выход - с третьим входом добавления новой вершины блока 6, четвертый выход - с первым входом записи четырех единиц устройства 5 управления и вторым входом разрешения записи блока 4, пятый выход - с вторым входом записи пяти единиц устройства 5 управления, вторым входом подключения шестого разряда блока 3 и вторым входом подключения шестого разряда и переключения коммутатора блока 9, шестой выход - с третьим входом устройства 5 управления, седьмой выход - с шестым входом устройства 5 управления, выход которого .соединен с первым входом формирования нового сочетания блока 4. Информа1 ионные выходы устройства 5 управления подключены к первым информационным входам блока 4. Выход блока 4 соединен с третьим входом устройства 7 управления. Выход. 10 блока 6 является выходом окончания работы устройства. Общий вход 11 установки исходного состояния устройства соединен с пятым входом блока 3, четвертым входом блока 9, четвертым входом блока 8, четвертым входом устройства 7 управления,четвертым входом блока

6и вторыми информационными входами блока 4,

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

Блок 4 содержит регистр 47, элементы ИЛИ 48,53 и 73, регистр 49 сдвига, элементы

70 и 72 задержки, переключатель 74, Каж-дый разряд блока 4, крЬме первого и последнего, содержит триггеры 54 и 59, элементы ИЛИ 55,67 и 68, элементы И 56,57,58,60,61,63 и 69 и формирователь 62

0 импульсов. Первый разряд блока 4 содержит указанные элементы, за исключением элементов ИЛИ 55,67 и 68 и элементов И 56,57 и 69. В последнем разряде отсутствуют элементы ИЛИ 67 и 68, элемент И 69 и

5 формирователь 62 импульсов. Кроме того, с первого по четвертый разряды блока 4 содержат элемент ИЛИ 51, а все, разряды с пятого по п-й содержат элемент И бб. Кроме того, разряды с третьего по п-й блока 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 (кроме

0 последнего триггера) соединен с первыми входами элементов И 61. Выход переключателя 71 подключен к входам первых элементов И 60 и 61. Выход i-ro элемента И 61 , п-1) соединен с входами соответствующих (i+1)-x элементов И 60 и 61. Выход последнего элемента И 61 связан с входом элемента ИЛИ 53. Выход i-ro элемента И 60 (1 2, п-1) соединен с первым входом 1-го элемента ИЛИ 68 и вторым входом i-ro эле-мента ИЛИ, 55. Выход первого элемента И

60 подключен к входу формироэателя импульсоаб2, второму входу элемента ИЛИ 68 и счетному входу первого триггера 54. Выход посл1гднегоэлемента И 60 соединен с вторым входом элемента ИЛИ 55. Первый выход регистра 47 связан с вторым входом элемента И 58. Второй, третий, четвертый регистра 47 соединены с вторыми входами элементов И 57 и 58 и вторыми инверсными входами элементов И 56 и 64. Остальные выходы регистра 47, кроме того, свяэаны с первыми инверсными входами элементов И 66. Единичный выход триггеров 54 соединен с вторым входом элементов И 63 и информационным входом триггеров 59.

Выходы 50 элементов И 63 являются информационными выходами устройства. Нулевой выход первого триггера 54 подключен к второму входу элемента И 55, нулевой выход i-го триггера 54 (1 2,п-1) к второму входу элемента ИЛИ 55 и первому входу элемента И 65, нулевой выход последнего триггера 54 - первому входу п-го элемента И 61, Выход элемента ИЛИ 55 соединен с входами элементов И 56 и 57. Выход элемента И 57 связан со счетным входом триггера 54. Выход i-ro элемента И 56 (I 1,п-1) соединен с третьим входом (i+1)-ro элемента ИЛИ 55 и вторым входом элемента ИЛИ 67, Выход последнего элемента И 56 подсоединен к входам элементов И 64 и 65. Выходы элементов И 65 соединены с входами элемента ИЛИ 53. выход 52 которого является выходом окончания перебора всех сочетаний. Выход 1-го элемента И 64 (i 3,п) соединен с входами (1-1)-х элементов И 64 и 65. Выход второго элемента И 64 соединен с входом первого элемента И 65: Выход элемента ИЛИ 68 соединен с первым входом соответствующих элементов И 69. Выход элемента ИЛИ 67 связан с вторым входом соответствующего элемента И 69. Выход 1-го элемента И 69 (1 1 ,п-1) соединен с входом соответствующего формирователя 62 и вторым входом (i+1)-ro элемента ИЛИ 68. Выход

последнего-элемента И 69 подсоединен к входу соответствующего формирователя 62. Выход i-ro формирователя 62 (i ; 1,п) соединен с i-м входом элемента ИЛИ 48, выход которого подключен к синхровходу регистра 49 сдвига.Второй вход i-ro элемента ИЛ И 51 (i 1 ,4) ивторые входы элементов И 58 и 66 соединены с информационными

входами устройства. Выход i-ro элемента И 66 связан с вторыми входами (1+1}-х элементов И 58 и 66.

Каждый разряд узлов 20 и 21 (кроме первого) содержит триггер 76, элементы ИЛИ 77 и 79 и элементы И 78 И 80. Первый

разряд выполнен только на триггере 76. При этом выход триггера 76 соединен с входом 1-го элемента ИЛИ 77 (I 1,п), второй вход которого связан с () элементом И 80, 5 выход элемента ИЛИ 77 соединен с первым входом элемента И 78 и первым входом элемента И ВО, второй инверсный вход которого подключен к выходу элемента ИЛИ 79, выход элемента ИЛИ 79 соединен также с

0 вторым входом соответствующего элемента И 78, выход которого подключен к D-входу i-ro триггера 76 (i 2,п). Синхровход триггера 76 соединнен с входом 81. R-вхбд i-ro триггера (1 2, п) и S-вход первого Триггера

5 связаны с входом 82. На D-вход первого триггера подается О. Первые входы элеменртов ИЛИ 79 соединены с входом 83, а вторые входы - с входом 84. Выходы 85 являются информационными выходами уст0 ройства.

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

5 и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени два одному из графов Пектрягина-Куратовского. Из теоремы следует что для определения планарности графа

0 из него необходимо последовательно выбирать всевозможные сочетания пяти- и шестивершинных подграфов и сравнивать их на изоморфизм с полносвязным пятивершинным (Gs) и двудольным шестивер5 шинным (граф Кенига бз.з) графами соответственно.

Для организации выбора из исследуемого графа 5- и 6-вершинных подграфов предлагается использовать формирователь

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

0 выбранных k разрядах из п разрядов (k п). Это позволит проводить формирование сочетаний не на всех разрядах, а только на тех, которые соответствуют рассматриваемым вершинам.

5 Дляопределения изоморфизма выбираемых 5- и 6-вершинных подграфов с полносвязным 5-вершинным и двудольным. 6-вершинным графами предлагается использовать процедуру полного перебора с помощью формирователя перестановок булевых переменных (т.е. выдача перестановок осуществляется в пространственно-временной форме). Целесообразно использовать наиболее простой алгоритм полного перебора, который аппаратно реализуется исключительно просто и требует всего 5 120 тактов при исследовании на изоморфизм 5-вершинных графов и 61 720 тактов при исследовании С-вершинных графов.

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

1.Подготовка устройства к работе. Для этого на вход 11 подается сигнал начальной установки. По этому же сигналу в БФС 4 в регистр 47 участия разрядов записываются все 1 и в первые пять разрядов также записываются 1. По входам 13 в БС и ЗТГ 8 заносится информация о топологии исследуемого графа.

2.Нахождение первой пятерки планарных вершин. Для этого в БФС 4 формируется сочетания пяти вершин, которое выделяет в БС и ЗТГ 8 из исходного графа пятивершинный подграф. С помощью БФП 3 и БЗ и С4 происходит сравнение этого подграфа с графом GB. ЕСЛИ произойдет поэлементное сравнение, то выбранный .подграф непланарен, в противном случае пять вершин данного подграфа планарны. Если подграф непланарен, то. формируется новое сочетание и работа продолжается аналогично.

3.Перепись информации из БФС 4 в БНПВ 6 и добавлений в БНВП 6 новой вершины.

4.3апись в регистр 47 БФС4 из БНПВ 6 информации. Разрешенными разрядами становятся разряды, определяемые информацией с БНПВ 6.

б.Запись по входу 12 четырех единиц в БФС 4, формирование в нем множества сочетаний Ck и определения с помощью БФП 3 и БЗ и СИ 9 для сочетания вершин графа изоморфизма графу GB (k - число вершин в БНПВ 6 на данном шаге).

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

7. В БФС 4 по входу 12 записывается пять единиц в первые пять разр ешенных разрядов. БФС 4 формирует сочетания вершин Ck. С помощью БФП 3 и БЗ и СИ 9 для каждого сочетания вершин графа определяется изоморфизм графу Сз.з.

8. обнаруживается непланарность какого-либо сочетания (т.е. изоморфизм в П.7), то в БНПВ 6 добавляется новая 1, а предыдущая блокируется, осуществляется

переход к 4. Если выбранное сочетание вершин планарно (т.е. изоморфизм в п.7 не обнаружен), то формируется следующее сочетание. По окончании перебора всех сочетаний происходит переход к п.9.

0 9. Если все вершины перебраны, то осуществляется переход к п. 10, шаг к п.4.

10. Конец работы устройства. На выходе 10 БНПВ б появляется сигнал окончания работы устройства.

5 Более подробно работу устройства рассмотрим по функциональной схеме (на фиг.2).

БЛОКОМ4формирования сочетаний генерируется лексикографическая последовательность сочетаний булевых переменных. При этоМ сначала формируются сочетания Сп , где п - число исследуемого графа. Каждое такое сочетание выбирает из блока 31с помощью узлов 20 и 21 соот5 ветствующую пятерку вершин. С помощью . блока 3 формирования перестановок, регистров 14 и 41 сдвига, ПЗУ 44 и 45, коммутаторов 16,17,42,43 и 46 и схемы 33 сравнения выполняется процедура проверки на изоО морфизм выбранной пятерки вершин и графа GS, информация о .котором хранится в ПЗУ 44. Первая найденная неизоморфная графу Gs, т.е. планарная, пятерка вершин переписывается в блок 6 накопления пла5 нарных вершин. Затем туда же добавляется новая вершиИа, и начк1нается процесс перебора сочетаний С е, причем перебор производится не по всем разрядам, а только п,о тем, которые соответствуют выбранным

0 вершинам (благодаря переписи из блока б комбинации рассматриваемых вершин в регистр 74, участия разрядов блока формирования сочетаний).

При каждом таком сочетании выполняется процедура контроля на изоморфизм. Если изоморфизм графу Gs ни в одной из всех пятерок сочетания С б не обнаружится, то осуществляется проверка на изоморфизм шестивершинного подграфа, вершины которого занесены в блок 6, и графа Ga.s, информация о котором хранится в ПЗУ 45. Если и теперь изоморфизм не обнаружен, то это означает, что выбранная пятерка вершин планарна. Поэтому дописанная к первоначальной пятерке вершин в блок б шестай вершина в нем не блокируется и к этой шестерке вершин добавляется новая седьмая вершина. В противном случае она блокируется, к первоначальной пятерке вершин вы бирается новая шестая вершийа.

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

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

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

Для худшего случая (когда исследуемый граф полностью планарный) числов всевозможных сочетаний пятерок и шестерок вершин соответственно составит:

Ni cVi;

N2 C%-1.

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

N 120(cVi +6CVi).

Рассмотрим в деталях динамику работы устройства для решения комбинаторно-логических задач.

Перед пуском устройства осуществляется подготовка его к работе. Для этого на вход 11 подается сигнал начальной установки, по которому блок 3 формирования перестановок, регистры 14 и 41, блок 6 накопления планарных вершин, узел 20, триггеры 24 и 28, устанавливаются в нулевое состояние, а в первый разряд узла 21 записывается единица. По этому же сигналу во все разряды регистра 47 блока 4 записываются 1 (т.е. первоначально все разряды формирователя сочетаний являются разрешенными) И в первые пять разрядов блока 4 формирования сочетаний заносятся Г, что соответствует исходному сочетанию 111110...0. По входам 13 в блок 31 задания топологии графа заносится информация о топологии исследуемого графа. После этого замыкается контакт 2 и тактовые импульсы (ТИ) начинают поступать на схему. Блок 3 формирования перестановок находится 3 исходном состоянии и при поступлении на него ТИ выдает единичные сигналы последовательно на входах 1,2,3,4,5.

Таким образом, по первому ТИ в блоке

3, регистре 14,и в узле 20 возбуждаются их первые разряды (т.е. единичные сигналы появляются на их первых разрядах). При этом ни из блока 44 памяти, ни из блока 31 считывания информации не происходит,

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

Если вершины, соответствующие первому и второму входам блока 31 связаны, то на одном из его выходов появляется единичный сигнал. Одновременно с этим из блока 44 памяти считывается 1 (так как в графе

Gs все вершины связаны), которая через коммутатор 46 и элемент ИЛИ 34 поступает на схему 33 сравнения. Поэтому схема 33 сравнения на своем выходе сигнал не вырабатывает. Если первая и вторая вершины исследуемого графа не связаны, то на выходе элемента ИЛИ 32 присутствует нулевой сигнал, схема 33 выдает на своем выходе сигна несравнения, по которому происходит установка в исходное состояние узла 20 через элементИЛИ 37 и узла 21 сначала через элемент ИЛИ 23 в нулевое состояние, а через 38 задержки и элемент ИЛ И 39 в исходное состояние (т.е. в первое). Этот же сигнал несравнения с

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

Положим, что сигнал несравнения по

второму ТИ на выходе схемы 33 не выработался. Поэтому по третьему ТИ аналогично описанному из блока 44 памяти и блока 31 считывается информация о смежности соответствующих вершин и. подается в схему

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

Допустим, что все пять элементов второй строки графа и первой строки исследуемого подграфа равны. Тогда сигнал несравнения на выходе схемы 33 не вырабатывается и очередной ТИ, появившись на выходе регистра 14, переводит 1, которая появляется на первом выходе коммутатора 17с первого выхода регистра 41 на его второй выход, а также единицу с первого выхода узла 21 на его второй выход (через элемент ИЛИ 39).

Таким образом, следующая пятерка ТИ последовательно считывает из блока памяти 44 элементы первой строки матрицы смежности графа Gs. а из блока 31 - элементы второй строки исследуемого пятивершинного подграфа и сравнивать их в схеме 33. Положим, что элементы этих строк равны. Тогда очередной ТИ устанавливает 1 в третьих разрядах регистра 41 и узла 21, а очередная пятерка ТИ коэлементно аналогично описанному сравнивает третьи строки матриц смежности из блока 44 и из блока 31.

Допустим, что во всех последующих строках также происходит поэлементное сравнение. Тогда по очередному ТИ на выходе регистра 41 появляется сигнал, свидетельствующий об изоморфизме пятивершинного подграфа, выбранного из исследуемого графа блоком 14 формирования, сочетаний, и графа GS. Поскольку граф Gs непланарен, то непланарен и выбранный подграф. Сигнал изоморфизма с выхода регистра 41 устанавливает в исходное состояние блок 3 формирования перестановок (через элемент ИЛИ 19), а в блоке 4 формирования сочетаний через логический элемент 2И-ИЛИ 18 устанавливает новое сочетание 1111010...0. Кроме того,

по этому сигналу узел 20 устанавливается в нулевое состояние. После этого начинается новый процесс определения изоморфизма (неизоморфизма) графа Gs и выбранного блоком 4 подграфа, состоящего в соответствии с сочетанием 1111010...О из 1-й,2-й,3-й, 4-й и 6-й вершин. Этот процесс протекает аналогично описанному с той разницей, что из-за подачи единиц с БФС 4 на 1-й,2-й,3-й,4-й и 6-й входы узлов

5 20 и 21 при последовательной подаче на их синхровходы ТИ единицы появляются последовательно на 1-м,2-м,3-м,4-м и 6-м выходах, т.е. именно на тех выходах, которые однозначно соответствуют сформированно0 му сочетанию 1111010...0.

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

0 перестановки. Сигнал окончания перебора всех перестановок появляется на выходе блока 3. Этот сигнал является признаком планарности выбранного с помощью блока 4 пятивершинного подграфа. Этот сигнал

5 через открытый элемент И 29 поступает на первый управляющий вход блока 6 накопления планарных вершин и переписывает содержимое блока 4 (т.е. 1111010...0) в блок 6. Кроме того, сигнал с выхода блока

0 3, пройдя открытый элемент И 29, поступает также через элемент ИЛИ 35 на первый ехид блока элементов И 15 (в результате этого от источника 12 единичных сигналов в первые четыре разряда блока 4 записываются 1). Через время задержки, достаточное для надежной переписи информации в блоке 6 (элемент 25 задержки), сигнал поступает на вход разрешения записи регистра блока 4 и переписывает в него

0 записанное в блоке 6 сочетание 1111010...О Гтаким образом, разрешенными разрядами, по которым производится перебор сочетаний, являются 1-й,2-й,3й,4-й,6-й разряды). После этого в блок 6

5 добавляется шестая единица, которая записывается в соседнмй разряд справа от f крайней правой единицы пленарной пятерки вершин. Поэтому после этого в блоке 6 записана информация 11110110...0. Причемтакая перепись в процессе работы и добавения единицы нужна только при первом оявлении сигнала на выходе блока 3 (т.е. ужно из Ьлока 4 переписать в блок 6 только первую планарную пятерку вершин).

Чтобы предотвратить такую перепись при последующих появлениях сигнала на выходе блока 3, задний фронт первого ТИ, поступая на единичный вход триггера 28, переводит его в единичное состояние. При этом закрываются элементы И 29 и первый (т.е. верхниЯ) элемент И узла 18, а открываются элемент И 30 и второй (т.е. нижний) элемент И узла 18. Поэтому в альнейшем смена сочетаний в блоке 4 происходит по сигналу с выхода блока 3 т.е. когда при данном сочетании перебраны все перестановки). Но этот сигнал в блок 6 же не поступает, поскольку элемент И 29 жеэакрыт.

В блоке 6 выделяются единицы старшего разряда и на первой шине выходов блика 6 имеется в данном случае унитарный код Od000010...0. Этрт код поступает на первые входы узлов 20 и 21.

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

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

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

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

1110010...О (а не 111010..., О, поскольку разрешенными являютс1я 1-й,2-й,3-й,4-й,6-й разряды для формирования сочетаний). Этот сигнал уже не проходит через элемент

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

0 изоморфизма графа Gs и подграфа, включающего 1,2,3,6,7 вершины.

Если выбранный подграф изоморфен графу GS (или впоследствии графу G3.3), то сигнал изоморфизма с выхода регистра 41

5 поступает через открытый элемент И 30 (так как после записи первой планарной пятерки вершин триггер 21 постоянно находится в единичном состоянии) на БНПВ 6, заблокирует на его выходе последнюю уставленную

0 вершину и в соседний разряд справа добавит новую единицу.

Предположим, что и это, и все последу ющие сочетания пятерок вершин из шести исследуемых, вплоть до сочетания 011101

5 неизоморфны графу Об. Так как пятый разряд является запрещенным, то это сочетание равносильно сочетанию 01111.

В данном случае, так как сочетание 011101, поскольку 5-й разряд запрещен, является последним, то при переднем импульсе на выходе блока 4 появляется сигнал об окончании формирования всех сочетаний. Этот сигнал перебрасывает триггер 24 в единичное состояние. На единичном выходе триггера 2 появляется сигнал, который поступает на второй вход блока элементов И 15 и на входы переключения емкости регистров 14 и 41 блока 3 и на вход коммута-. тора 46. В результате этого по входу 12 от

0 источника единичных сигналов ,в первые пять разрядов блока 4 записываются единицы, к регистрам 14,41 и блоку 3 подключаются шестые разряды, коммутатор .46 подключается к выходам блока 45 памяти.

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

0 45 памяти.

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

5 перестановке вырабатывался сигнал несравнения, Таким образом, перебирают все перестановки и на выходе блока 3 появляется сигнал окончания перебора всех перестановок. Этот сигнал через узел 18 поступит на вход бдока 4, в котором формируется новое сочетание. Поскольку первоначально в блоке 4 разрешены пять разрядов (1-й,2-й,37й;4-й,6-й) и во все эти разряды записаны 1, то это сочетание . является единственным, т.е. Cs. Поэтому при поступлении очередного сигнала в блок 4 с блока 3 на выходе блока 4 появляется сигнал об окончании формирования всех сочетаний. Этот сигнал поступает на счетный вход триггера 24 и переводит его в нулевое состояние. Этот же сигнал через элемент 27 задержки и открытый элемент И 26 поступает на третий вход блока 6 и записывает единицу в его 8-й разряд, а также череЗЭлемент ИЛИ 35 поступает на первый вход блока элементов И 15. В результате этого по входу 12 от источника единичных сигналов в первые четыре разряда блока 4 записываются единицы. Так как триггер 24 находится в нулевом состоянии, на его единичном выходе установлен нулевой потенциал if от регистров 14,41 и блока 3 отключены шестые разряды, а коммутатор 46 переключен к выходам блока 44 памяти. После этого начинается новый процесс анализа на планарностьсемивершинного графа, состоящего из вершин 1,2,3,4,6,7,8 аналогично описанному, т.е. сначала перебирают все сочетания по 5 из всех вершин, записанных в блоке б (при этом вершина 8 фиксируется,.а перебираются только четыре вершины из планарного подграфа, состоящего из вершин 1,2,3,4,6,7). Если при этом появляется хотя бь1 для одного сочетания сигнал изоморфизма, то 8-я вершина нарушает планарность подграфа, поэтому она блокируется на выходе блока 6, а новая единица записывается в 9-й разряд блока 6. Если сигнал изоморфизма не появляется, то схема переходит к формированию всех сочетаний по 6 из всех вершин, записанных в блоке 6. Если нарушений планарности не обнаружено, тО на третий вход блока 6 поступает сигнал планарности, по которому в 9-й разряд записывается единица, а 8-я вершина не блокируется./

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

На фиг.З приведен вариант выполнения функциональной схемы блока формирования сочетаний на произвольно выбранных k разрядах (), причем последовательность разрядов является произвольной.

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

Каждое очередное сочетание получается из предыдущего путем перевода гл левых следующих подряд единичных разрядов в О, а первого правого нулевого

разряда-в 1 и последующего восстановления в (m-l)-x крайних левых разрядах единиц. Если в р левых разрядах стоят , нули, то осуществляется обход этих разрядов и в О переводятся m подряд следующих единичных разрядов начиная с (р+1}-го разряда, а (р+т+1)-й разряд переводится в 1. При этом независимо от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстанавливаются (т-1) левых разрядов. Если имеется п разрядов, а необходимо сформировать сочетания из k разрядов ()t то вводится запрет на использование ненужных раЗ;рядов, и происходит обход запрещенных разрядов. Запрещенными могут быть любые разряды.

Перевод в единицу нулевого разряда, которому предшествует группа из подряд следующих единичных разрядов, происходит в триггерах 54. Восстановление единиц обеспечивается триггерами 59 с элементами И 60,61 и 69, формирователями 69 и элементами ИЛИ 67 и 68. Элементы ИЛИ 51, И 56-58 и регистр 47 обеспечивают обход

0 запрещенных разрядов. Элементы И 64 и 65 и ИЛИ 53 обеспечивают окончание работы устройства после формирования всех сочетаний. На выходе 50 элементов И 63 снимаются сочетания после окончания пе5 рвходных процессов.

Перед началом работы в регистр 47 заносится комбинация участия разрядов в формировании сочетаний. Если разряд участвует в формировании сочетаний, в со0 оответствующий разряд регистра 47 записывается 1, в противном случае - О.

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

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

0 функции коммутатора в предлагаемом устройстве выполняет блок перебора сочетаний.

Кроме того, предлагаемое устройство более функционально надежно, так как в

5 нём используется более надежная схема узлов последов.ательного опроса разрядов, i блок перебора сочетаний.

Формула изобретения Устройство для решения комбинаторнологических задач на графах, содержащее генератор тактовых импульсов, ключ, блок управления формированием сочетаний, блок формирования перестановок, блок накопления планарных вершин, блок управления накоплением планарных вершин, блок селекции и задания топологии графа и блок записи и считывания информации, причем выход генератора тактовых импульсов подключен через ключ к счетным входам блока формирч.эания перестановок, блока селекции и задания топологии графа и блока записи и сч/.тывания информации, информационные выходы блока формирования перестанЬв-,х г дключены к информационным входам олрка записи и считывания информации, выход окончания перебора всех перестановок блока формирования перестановок подключен к входу формирования нового сочетания блока управления формированием сочетаний и входу записи первой планарной пятерки блока управления накоплением планарных вершин, информационные выходы блока формирования сочетаний подключены к информационным входам блока накопления планарных вершин, первые информационные выходы которого подключены к первым информационным входам блока селекции и задания топологии графа, первый выход изоморфизма полному пятивершинному графу блока записи и считывания информа. ции подключен к входам установки в исходное состояние блока формирования перестановок и блока селекции и задания топологии графа, входу формирования нового сочетания блока управления формированием сочетаний и входу блокировки непланарной вершины блока управления накоплением планарных вершин, выход смежности блока записи и считывания информации подключен к входу сравнения блока селекции и задания токологии графа, выход несравнения которого подключен к входу формирования новой перестановки блока формирования перестановок и входу установки в исходное состояние блока записи и считывания информации, выход записи первой планарной вершины блока управления накоплением планарных вершин подключен к входу записи первой планарной пятерки блока накопления планарных вершин, выход блокировки непланарной вершины блока управления накоплением планарных вершин подключен к одноименному входу блока накопления планарных вершин, выход добавления новой вершины блока управления накоплением планарных вершин - к одноименному входу блока накопления планарных вершин, выход записи четырех единиц блока управления накоплением планарных вершин - к одноименному входу блока управления формированием сочетаний, выход проверки изоморфизма шестивершинному двудольному графу Кенига блока управления накоплением планарных вершин подключен к входу записи пяти еди ниц блока управления формированием сочетаний, входу подключения шестого разряда блока формирования перестановок и входу подключения шестого разряда и переключения коммутатора блока записи и считывания информации, выход переключения блока управления накоплением планарных вершин подключен к входу формирования нового сочетания блока управления формированием сочетаний, выход формирования нового сочетания которого полключен к одноименному входу блока формирования сочетаний, первые информационные входы которого подключены к информационным выходам блока управления формированием сочетаний, управляющий выход блока накопления планарных вершин является выходом признака окончания работы устройства, общий вход ус;тановки исходного состояния устройства подключен к одноименным входам блока формирования перестановок, блока записи и считывания информации, блока селекции и задания топологии графа, блока управления накоплением планарных вершин, блока накопления планарных вершин и вторым информационным входам блока формирования сочетаний, вход единичных . сигналов блока управления формированием сочетаний является входом для подключения источника единичных сигналов устройства, отличающееся тем, что, с целью уменьшения аппаратурных затрат, вторые информационные выходы блока накопления планарных вершин подключены к вторым информационным входам блока формирования сочетаний, информационные выходы которого подключены к вторым информационным входам блока селекции и задания топологии графа,выход записи четырех единиц блока управления накоплением планарных вершин подключен к входу разрешения записи блока формирования сочетаний, управляющий выход которого подключенкодноименному входу блока управления накоплением планарных верц1ин.

uogisd€rj(f unnJoifJBdvj}

r о o

01

t-

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