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

 

Изобретение относится к вычислительной технике и может быть использовано для выделения планарной части схемы при автоматизированном проектировании электронных схем. Целью изобретения является уменьшение аппаратурных затрат. Задача выделения планарной части графа (планарной части схемы) решается путем перебора возможных сочетаний вершин и проверки их планарности. Алгоритм перебора сочетаний позволяет уменьшить аппаратурные затраты по сравнению с известным устройством и исключить некоторые заведомо неподходящие сочетания. 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, поскольку раз- и яв о лении сигнала на выходе блока 3 (т.е. решенными являются 1-й,2-й,З-й,4-й,6-й ч т.аний). нужно из лока и

Ь к 4переписать вблок6только разряды для формирования сочета ). первую планарную пятерку вершин). Этот сигнал уже не проходит чер

Чтобы предотвратить такую перепись 5 И 29 на.первый входбйока 6, так как элемент при последующих появлениях сигнала на И 29 был открыт для прохождения только выходе блока 3, задний фронт первого ТИ, первого сигнала с выхода блока 3. Поэтому поступая на единичный вход. триггера 28, вблокебникакихизмененийнепроисходит, переводит его в единичное состояние. а начинается новый процесс установления, При этом закрываются элементы И 29 и 10 изоморфизма графа Gs и подграфа, включапервый (т,е. верхний) элемент И узла 18, ющего 1,2,3,6,7 вершины. а открываются элемент ИЗОи второй(т.е. Если выбранный подграф изоморфен й) элемент И узла 18. Поэтому в графу Gs.(или впоследствии графу 6з,з), то дальнейшем смена сочетаний в блоке 4 сигнал изоморфизма с выхода ре р гист а 41 происходит по сигналу с выхода блока 3 15 поступаетчереэоткрытыйэлементИЗО(так (т.е. когда при данном сочетании перебраны как после записи первой пленарной пятерки . все перестановки), Но этот сигнал в блок 6, вершин триггер 21 постоянно находится в уже не поступает, поскольку элемент И 29. единичном состоянии) на БНПВ 6, заблокиуже закрыт. рует на его выходе последнюю уставленную оба-, В блоке 6 выделяются единицы старше- 20 вершину и в соседний разряд справа до а-, го разряда и на йервой шине выходов блока вит новую единицу.

6 имеется в данном случае унитарный код Предположим, что и это, и все последу.—

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

Так как в первые четыре разряда блока 25 неизоморфны графу Gs. Так как пятый раз4 нь единицы то он последовательно ряд является запрещенным, то это сочетазаписа ию 01111. формирует-сочетанияиз "5" по "4". Посколь- ние равносильно сочетанию ку на левые входы блоков 20 и 21 с блока 6 В данном случае, так как сочетание подается код 1111010...0, то единицы перво- 011101, поскольку 5-й разряд запрещен, явго сочетания 11110...0 с выхода блока 4, 30 ляется последним, то при переднем импульоказываются на первых четырех входах уз- се на выходе блока 4 появляется сигнал об ,лов и

20 21.Сучетомтого чтов7-хразрядах окончании формирования, всех сочетаний.

24 в

20 и 21 находятся единицы, то общее Этот сигнал перебрасывает триггер в узлов и сочетание, поданное на входы узлов 20 и 21 единичное состояние. На единично ом выхследующее 11110010...0. 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 сравнени ние матриц смежности для графа Gs ся шестые разряды, коммутатор . ! к 45 памяти. и исследуемого подграфа, включающего подключается к выходам блока и вершины 1,2,3,4,7. 45 Теперь при поступлении ТИ в схему поэлеЕсли в какой-то момент времени на вы- ментно и синхронно считывается из блока ходе схемы в емы 33 вырабатывается сигнал не- 31 матрица смежности исследуемого подсравнения (т.е. неиэоморфизма), то по этому графа, включающего вершины сигналу блок 3 формирует вторую переста- а матрица смежности графа 6з,з — из блока новку 2,1,3,4,5 и начинается новый процесс 50 45 памяти. сравнения матриц смежности. Предположим, что эти графы неизоПредположим, что, перебрав все-5 пере- морфны, т.е. в процессе считывания элестановок; при каждой из них на выходе схе- ментов матриц смежности и сравнения их мы 33 вырабатывался сигнал несравнения элементов на выходе схемы 33 при каждой (неизоморфизма). Тогда на выходеблока 3 55 перестановке вырабатывался сигнал непоявляется сигнал окончания перебора сравнения. Таким образом, перебирают всех перестановок при данйом сочетании. все перестановки и на выходе лока поЭ л поступает через открытый является сигнал окончания перебора всех тот сигнал по т игнал че еэ зел 18 верхний элемент узла 18 на вход блока 4, перестановок. Этот сигнал через узел который формирует новое сочетание поступитнавходблока4, вкоторомформи1709349

10

15 навливаются (m-1) левых разрядов. Если имеется и разрядов, а необходимо сформи20

40

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

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

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

Формула изобретения

Устройство для решения комбинаторнологических задач на графах, содержащее геруется новое сочетание. Поскольку первоначально в блоке 4 разрешены пять разрядов (1-й,2-й,3-й, 4-й,б-й) и во все эти разряды записаны "1", то это сочетание ., является единственным, т.е. Сзв, Поэтому при поступлении очередного сигнала в . блок 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). Если при этом появляется хотя бы для одного сочетания сигнал изомор- 3 физма, то 8-я вершина нарушает планар- ность подграфа, поэтому она блокируется на выходе блока 6, а новая единица записывается в 9-й разряд блока 6. Если сигнал изоморфизма не появляется, то схема переходит к формированию всех сочетаний по

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

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

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

Каждое очередное сочетание получается из предыдущего путем перевода m левых следующих подряд единичных разрядов в "0", а первого правого нулевого разряда — в "1" и последующего восстановления в (m-1)-х крайних левых разрядах единиц. Если в р левых разрядах стоят нули, то осуществляется обход этих разрядов и в "0" переводятся m подряд следующих.единичных разрядов начиная с (р+1)-го разряда, а (р+п +1)-й разряд переводится в

"1". При этом независимо от того, с каких разрядов начинается их перевод в нулевое состояние, в единичное состояние восстаровать сочетания из k разрядов (k n), то вводится запрет на использование ненужных разрядов, и происходит обход запрещенных разрядов, Запрещенными могут быть любые разряды.

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

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

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

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

1739349

22 нератор тактовых импульсов, ключ, блок управления формированием сочетаний, блок формирования перестановок, блок накоп-, ления планарных вершин, блок управления накоплением планарных вершин, блок селекции и задания топологии графа и блок записи и считывания информации, причем выход генератора тактовых импульсов подключен через ключ к счетным входам блока формир,. ээния перестановок, блока селекции и задания топологии графа и блока записи и чятывания информации, информационные выходы блока формирования перестанos=x г адключены к информационным входам блока записи и считывания информации, выход окончания перебора всех перестановок блока формирования перестановок подключен к входу формирования нового сочетания блока управления формированием сочетаний и входу записи первОй планарной пятерки блока управления накоплением планарных вершин, информационные выходы блока формирования сочетаний подключены к информационным входам блока накопления планарных вершин, первые информационные выходы которого подключены к первым информационным входам блока селекции и задания топологии графа, первый выход изоморфизма полному пятивершинному графу блока записи и считывания информа, ции подключен к входам установки в исходное состояние блока формирования перестановок и блока селекции и задания топологии графа, входу формирования нового сочетания блока управления формированием сочетаний и входу блокировки непланарной вершины блока управления накоплением планарных вершин, выход смежности блока записи и считывания информации подключен к входу сравнения блока селекции и задания топологии графа, выход несравнения которого подключен к входу формирования новой перестановки блока формирования перестановок и входу установки в исходное состояние блока записи и считывания информации, выход записи первой планарной вершины блока управления накоплением планарных вершин подключен к входу записи первой планарной пятерки блока накопления планарных вершин, выход блокировки непланарной вершины блока управления накоплением планарных вершин подключен к одноименному входу блока накопления планарных вершин, выход добавления новой вершины блока управле1 ния накоплением планарных вершин — к одноименному входу блока накопления планарных вершин, выход записи четырех единиц блока управления накоплением пла5 нарных вершин — к одноименному входу блока управления формированием сочетаний, выход проверки изоморфизма шестивершинйому двудольному графу Кенига блока управления накоплением планарных, 10 вершин подключен к входу записи пяти единиц блока управления формированием сочетаний, входу йодключения шестого разряда блока формирования перестановок и входу подключения шестого разряда

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

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

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

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

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

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

1709349

1709349

1709349

l40gsdf vd

sntnmhgavp y гРедактор Л. Пчолинская Техред M,Mîðãåíòàë Корректор М. Демчик

Заказ 428 Тираж Подписное

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

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

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