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

Союз СоветсинкСоциалнстнчесникРеспублик АВТОРСКОМ ИТЕЛЬСТЕ 61) Дополнительное к авт. свид-ву 9 (21) 2870565/18-2415/2 заявки Гооударствеииый комитет СССР(23) Приоритет Опубликовано 30. 10. 81. Бюлле по делам иэобретеиии и открытий2) зо Институт электродинамики АН Украинскойрадиотехнический институт им. В.Д.Калмыко(71) За 54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ 20го с а я цель дройстводержащевыход к Поставленнтем, что в усния графов, свход и первый я исследоваист орого подклюИзобретение относится к электрон ному моделированию и может быть использовано при построении цифровых специализированных вычислительных устройств для решения задач на графах,. в частности для поиска максимальных полных подграфов в графе,Полным подграфом графа называется такой подграф, любые две вершины которого соединены ребром.Максимальным полным подграфом называют полный подграф, который не является подграфом какого-либо другого полного подграфа.Известно устройство, содержащее модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, вход и выход которого подключены к первому входу и выходу блока управления, второй, третий и четвертый выходы которо соединены соответственно с первым,. вторым и третьим входами моделей вершин, группа элементов И 11 . Наиболее близким по техническому решению к предлагаемому является уст ройство для исследования графов, содержащее модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, группу элементов И, блок управленияв состав каждой модели вершины входят триггеры, элементы И, элементы ИЛИ, элемент НЕ,счетчик импульсов, блок индикации и формирователи одиночныхимпульсов 2).Недостатком известных устройств является то, что они не позволяют определить все существующие в графе максимальные полные подграфы.Цель изобретения - расширение функциональных возможностей за счет. определения максимальных полных подграфов.а орректор М.Демч Редактор ВЛетраш дписное Заказ 9617 ППП Патент , г. Ужгород, ул, Проекты Ф 74 Тираж 7 ВНИИПИ Государствпо делам изобр 113035, Москва, Ж нного комитета С тений и открытий 35, Раушская наб д. 4/ 4чены соответственно к первому выхо; ду и входу блока управления, и модели вершин, соединенные между собой согласно топологии исследуемого графа, причем кащдая модель вершины содержит первый элемент И, выход которого подключен к первому входу первого элемента ИЛИ, первый элемент НЕ, второй и третий элементы И, выходы которых соединены со входами 10 второго элемента ИЛИ, выход которого подключен к единичному входу первого триггера, выход которого соединен с первым входом четвертого элемента И, второй триггер, пятый и шестой элементы И и блок индикации, введены многовходовой элемент ИЛИ, йер-. ;вый и второй элементы И, первый и второй элементы НЕ,а в,каждую модель вершины введены третий элемент ИЛИ, седьмои элемент И и кольцевои регистр,о ,20 причем в каждой модели вершины первый выход кольцевого регистра подключен к первому входу пятого элемента И и к входу первого элемента НЕ, выход25 которого соединен с первым входом третьего элемента ИЛИ, выход которого является первым выходом модели вершины, выход пятого элемента И является вторым, выходом модели вершины и подключен к второму входу третьего эле 30 мента ИЛИ и к первому входу третьего элемента. И, первый вход шестого элемента И соединен с первыми входами первого, седьмого и второго элементов И и является первым входом модели вер шины, вторым входом которой является второй вход шестого элемента И, выход которого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевым входом ,40 второго триггера, со вторым входом четвертого элемента И и. является третьим входом модели вершины, четвертым входом которой является третий вход первого элемента И, второй вход седьмого эле мента И соединен со вторыми входами .второго и третьего элементов И и является пятым входом модели вершины, третий вход второго элемента И соединен с третьим входом третьего элемента И, 50 входом второго элемента НЕ и является шестым входом модели вершины, седьмым входом которой является третий вход седьмого элемента И, четвертый вход которого подключен к выходу второго эле мента НЕ, выход четвертого элемента И соединен с нулевым входом первого триггера и со вторым входом первого элемента ИЛИ, выход которого подключен к установочному входу кольцевого регистра, второй выход которого соединен с входом блока индикации, выход второго триггера подключен к второму входу пятого элемента И, единичный вход второго триггера является .восьмым входом модели вершины, девятым входом которой является сдвиговый вход кольцевого регистра,. выход седьмого элемента И подключен к третьему входу первого элемента ИЛИ. вторые выходы всех моделей вершин соединены с входами многовходового элемента ИЛИ, выход которого подключен к седьмым входам всех моделей вершин, к входу первого элемента НЕ, к второму входу блока управления и к первому входу первого элемента И, выход которого соединен с шестыми входами моделей вершин, первые выходы моделей вершины подключены к входам второго элемента И, выход которого соединен с входом второго .элемента 11 Е й третьим входом блока управлений, второй выход которого подключен к девятым входам моделей вершин, вторые входы которых соединены с третьим выходом блока управления, четвертый и пятый входы которого соответственно поцключены к пятому и третьему входам всех моделейевершин, выход первого элемента НЕ соединен с четвертым входом всех моделей вершин, выход второго элемента НЕ подключен к второму входу первого элемента И.На фиг. 1 представлена блок-схема устройства для исследования графов; на фиг. 2 - схема блока управления; на фиг. 3 - пример графа; на фиг. 4- поразрядно показано содержимое кольцевых регистров.Устройство для исследования графов содержит модель 1 1 -ой вершины исследУемого .графа, блок 2 управле - ния, сдвиговый регистр 3, второй 4 и первый 5 элементы И, элемент ИЛИ б, второй 7 и первый 8 элементы НЕ, в состав каждой модели 1 вершины входят.второй 9 и первый 10 триггеры, шестой, первый, седьмой, пятый, второй, третий и четвертый элементы И 11-17, первый, второй и третий элементы ИЛИ 18-20, первый и второй элементы НЕ. 21 и 22, кольцевой регистр 23, блок 24 индикации, входы и выходы модели вершин и блока управления являются полюсами 25-44.Блок 2 управления (фиг. 2) содержит элементы ИЛИ 45 и 46, элементы15 20 25 5 87 И 47-52, элементы НЕ 53-55, генератор 56 импульсов и триггер 57,Получение решения задачи на устройстве производится в результате выбора в произвольном порядке Х вершины графа, определения множества вершин С 1=5 ПГ 111 Формирования максимальных полйых подграфав; которое состоит из проверки множества С на возможность включения его в формируемые максимальные полные подграфы и пометки вершин, входящих в эти подграфы. При этом под 5; подразумевается 1-ый максимальный полный подграф графа а Г 11 - отображение вершинысХ в граФе.Произвольный выбор вершин Х 1 осуществляет сдвиговый регистр 3, разрядные выходы которого в произвольном порядке соединены с полюсами 28 моделей 11 вершин.Множества вершин С формируются в результате совместной работы всех моделей 1 вершин, которые соединены между собой полюсами 25 и 26 согласно конфигурации исследуемого графа. При этом в каждой модели используются элемент И 14, элемент НЕ 21, элемент ИЛИ 20, триггер 9 и кольцевой регистр 23.Одновременно с определениеммножества С, происходит его проверка на возможность включения в максимальный .полный подграф, При этом возможно выполнение следующих условий:С.=5 С=Ф; С 1 Ф 5;Ф.Выполнение первого условия свидетельствует о том, что в максимальный полный подграф 5включается Х 1, вершина и"в результате формируется 5 1 максимальный полный подграф.Выполнение второго и третьего условий свидетельствует о том, что в Формируемый 5;+1 максимальный полный подграф включается без изменения 51 подграф. Кроме того, при выполнении третьего условия формируется специальное множество вершин. В это множество вершин относят вершины Си вершину Х 1,. После того как сформирован 5,1 подграф, в него до 11 олнительно включают те вершины из специального множества, которые не являются его элементами.Проверку условий осуществляют элементы И 4 и ИЛИ 6. Специальное множество вершин формируется элементами И 5 и НЕ 7 и в каждой модели 1 триггерои 10, элементами НЕ 8, И 15 и 16. 552 6 Для пометки вершин, входящих в максимальный полный подграф, используются элементы И 12 и 13, элемент И 91 18и кольцевой регистр 23 в каждой моде"ли 11 . При этом для пометки вершин,принадлежащих Формируемому подграфу,используются разряды кольцевых регистров 23 всех моделей 1, Наличие единицы в том или ином разряде этого регистра одной из моделей 1; свидетельствует о принадлежности этой вершины тому или иному максимальному полному подграфу,В результате проверки элементы И 4 и ИЛИ б выдают сигналы, которые поступают в блок 2 управления, который по этим сигналам выдает на свои выходные полюса синхронизирующие импульсы, обеспечивающие синхронную работу всех моделей 1 вершин и регистрацию результата решения. Устройство работает следукщим образом. Первоначально посредством полюсов 26 и 25 модели вершин коммутируются между собой в соответствии с конфигу"рацией исследуемого графа.При этом считается, что полюс 25является входом модели, а полюс 2630выходом. Сдвиговый регистр 3 и коль- цевые регистры 23 всех моделей вершинобнуляются, а триггеры 9 и 10 устанавливаются в нулевое состояние. Установочные шины на фиг. 1 не показаны.1Решение задачи на устройстве (фиг.3)начинается с момента подачи импульса блоком 2 управления 1 который работает следующим образом: в исходномсостоянии триггер 57 находится в нуле. На полюса 43 и 42 поступают сигналы с элементов И 4 и ИЛИ 6; на полюсе 42 сигнал отсутствует, на полюсе 43 - присутствует. Импульс ГИиз генератора 56 импульсов через злемент И 47 поступает на полюс 39 блока управления и далее на вход сдвигового регистра 3, одновременно этотимпульс через элемент ИЛИ 45 поступает на счетный вход триггера 57 иустанавливает его в единичное состоя" 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 модели сигнал "присутствует, так как он снимаетсячерез элемент ИЛИ 2 О с выхода элемента НЕ 21.Если в процессе поступления серии одиночных импульсов изменение сигналов на выхода элементов И 4, ИЛИ 6и, следовательно, на полюсах 42 и43 блока 2 управления не происходит., то блок 2 управления выдает импульсф. на полюс 41, который поступает наполюс 44 всех моделей 1; . Он проходитчерез элемент И 12 только в выбранной модели и поступает через элементИЛИ 18 на вход первого разряда кольцевого регистра 23, что обеспечивает запись единицы в данный разрядрегистра 23. Например, если выбраннаямодель соответствует вершине 65 гра-,фа (Фиг, 3), то в первый разряд кольцевого регистра 23 этой модели заносится единица. Это свидетельствует о том, что данная вершина включена в Формируемый максимальный полныйподграф,Импульсом, поступающим с полюса41. блока 2 управления на полюса 44,моделей 1 , триггеры 9 устанавливаются в нулевое состояние, Такими мо 5 8775И 49, элемент ИЛИ 46 поступают на,полюс 37 блока 2 управления и далеена полюса 27 всех моделей вершин,где они используются для сдвигов кольцевых регистров 23.5Сдвинутый относительно ГИ 1 импульс ГИ 3 генератора 56 поступаетчерез элемент И 48, элемент ИЛИ 45,на счетный вход триггера 57 и устанавливает его в нулевое состояние. 1 ОЗа то время, что триггер 57 находит-,ся в единичном состоянии, на полюс37 поступает число импульсов ГИ 2,равное числу разрядов кольцевого регистра 23, и происходит изменениесигналов на полюсах 42 и 43 блокауправления.Если при этом на полюсе 43 имеется разрешение, а на полюсе 42 разрешение отсутствует, то импульс ГИ 3через элемент И БО поступает на по"люс 41 и далее в модели вершины.Этот импульс служит для установкитриггера 9 в исходное состояние идля занесения значащей единицы в соответствующий разряд кольцевого регистра 23, Если:на полюсе 43, такжекак и на полюсе 42, отсутствует разрешение, то вместо серии импульсовГИ 2 блок управления выдает один импульс ГИ 3 через элемент И 51 и элемент ИЛИ 46 на полюс 37. Этот импульс,поступая в модели 11 вершин, производит сдвиг кольцевого регистра 23Этолько на один разряд. Импульсом с по 35люса 39 на вход регистра 3 обеспечивается выбор произвольной модели 1 фи достигается то, что на выходе первого разряда сдвигового регистра 3 появляется сигнал, который поступаетна полюс 28 модели 1, соединенной свыходом этого разряда С полюса 28 сигнал поступает на вход элементов И 1113 и 15. Для этих элементов он служитразрешением на прохождение через них45сигналов. Одновременно с этим импульсом блок 2 управления выдает импульсна полюс 36 и серию одиночных импульсов, число которых равно емкости коль"цевого регистра 23 модели, на полюс 37.С полюса 36 импульс поступает на,полюс 29 всех моделей 1 1. В выДран"ной модели импульс с полюса 29 черезэлемент И 11 проходит на полюс 26.Далее этот импульс с полюса 26 посту-,пает на полюса 25 моделей, которые соединены с выбранной моделью согласно .конфигурации графа (фиг. 3), содержащей вершины 58-65,20 9 8775 делями в данный момент являются моФ дели вершин 59, 60,и 63 графа.Одновременно с импульсои, выданным на полюс 41 блока 2 управления последний выдает импульсы на полюса5 39 и 36 и серию одиночных импульсов на полюс 37. Этим обеспечивается. выбор очередной модели 11 .Предположим, что следующей выбранной моделью. является соответствующая вершине 64 графа (фиг. 3). При этом триггеры 9 моделей 1 , соответствующих вершинам 59, 60, 62 и 63 граФа, оказываются установленными в единичное состояние.В результате поступления серии одиночных импульсов происходит изменение сигнала только на выходе элемента И 4, так как ранее включенная модель вершины (в данном случае 65) выдает сигнал на выходе первого разряда кольцевого регистра 23. Этот сигнал не проходит через элемент И 14, потому что триггер 9 этой модели на-, ходится в нулевом состоянии и не изме- .25 няет значение сигнала на полюсе 33. Однако сигнал с выхода первого разряда кольцевого регистра 23 этой модели поступает на вход элемента НЕ 21 и изменяет через элемент ИЛИ 20 значение сигнала на полюсе 34, Соответзо ственно изменяется сигнал на выходе элемента И 4 и полюсе 43 блока 2 управления 1 что соответствует выполнению второго условия. При этом блок 2 управления вьщает. один импульс на полюс З 5 37, чем обеспечивает сдвиг кольцевых регистров 23 во всех моделях 1 на один разряди импульс на полюс 41. Импульсом, поступающим на полюс 41, выбранная модель включается в другой 4 о максимальный полный подграф и триггеры 9 ранее установленные в единич-. ное состояние, устанавливаются в нулевое. В данном примере вершины 65 и 64 относятся к разным максимальным 45 ,полным подграфам, о чем свидетельст вуют единицы, занесенные в их кольцевые регистры в разные разряды.После этого блок 2 управления снова выбирает очередную модель 1 вершины как описано ранее. 52 1 О полюсах 27 моделей 1 происходит два1раза изменение сигналов на выходах элементов И 4 и ИЛИ 6, Первый,раз это происходит при совПаденин сигналов, снимаемых оединичного выхода триггера 9 и первого разряда кольцевого регистра 23, на элементе И 14 в модели 11, которая соответствует вершине 65 графа, второй раз - в модели 1;, ко" торая соответствует вершине 64 графа. В этом случае на полюсе 34 сигнал отсутствует, а на полюсе 33 укаэанных моделей сигнал появляется. Одновременно происходит изменение сигналов на выходах элементов И А и ИЛИ 6 и, следовательно, на полюсах 43 и 42 блока 2 управления. При этом на поз люсе 42 появляется сигнал, а на полюсе 43 - отсутствует, что соответствует выполнению третьего условия. Одновременно с этим на выходе элемента И 5 появляется сигнал, который поступает на полюс 35 всех моделей 1 Этот сигнал с полюса 35 поступает на вход элементов И 15 и 16.Каждый раз, как только выполняется третье условие, блок управления выдает импульсы на полюс 40, которые поступают на полюс 32 всех моделей Этот импульс в выбранной очередной раз регистром 3 модели 1 проходит через элементы И 13, ИЛИ 18 и поступает на вход первого разряда кольце-. вого регистра 23, где он фиксируется. Такой моделью в данном случае является модель которая соответству" ет вершине 63 графа. В этой модели в кольцевой регистр 23 заносится по импульсу в те же разряды, что и в разрядах кольцевых регистров 23 моделей, соответствующих вершинам 64 и 65. В моделях 1, в которых происходит совпадение сигналов на элементе И 14 им" пульс с полюса 32 поступает через элементы И 16, ИЛИ 19 на вход триггера 10 и устанавливает его в единичное состояние. По мере поступления серии одиночных импульсов на полюс 27 всех моделей происходит описанньм выше процесс и исправляются сигналы на выходах эле,ментов И 4, ИЛИ 6, т.е, на выходеПредположим, что такой моделью является модель, соответствующая вершине 63 графа. В результате триггер 9 в моделях соответствующих вершинам55 58, 59, 61,. 64, 65 графа установлены в единичное состояние, В процессе поступления серии одиночных импульсов на элемента И 4 присутствует сигнал, ана выходе элемента ИЛИ 6 - отсутствует. Как только это происходит, блок2 управления выдает импульс на полюс 41 который поступает на полюс44 всех моделей 1;. Импульс устанавливает триггер 9 в нулевое состояние11 87 Ь моделях, в которых они установлены в единичное состояние. Импульс вэтом. случае поступает на вход элемента И 17 и проходит через этот элемент только в тех случаях, в которых . триггер 10 находится в единичном состоянии. В дайном случае такими моделями являются модели, которые соответствуют вершинам 63, 64 и 65 графаВ этих моделях этот импульс сбрасывает триггер 1 О в нулевое состояние и поступает через элемент ИЛИ 18 на вход первого разряда кольцевого регистра 23, где фиксируется.В дальнейшем весь процесс работы устройства повторяется аналогично описанному ранее до тех пор, пока на выходе сдвигового регистра 3 не появляется сигнал, который поступает на полюс 38 блока 2 управления и сигнализирует о конце решения задачи.К этому моменту все максимальные полные подграфы сформированы. Принадлежность моделей и, следовательно, вершин графа к тому или иному максимальному полному подграфу определяется наличием единиц в соответствующих разрядах кольцевых регистров 23, В нашем примере такими подграфами являются 7552 12Формула изобретения Устройство для исследования графов,содержащее регистр, вход и первый выход которого подключены соответственно к первому выходу и входу блока управления, и модели вершин, соединенные между собой согласно топологииисследуемого графа, причем каждая мо дель вершины содержит первый элементИ, выход которого подключен к первомувходу первого элемента ИЛИ, первыйэлемент НЕ, второй и третий элементыИ, выходы которых соединены со входа ми второго элемента ИЛИ, выход которого подключен к единичному входу первого триггера, выход которого соединен с первым входом четвертого элемента И, второй триггер; пятый и шестойэлементы И и блок индикации, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностейза счет определения максимальных полных подграфов, в него введены много входовой элемент ИЛИ, первый и второйэлементы И, первый и второй элементы , НЕ, а в каждую модель вершины введенытретий элемент ИЛИ, седьмой элементИ и кольцевой регистр, причем в каждоймодели вершины первый выход кольце-,вого регистра подключен к первому вхо 35 40 45 50 55 59, 63, 65, 59, 63, 64;59, 60, 6511 58, 59, 61, 63; 64, 62; 59, 60, 64; 58, 59, 60,На фиг. 4 поразрядно показано содержимое кольцевых регистров 23,мо-ф делей 1 (римскими цифрами отмечены номера разрядов кольцевых регистров., греческими цифрами - номера кольцевых регистров моделей и соответствуют номерам вершин приведенного графа) .Предлагаемое устройство по сравнению с известным дает возможность определять максимальные полные подграфы в графе. Решение этой задачи тесно связано с решением таких практических важных задач как опредение связных частей схемы в задачах технического проектцрования схем вы-, числительных устройств, группировка слов в блоки в информационных системах, определение максимального множества совместимых состояний и минимизация числа состояний при синтезе. дискретных автоматов, определение минимального числа рабочих ячеек программы в ЭЦВМ. ду пятого элемента И и к входу первогоэлемента НЕ, выход которого соединенс первым входом третьего элемента ИЛИ,выход которого является первым выходоммодели вершины, выход пятого элементаИ является вторым выходом модели вершины и подключен к второму входу третьего элемента ИЛИ и к первому входу третьего элемента И,первый вход шестогоэлемента И соединен с первыми входамипервого, седьмого и второго элементовИ и является первым входом модели вершины, Вторым входом которой являетсявторой вход шестого элемента И, выходкоторого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевым входом второго триггера, со вторым входом четвертого элемента И и является третьим входом модели вершины, четвертьщ входомкоторой является третий вход пеовогоэлемента И, второй вход седьмого элемента И соединен со вторыми входами второ-.го и третьего элементов И и являетсяпятым входом модели вершины, третийвход второго элемента И соединен стретьим входом третьего элемента И,входом второго элемента НЕ и является13 877552шестым входом модели вершины, седьмымвходом которой является третий входседьмого элемента И, четвертый входкоторого подключен к выходу второго.элемента НЕ, выход четвертого -элемен 5та И соединен с нулевым входом первого триггера и со входом первого элемента ИЛИ, выход которого подключенк установочному входу кольцевого регистра, второй выход которого соединен с входом блока индикации, выходвторого триггера подключен к второму входу йятого элемента И, единичный вход второго триггера являетсявосьмым входом модели вершины, девятым входом которой является сдвиговый вход кольцевого регистра, выход. седьмого элемента И подключен к третьему входу первого элемента ИЛИ,вторые выходы всех моделей вершин.соединены с входами многовходовогоэлемента ИЛИ, выход которого подключен к седьмым входам всех моделейвершин, к входу первого элемента НЕ,к второму входу блока управления и 14к первому входу первого элемента И,выход которого соединен с шестымивходами моделей вершин, первые выходымоделей вершины подключены к входамвторого элемента И, выход которогосоединен с входом второго элементаНЕ и третьим входом блока управления,второй выход которого подключен кдевятым. входам моделей вершин, вторыевходы которых соединены с третьимвыходом блока управления, четвертыйи пятый входы которого соответственно подключены к пятому и третьемувходам всех моделей вершин, выходпервого элемента НЕ соединен с четвертый входом всех моделей вершин,выход второго элемента НЕ подключенк второму входу первого элемента И.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРУ 408312, кл. С 06 Г 15/20, 1974.2. Авторское свидетельство СССРВ 643880, кл. С 06 Г 15/20, 1975