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

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

Иллюстрации

Показать все

Реферат

 

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

союз советских

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

РЕСПУБЛИК (я)з G 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4812836/24 (22) 09.04.90 (46) 30.01.92. Бюл. ЬВ 4 (71) Таганрогский радиотехнический институт им. В.Д, Калмыкова (72) В.M. Глушань, В .M. Курейчик и С.И. Макеев (53) 681.333(088.8) (56) Авторское свидетельство СССР

Я 482751, кл. G 06 F 15/20, 1973, Авторское свидетельство СССР

M 1517036,.кл. G 06.F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ КОМ6МНАТОРЦО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

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

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

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

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

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

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

Наиболее близким к предлагаемому является устройство для решения комбина-.

1709349

15

35 управления блоком накопления планарных вершин соединен с вторым входом

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

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

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

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

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

1709349 вершины УУ2 соединен с первым входом записи первой планарной пятерки вершин

БНПВ,-второй выход блокировки непланарной вершины УУ2 соединен с вторым входом блокировки непланарной вершины

БНПВ, третий выходдобавления новой вер-. шины УУ2 соединен с третьим входом добавления новой вершины БНПВ, четвертый выход записи четырех единиц УУ2 соединен с первым входом записи четырех единиц

УУ1, пятый выход проверки изоморфизма шестивершинному двупольному графу Кенига УУ2 соединен с вторым входом записи пяти единиц УУ1, вторым входом подключения шестого разряда БФП и вторым входом подключения шестого разряда и переключе-. ния коммутатора БЗ и СИ, шестой выход переключения УУ2 соединен с третьим входом формирователя нового сочетания УУ1, седьмой выход переключения УУ2 — с шес45

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

УУ1 и первым входом блокировки непланарной вершины УУ2, второй выход смежности

БЗ и СИ соединен с третьим входом сравне- 35 ния БС и ЗТГ, выход несравнения БС и ЗТГ соединен с третьим входом формирования новой перестановки БФП и третьим входом установки в исходное состояние 63 и СИ, первый выход записи первой планарной 40 тым входом формирования нового сочетания УУ1, выход формирования нового сочетания которого соединенр с первым входом формирования нового сочетания БФС, информационные выходы УУ1 соединены с первыми информационными входами БФС, выход БНПВ является выходом окончания работы устройства, общий вход установки исходного состояния устройства соединен с пятым входом БФП, четвертым входом БЗ и

СИ, четвертым входом БС и ЗТГ, четвертым входом УУ2, четвертым входом БНПВ и вторыми информационными входами БФС, источнйк единичных сигналоЬ соединен с седьмым входом УУ1, вторые информацион,ные выходы БНПВ соединены с вторыми информационными входами БФС, информационные- выходы-БФС вЂ” с вторыми информационными входами БС и ЗТГ, четвертый выход УУ2 — с вторым входом разрешения записи БФС, выход БФС вЂ” с третьим входом УУ2.

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

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

6 накопления планарных вершин, устройство 7управления блоком накопления планарных вершин, блок 8 селекции и задания топологии графа, блок 9 записи и считывания информации, выход 10 окончания работы устройства, вход 11 установки v:ñõoäíîão состояния, вход 12 источника единичных . сигналов и входы 13 задания топологии графа. Генератор 1 через ключ 2 соединен с первым входом блока 3, первым входом блока 8 и первым входам блока 9. Информаци-, онные выходы блока 3 подключены к информационным входам блока 9. Выход окончания перебора перестановок блока 3соединен с пятым входом устройства 5 управления и вторым входом устройства 7 управления. информационные выходы блока 4 связаны с информационными входами блока 6 и вторыми информационными входами блока 8. Первые информационные выходы блока 6 соединены с первыми информационными входами блока 8, вторые информационные выходы блока 6-с информационными входами блока 4. Первый выход блока 9 подключен к четвертому входу

1709349 управления. Выход 10 блока 6 является выходом. окончания работы устройства. Общий 35

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, элементы lflJllfl 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

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. Выход l-го элемента И 61 (l = 1, и-1) соединен с входами соответствующих (i+1)-õ элементов И 60 и 61. Выход последнего элемента И 61 связан с входом элемента ИЛИ 53. Выход l-ro элемента И 60 (i = 2, и-1) соединен с первым входом l-ro элемента ИЛИ 68 и вторым входом l-го эле-. мента ИЛИ. 55. Выход первого элемента И

1709349

10 выход которого подключен к синхровходу регистра 49 сдвига. Второй вход i-ro элемента ИЛИ 51 (!.= 1,4} и вторые входы элементов

И 58 и 66 соединены с информационными входами устройства. Выход I-ro элемента И

66 связан с вторыми входами (i+1)-х элементов И 58 и 66, Каждый оазряд узлов 20 и 21 (кроме первого) содержит триггер 76, элементы

ИЛИ 77 и 79 и элементы И 78 и 80. Первый

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, нулевой выход i-го триггера 54 (I = 2,п-1) — .20 к второму входу элемента ИЛИ 55 и первому входу элемента И 65, нулевой выход последнего триггера 54 — первому входу и-ro элемента И 61. Выход элемента ИЛИ 55 соединен с входами элементов И 56 и 57. 25

Выход элемента И 57 связан со счетным входом триггера 54. Выход i-ro элемента И

56 {! =1,п-1) соединен с третьим входом (!+1)-го элемента ИЛИ 55 и вторым входом элемента ИЛ И 67. В ыход последнего эле- 30 мента И 56 подсоединен к входам элементов И 64 и 65. Выходь| элементов И 65 соединены с входами элемента ИЛИ 53, выход 52 которого является выходом окон чания перебора всех сочетаний. Выход I-ro 35 элемента И 64 (i = З,п) соединен с вхоДами (i-1)-х элементов И 64 и 65. Выход второго элемента И 64 соединен с входом первого элемента И 65. Выход элемента ИЛИ 68 соединен с первым входом соответствую- 40 щих элементов И 69. Выход элемента ИЛИ

67 связан с вторым входом соответствующего элемента И 69. Выход i-ro элемента

И 69 (I = 1,п-1) соединен с входом соответствующего.формирователя 62 и вторым 45 входом (i+1)-го элемента ИЛИ 68. Выход ,последнего. элемента И 69 подсоединен к входу соответствующего формирователя

62. Выход i-ro формирователя 62 (! =. 1,п) соединен с l-м входом элемента ИЛИ 48, 50,> разряд выполнен только на триггере 76; При этом выход триггера 76 соединен с входом !

-го элемента ИЛИ 77 (i - 1,n), второй вход которого связан с (i-1)-м элементом И 80, выход элемента ИЛИ 77 соединен с первым входом элемента И 78 и первым входом элемента И 80, второй инверсный вход которого подключен к выходу элемента ИЛИ 79, выход элемента ИЛИ 79 соединен также с . вторым входом соответствующего элемента

И 78, выход которого подключен к 0-входу !

-го триггера 76 (i = 2,п). Синхровход триггера 76 соединнен с входом 81. R-вход I-ro триггера (i - 2, n) и S-вход первого триггера связаны с входом 82. На 0-вход первого триггера подается "0". Первые входы элеменртов ИЛИ?9 соединены с входом 83, а вторые входы — с входом 84. Выходы 85 являются информационными выходами устройства.

Принцип работы устройства основан на

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

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

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

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

6-вершинным графами предлагается ис-. пользовать процедуру полного перебора с помощью формирователя перестановок бу1709349

12 левых переменных (т.е. выдача перестановок осуществляется в пространственно-временной форме). Целесообразно использовать наиболее простой алгоритм полного перебора,,который. аппаратно реализуется исключительно просто и требует. всего 5! = 120 тактов при исследовании на изоморфизм

5-вершинных графов и 6l = 720 тактов при исследовании C-вершинных графов.

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

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

8 заносится информация о топологии исследуемого графа.

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

Если подграф непланарен, то формируется новое сочетание и работа продолжается аналогично.

З,Перепись информации из БФС 4 в

БНПВ 6 и добавления в БНВП 6 новой вершины.

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

5.Запись по входу 12 четырех единиц в

БФС 4, формирование в нем множества сочетаний С и определения с помощью БФП

3 и БЗ и СИ 9 для каждого сочетания вершин графа изоморфизма графу Ов (k — число вершин в БНПВ 6 на данном шаге).

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

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

40

50 рого занесены в блок 6, и графа 6з,з, инфор55

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. Первая найденная неизоморфная графу Gg, т.е. планарная, пятерка вершин переписывается в блок 6 накопления планарных вершин. Затем туда же добавляется новая вершина, и начинается процесс перебора сочетаний С 6, причем перебор произ5 водится не по всем разрядам, а только по тем, которые соответствуют выбранным вершинам (благодаря переписи из блока б комбинации рассматриваемых вершин в регистр 74, участия разрядов блока формирования сочетаний).

При каждом таком сочетании выполняется процедура контроля на изоморфизм.

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

1709349

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

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

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

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

N1 С и-1;

NZ=С п-1.

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

N = 120(С п-1 + 6С п-1).

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

Перед пуском устройства осуществляет- 40 ся подготовка его к работе. Для этого на вход 11 подается сигнал начальной установки, по которому блок 3 формирования перестановок, регистры 14 и 41, блок 6 накопления планарных вершин, узел 20, триг- 45 геры 24 и 28.устанавливаются в нулевое состояние, а в первый разряд узла 21 записывается единица. По этому же сигналу во все разряды регистра 47 блока 4 записываются "1" (т,е. первоначально все разряды 50 формирователя сочетаний являются разрешенными) и в первые пять разрядов блока 4 формирования сочетаний заносятся

"1", что соответствует исходному сочетанию

111110...0, По входам 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" (так как в графе

G5 все вершины связаны), которая через коммутатор 46 и элемент ИЛИ 34 поступа- . ет на схему 33 сравнения. Поэтому схема

33 сравнения на своем выходе сигнал не вырабатывает. Если первая и вторая вершины исследуемого графа не связаны, то на выходе элемента ИЛИ 32 присутствует нулевой сигнал, схема 33 выдает на своем выходе сигнал несравнения, по которому происходит установка в исходное состояние узла 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. Если в регистрах

1709349

1

14 и 41 сдвига по каждому ТИ на их входах

"1" всегда последовательно переходит с предыдущего разряда на последующий, то нэ выходах коммутаторов 16 и 17 единицы появляются на их выходах в последовательности, определяемой перестановкой, сформированной блоком 3. Так, вторая перестановка 2,1,3,4,5 приводит к тому, что единица с первого выхода регистра 14 проходит на второй выход коммутатора 16 и, соответственно, на второй вход блока 44 памяти. Единица с второго выхода регистра 14 проходит на первый выход коммутатора 16, с третьего — на третий, с четвертого — на четвертый и с пятого — на пятый, Единица с первого выхода регистра

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

17. Таким образом, из блока 44 памяти последовательно считываются элементы второй строки матрицы смежности графа

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

4 формирования сочетаний.

Допустим, что все пять элементов второй строки графа и первой строки исследуемого подграфа равны, Тогда сигнал несравнения на выходе схемы 33 не выра.батывается и очередной.ТИ, появившись на выходе регистра 14, переводит "1", которая появляется на первом выходе коммутатора

17 с первого выхода регистра 41 íà его вто-рой выход, а также единицу с первого выхода узла 21 íà его второй выход (через элемент ИЛИ 39).

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

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

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

G5 непланарен, то непланарен и выбранный подграф. Сигнал изоморфизма с выхода регистра 41 устанавливает в исходное состояние блок 3 формирования перестановок (через элемент ИЛИ 19), а в блоке 4 формирования сочетаний через логический элемент 2И-ИЛИ 18 устанавливает новое сочетание 1111010...0. Кроме того, по этому сигналу узел 20 устанавливается в нулевое состояние. После этого начинается новый процесс определения изоморфизма (неизоморфизма) графа Gg u выбранного блоком 4 подграфа, состоящего в соответствии с сочетанием 1111010...0 из 1-й,2-й,З-й, 4-й и 6-й вершин. Этот процесс протекает аналогично описанному с той разницей, что иэ-за подачи единиц с

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

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

25 на выходе схемы 33 появляется сигнал несра вн ения (не изоморфизма), которы й. устанавливает каждый раз новую перестановку. При этом перебирают все перестановки. Сигнал. окончания перебора всех перестановок появляется нэ выходе блока 3. Этот сигнал является признаком планарности выбранного с помощью блока

4 пятивершинного подграфа. Этот сигнал

30 через открытый элемент И 29 поступает на первый управляющий вход блока 6 накопления планарных вершин и переписывает

35 содержимое блока 4 (т.е. 1111010...0) в блок б. Кроме того, сигнал с выхода блока

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

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

50 добавляется шестая единица, которая зэписывается в соседний разряд справа от крайней правой единицьь планарной пятерки вершин. Поэтому после этого в блоке 6 записана информация 11110110...0. Причем такая перепись в процессе работы и добавБФС 4 на 1-й,2-й,Ç-й,4-й и б-й входы узлов

15 20 и 21 при последовательной подаче на их

18

1709349

17

j ления единицы нужна только при первом 1110010...0(a не 111010...,0, поскольку раз- и яв о лении сигнала на выходе блока