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

 

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

Социалкстнческик

Республик к авторском свидетельств (5I ) Дополнительное к авт. свид-ву (22) Заявлено 30. 11 79 (21) 2870565/18-. 24 с присоеяинением заявки РЙ (23) Приоритет

Опубликовано 30. 10. 81 ° Бюллетень йе 40 (5! )М. Кл.

G 06 F 15/20

Гооуаарствеииый комитет по делам иэобретеиий и открытий (53) УДК 681.333 (088.8) Дата опубликования описания 30. 10. 81

; ° 1;

А.П. Германюк, В.А. Калашников, В.А. Литв

Е.А.Ралдугин и Н.В.Федотов (72) Авторы изобретения

Институт электродинамики АН Украинской радиотехнический институт им. В.Д.Калмыкова (71) Заявители (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ

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

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

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

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

15 максимальные полные подграфы.

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

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

;вый и второй элементы И, первый и вто рой элементы НЕ,а в,каждую модель вершины введены третий элемент ИЛИ, седьмой элемент И и кольцевой регистр, причем в каждой модели вершины первый выход кольцевого регистра подключен к первому входу пятого элемента И и к входу первого элемента НЕ, выход

25 которого соединен с первым входом òðå тьего элемента ИЛИ, выход которого является первым выходом модели вершины, выход пятого элемента И является вторым, выходом модели вершины и подключен к второму входу третьего эле30 мента ИЛИ и к первому входу третьего элемента. И, первый вход шестого элемента И .соединен с первыми входами первого, седьмого и второго элементов

И и является первым входом модели вер- 35 шины, вторым входом которой является второй вход шестого элемента И, выход которого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевым входом 40 второго триггера, со вторым входом четвертого элемента И и. является третьим входом модели вершины, четвертым входом которой является третий вход первого элемента И, второй вход седьмого эле- 4s мента И соединен со вторыми входами .второго и третьего элементов И и является пятым входом модели вершины, третий вход второго элемента И соединен с третьим входом третьего элемента И, 50 входом второго элемента НЕ и является шестым входом модели вершины, седьмым входом которой является третий вход седьмого элемента И, четвертый вход которого подключен к выходу второго эле- 5 мента НЕ, выход четвертого элемента И соединен с нулевым входом первого триггера и со вторым входам первого эле4 мента ИЛИ, выход которого подключен к установочному входу кольцевого регистра, второй выход которого соединен с входом блока индикации, выход второго триггера подключен к второму входу пятого элемента И, единичный вход второго триггера является .восьмым входом модели вершины, девятым входом которой является сдвиговый вход кольцевого регистра,. выход седьмого элемента И подключен к третьему входу первого элемента ИЛИ. вторые выходы всех моделей вершин соединены с входами многовходового элемента ИЛИ, выход которого подключен к седьмым входам всех моделей вершин, к входу первого элемента НЕ, к второму входу блока управления и к первому входу первого элемента И, выход которого соединен с шестыми входами моделей вершин, первые выходы моделей вершины подключены к входам второго элемента И, выход которого соединен с входом второго .элемента

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

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

Устройство для исследования графов содержит модель I 1.-ой вершины исследуемого .графа, блок 2 управле— ния, сдвиговый регистр 3, второй 4 и первый 5 элементы И, элемент ИЛИ б, второй 7 и первый 8 элементы HE в состав каждой модели 1„вершины входят второй 9 и первый 10 триггеры, шестой, первый, седьмой, пятый, второй, третий и четвертый элементы

И II-17, первый, второй и третий .элементы ИЛИ I8-20, первый и второй элементы НЕ. 21 и 22, кольцевой регистр

23, блок 24 индикации, входы и выходы модели вершин и блока управления являются полюсами 25-44.

Блок 2 управления (фиг. 2) содержит элементы ИЛИ 45 и 46, элементы

15

25

5 87

И 47-52, элементы НЕ 53-55, генератор 56 импульсов и триггер 57.

Получение решения задачи на устройстве производится в результате выбора в произвольном порядке Х вершины графа, определения множества вершин С =S1ÏГ11 формирования максимальных полйых подграфав, которое состоит из проверки множества С на возможность включения его в формируемые максимальные полные подграфы и пометки вершин, входящих в эти подграфы. При этом под S; подразумевается с -ый максимальный полный подграф графа а à — отображение вершины у С

Х„ в графе.

Произвольный выбор вершин X„ осуществляет сдвиговый регистр 3, разрядные выходы которого в произвольном порядке соединены с полюсами 28 моделей ll вершин.

Множества вершин С„ формируются в результате совместной работы всех моделей 1 вершин, которые соединены между собой полюсами 25 и 26 согласно конфигурации исследуемого графа.

При этом в каждой модели используются элемент И 14, элемент НЕ 21, элемент ИЛИ 20, триггер 9 и кольцевой регистр 23.

Одновременно с определениеммножества С, происходит его проверка на возможность включения в максимальный .полный подграф. При этом возможно выполнение следующих условий:

С„.=S,.; С„. = ; С1 WS; Ф.

Выполнение первого условия свидетельствует о том, что в максимальный полный подграф S ° включается Х1, вер1 шина и-"в результате формируется S 1 максимальный полный подграф.

Выполнение второго и третьего условий свидетельствует о том, что в формируемый S 1+ ìàêñèìàëüíûé полный подграф включается без изменения S подграф. Кроме того, при выполнении третьего условия формируется специальное множество вершин. В это множество вершин относят вершины С и вершину Х . После того как сформирован 5„ 1 подграф, в него до11олнительно включают те вершины из специального множества, которые не являются его элементами.

Проверку условий осуществляют элементы И 4 и ИЛИ 6. Специальное множество вершин формируется элементами

И 5 и НЕ 7 и в каждой модели 1 триг1 герои 10, элементами HE 8, И 15 и 16 °

7552 6

Для пометки вершин, входящих в максимальный полный подграф, используются элементы И 12 и 13, элемент ИЛ11 18 и кольцевой регистр 23 в каждой моде" ли 1 . При этом для пометки вершин, принадлежащих формируемому подграфу, используются разряды кольцевых регистров 23 всех моделей l„. Наличие единицы в том или ином разряде этого регистра одной из моделей 1; свидетельствует о принадлежности этой вершины тому или иному максимальному полному подграфу.

В результате проверки элементы

И 4 и ИЛИ б выдают сигналы, которые поступают в блок 2 управления, который по этим сигналам выдает на свои выходные полюса синхронизирующие импульсы, обеспечивающие синхронную работу всех моделей I. вершин и регист1 рацию результата решения.

Устройство работает следукщим образом.

Первоначально посредством полюсов

26 и 25 модели вершин коммутируются между собой в соответствии с конфигурацией исследуемого графа.

При этом считается, что полюс 25 является входом модели, а полюс 2630 выходом. Сдвиговый регистр 3 и коль цевые регистры 23 всех моделей вершин обнуляются, а триггеры 9 и 10 устанавливаются в нулевое состояние. Установочные шины на фиг. 1 не показаны.

Решение задачи на устройстве (фиг ° 3) начинается с момента подачи импульса блоком 2 управления1 который работает следующим образом: в исходном состоянии триггер 57 находится в нуле. На полюса 43 и 42 поступают сигналы с элементов И 4 и ИЛИ 6; на полюсе 42 сигнал отсутствует, на полюсе 43 — присутствует. Импульс ГИ из генератора 56 импульсов через зле45 мент И 47 поступает на полюс 39 блока управления и далее на вход сдвигового регистра 3, одновременно этот импульс через элемент ИЛИ 45 поступает на счетный вход триггера 5? и устанавливает его в единичное состоя50 ние. Единичное состояние триггера

57 выдает разрешение на полюс 36, которое далее поступает на полюса 29 моделей вершин и на вход элемента

И 49. На другие входы элемента И 49 поступает разрешение с полюса 43, с выхода элемента НЕ 54 и импульсы

ГИ 2 с выхода генератора 56 ймпульсов. Эти импульсы через элемент

52 8

Если предположить, что выбранной моделью 1 является модель, соответствующая вершине 65 графа, то импульс с полюса 26 вершины 65 модели поступает на полюса 25 вершин 59, 60 и 63моделей. В этих моделях импульс с полюса 25 поступает на вход триггера 9 и устанавливает его в единичное сос-, тояние, что дает возможность проходить сигналам через элемент И 14.

Серия же одиночных импульсов с полюса 37 блока 2 управления поступает на полюс 27 всех моделей 11 и далее на входы кольцевых регистров 23.

В процессе поступления этой серии одиночных импульсов происходит изменение сигналов на выходах элементов

И 4и ИЛИ 6

В.первоначальный момент, когда не сформирован. йи один максимальный .полный подграсЪ, на выходе элемента ИЛИ 6 сигнал отсутствует, а на выходе элемента И.4 присутствует. Достигается это тем, что в процессе действия .серии одиночных импульсов на выходе первого разряда кольцевого регистра

23 не появляется сигнал, так как эти регистры обнулены. Следовательно, отсутствует сигнал на выходе элемента

И 14 и на полюсе 33 модели 1„. В то же время на полюсе 34 модели сигнал " присутствует, так как он снимается через элемент ИЛИ 20 с выхода элемента НЕ 21.

Если в процессе поступления серии одиночных импульсов изменение сигналов на выхода элементов И 4, ИЛИ 6 и, следовательно, на полюсах 42 и

43 блока 2 управления не происходит., то блок 2 управления выдает импульс ф . на полюс 41, который поступает на полюс 44 всех моделей 1; . Он проходит через элемент И 12 только в выбранной модели и поступает через элемент

ИЛИ 18 на вход первого разряда кольцевого регистра 23, что обеспечивает запись единицы в данный разряд регистра 23. Например, если выбранная модель соответствует вершине 65 гра-, фа (фиг. 3), то в первый разряд кольцевого регистра 23 этой модели заносится единица. Это свидетельствует о том, что данная вершина включена в формируемый максимальный полный подграф.

Импульсом, поступающим с полюса 41. блока 2 управления на полюса 44 .моделей 1, триггеры 9 устанавлива ются в нулевое состояние, Такими мо!

7 8775

И 49, элемент ИЛИ 46 поступают на,полюс 37 блока 2 управления и далее на полюса 27 всех моделей вершин, где они используются для сдвигов кольцевых регистров 23.

Сдвинутый относительно ГИ 1 импульс ГИ 3 генератора 56 поступает через элемент И 48, элемент ИЛИ 45, на счетный вход триггера 57 и устанавливает его в нулевое состояние.

За то время, что триггер 57 находит- . ся в единичном состоянии, на полюс

37 поступает число импульсов ГИ 2, равное числу разрядов кольцевого регистра 23, и происходит изменение сигналов на полюсах 42 и 43 блока управления.

Если при этом на полюсе 43 имеется разрешение, а íà полюсе 42 разрешение отсутствует, то импульс ГИ 3 через элемент И 50 поступает на полюс 41 и далее в модели вершины.

Этот импульс служит для установки триггера 9 в исходное состояние.и для занесения значащей единицы в соответствующий разряд кольцевого регистра 23, Если:на полюсе 43, также как и на полюсе 42, отсутствует разрешение, то вместо серии импульсов

ГИ 2 блок управления выдает один импульс ГИ 3 через элемент И 51 и элемент ИЛИ 46 на полюс 37. Этот импульс, поступая в модели l вершин, производит сдвиг кольцевого регистра 23 е только на один разряд. Импульсом с по35 люса 39 на вход регистра 3 обеспечивается выбор произвольной модели 1„ и достигается то, что на выходе первого разряда сдвигового регистра 3 появляется сигнал, который поступает на полюс 28 модели 1„, соединенной с выходом этого разряда. С полюса 28 сигнал поступает на вход элементов И 1113 и 15. Для этих элементов он служит разрешением на прохождение через них

45 сигналов. Одновременно с этим импульсом блок 2 управления выдает импульс на полюс 36 и серию одиночных импульсов, число которых равно емкости кольцевого регистра 23 модели, на полюс 37.

С полюса 36 импульс поступает на, полюс 29 всех моделей l- . В вырранной модели импульс с полюса 29 через элемент И 11 проходит на полюс 26.

Далее этот импульс с полюса 26 посту-, пает на полюса 25 моделей, которые сое- 55 динены с выбранной моделью согласно . конфигурации графа (фиг. 3), содержащей вершины 58-65.

9 8775 делями в данный момент являются мо+ дели вершин 59, 60,и 63 графа.

Одновременно с импульсои, выданным на полюс 41 блока 2 управления

1 последний выдает импульсы на полюса

39 и 36 и серию одиночных импульсов на полюс 37. Этим обеспечивается. выбор очередной модели 11 .

Предположим, что следующей выбранной моделью. является соответствующая вершине 64 графа (фиг. 3). При этом триггеры 9 моделей 1 „, соответствующих вершинам 59, 60, 62 и 63 графа, оказываются установленными в единичное состояние.

В результате поступления серии одиночных импульсов происходит изменение сигнала только на выходе элемента И 4, так как ранее включенная модель вершины (в данном случае 65) выдает сигнал на выходе первого разряда кольцевого регистра 23. Этот сигнал не проходит через элемент И 14, потому что триггер 9 этой модели на-, ходится в нулевом состоянии и не изме- .

25 няет значение сигнала на полюсе 33.

Однако сигнал с выхода первого разряда кольцевого регистра 23 этой модели поступает на вход элемента НЕ 21 и изменяет через элемент ИЛИ 20 значение сигнала на полюсе 34. Соответзо ственно изменяется сигнал на выходе элемента H 4 и полюсе 43 блока 2 управления1 что соответствует выполнению второго условия. При этом блок 2 управления вьщает. один импульс на полюс

37, чем обеспечивает сдвиг кольцевых регистров 23 во всех моделях 1. на один разряд и импульс на полюс 41.

Импульсом, поступающим на полюс 41, выбранная модель включается в другой 4о максимальный полный подграф и триггеры 9,,ранее установленные в единич= ное состояние, устанавливаются в нулевое. В данном примере вершины 65 и

64 относятся к разным максимальным 45 ,полным подграфам, о чем свидетельст" вуют единицы, занесенные в их кольцевые регистры в разные разряды.

После этого блок 2 управления снова выбирает очередную модель 1„ вершины> как описано ранее.

Предположим, ;то такой моделью является модель, соответствующая вершине 63 графа. В результате триггер 9 в моделях соответствующих вершинам

58, 59, 61,. 64, 65 графа установлены в единичное состояние. В процессе поступления серии одиночных импульсов на

52 10 полюсах 27 моделей 1 происходит два

1 раза изменение сигналов на выходах элементов И 4 и ИЛИ 6. Первый,раз это происходит при совПаденин сигналов, снимаемых o åäèíè÷íîãî выхода триггера 9 и первого разряда кольцевого регистра 23, на элементе И 14 в модели

I<, которая соответствует вершине 65 графа, второй раз — в модели 1;, ко" торая соответствует вершине 64 графа.

В этом случае на полюсе 34 сигнал отсутствует, а на полюсе 33 укаэанных моделей сигнал появляется. Одновременно происходит изменение сигналов на выходах элементов И А и ИЛИ 6 и, следовательно, на полюсах 43 и 42 блока 2 управления. При этом на поз люсе 42 появляется сигнал, а на полюсе 43 — отсутствует, что соответствует выполнению третьего условия.

Одновременно с этим на выходе элемента И 5 появляется сигнал, который поступает на полюс 35 всех моделей

1.. Этот сигнал с полюса 35 поступает

1 на вход элементов И 15 и 16.

Каждый раз, как только выполняется третье условие, блок управления выдает импульсы на полюс 40, которые поступают на полюс 32 всех моделей

Этот импульс в выбранной очередной. раз регистром 3 модели 1„ проходит через элементы И 13, ИЛИ 18 и поступает на вход первого разряда кольце-. вого регистра 23, где он фиксируется. Такой моделью в данном случае является модель,, которая соответствует вершине 63 графа. В этой модели в кольцевой регистр 23 заносится по импульсу в те же разряды, что и в разрядах кольцевых регистров 23 моделей, соответствующих вершинам 64 и 65. В моделях 1„, в которых происходит совпадение сигналов на элементе И 14 импульс с полюса 32 поступает через элементы И 16, ИЛИ 19 на вход триггера

10 и устанавливает его в единичное состояние.

По мере поступления серии одиночных импульсов на полюс 27 всех моделей происходит описанный выше процесс и исправляются сигналы на выходах эле,ментов И 4, ИЛИ 6, т.е. на выходе элемента И 4 присутствует сигнал, а на выходе элемента ИЛИ 6 — отсутствует. Как только это происходит, блок

2 управления выдает импульс на полюс 41 который поступает на полюс

44 всех моделей 1;. Импульс устанав ливает триггер 9 в нулевое состояние

I) 87

Ь моделях, в которых они установлены в единичное состояние. Импульс в этом. случае поступает на вход элемента И 17 и проходит через этот элемент только в тех случаях, в которых . триггер 10 находится в единичном состоянии. В дайном случае такими моделями являются модели, которые соответствуют вершинам 63, 64 и 65 графа.. В этих моделях этот импульс сбрасывает триггер 10 в нулевое состояние и поступает через элемент ИЛИ 18 на вход первого разряда кольцевого регистра 23, где фиксируется.

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

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

23. В нашем примере такими подграфами являются (59, 63, 65), (59, 63, 64 ; (59, 60, 65); 58, 59, 61, 63); (64, 62 ; (59, 60, 64 ; (58, 59, 60).

На фиг. 4 поразрядно показано содержимое кольцевых регистров 23,мо- № делей 1„ (римскими цифрами отмечены номера разрядов кольцевых регистров., греческими цифрами — номера кольцевых регистров моделей и соответствуют номерам вершин приведенного графа) .

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

7552

12

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

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

И, выход которого подключен к первому входу первого элемента ИЛИ, первый элемент НЕ, второй и третий элементы

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

НЕ, а в каждую модель вершины введены третий элемент ИЛИ, седьмой элемент

И и кольцевой регистр, причем в каждой модели вершины первый выход кольце--, вого регистра подключен к первому вхо35

55 ду пятого элемента И и к входу первого элемента НЕ, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого является первым выходом модели вершины, выход пятого элемента

И является вторым выходом модели вершины и подключен к второму входу третьего элемента ИЛИ и к первому входу третьего элемента И, первый вход шестого элемента И соединен с первыми входами первого, седьмого и второго элементов

И и является первым входом модели вершины, Вторым входом которой является второй вход шестого элемента И, выход которого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевым входом второго триггера, со вторым входом четвертого элемента И и является третьим входом модели вершины, четверть|а входом которой является третий вход первого элемента И, второй вход седьмого элемента И соединен со вторыми входами второ-. го и третьего элементов И и является пятым входом модели вершины, третий вход второго элемента И соединен с третьим входом третьего элемента И, входом второго элемента НЕ и является

13 877552 шестым входом модели вершины, седьмым входом которой является третий вход седьмого элемента И, четвертый вход которого подключен к выходу второго элемента НЕ, выход четвертого -элемен5 та И соединен с нулевым входом перво го триггера и со входом первого элемента ИЛИ, выход которого подключен к установочному входу кольцевого регистра, второй выход которого соединен с входом блока индикации, выход второго триггера подключен к второму входу йятого элемента И, единичный вход второго триггера является .

ВОсьмым ВхОдОм мОдели Вершины девя» тым входом которой является сдвиговый вход кольцевого регистра, выход . седьмого элемента И подключен к третьему входу первого элемента ИЛИ, вторые выходы всех моделей вершин .соединены с входами многовходового элемента ИЛИ, выход которого подключен к седьмым входам всех моделей вершин, к входу первого элемента HE к второму входу блока управления и

14 к первому входу первого элемента И, выход которого соединен с шестыми входами моделей вершин, первые выходы моделей вершины подключены к входам второго элемента И, выход которого соединен с входом второго элемента

НЕ и третьим входом блока управления, второй выход которого подключен к девятым; входам моделей вершин, вторые входы которых соединены с третьим выходом блока управления, четвертый и пятый входы которого соответственно подключены к пятому и третьему входам всех моделей вершин, выход первого элемента НЕ соединен с четвертьп! Входом всех моделей вершин, выход второго элемента НЕ подключен к второму входу первого элемента И.

Источники информации, принятые во внимание при экспертизе

1. Авторское св щетельство СССР

Ф 408312, кл. G 06 Г 15/20, 1974.

2. Авторское свидетельство СССР

9 643880, кл. G 06 F 15/20, 1975 (прототип).

877552

80 81 Б2 ЮЗ 6 р

Составитель И.Дубинина

Редактор В.Петраш Техред Л.Пекарь Корректор М.Демчик

Заказ 9617 74 Тираж 748 Подписное

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

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

Филиал ППП Патент, г. Ужгород, ул. Проектная,