Устройство для исследования графов Советский патент 1981 года по МПК G06F15/173 

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

1

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

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

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

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

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

10 индикации и формирователи одиночных импульсов Г2.

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

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

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

М

Поставленная цель достигается тем, что в устройство для исследования графов, содержащее регистр, вход и первый выход которого подклю- чены соответственно к первому въкоду и входу блока управления, и модели вершин, (Соединенные между собой согласно топологии исследуемого графа, причем каждая модель вершины содержит первый элемент И, выход которого Подключен к первому входу первого элемента ИЛИ, первый элемент НЕ, второй и третий элементы И, выходы которых соедине.ны со входами второго элемента ИЛИ, выход которого подключен к единичному входу первого триггера, выход которого соединен с первым входом четвертого элемента И, второй триггер, пятый и шестой элементы И и блок индикации, введены многовходовой элемент ИЛИ, пер;вый и второй элемента Ид первый и второй элементы НЕ , а в,кажр,у1о модель вершины введегП) третий элемент ИЛИ, седьмой элемент И и кольцевой регистр, причем в кавдой модели вершины первый выход кольцевого регистра подключен к первому входу пятого элемента И и к входу первого элемента НЕ, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого является первым выходом модели вершины, выход пятого элемента И является вторым, выходом модели вершины и под ключей к второму входу третьего элемента ИЛИ и к первому входу третьего элемента И, первый вход шестого элемента И -соединен с первыми входами первого, Седьмого и второго элементов И и является первыг-j входом модели вершины, вторьм входом которой является второй вход шестого элемента И, выход которого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевьм входом второго триггера, со вторьпм входом чет вертого элемента И и является треты-iM входом модели вершины, четвертым входо которой является третий вход первого элемента И, второй вход седьмого элемента И соединен со вторыми входами второго и третьего элементов И и является пятымвходом модели вершины, тре тий вход второго элемента И соединен с третьим входом третьего элемента И, входом второго элемента НЕ и является шестым входом модели вершины, седьмым входом которой является третий вход седьмого элемента И, четвертый вход к торого подключен к выходу второго эле мента НЕ, выход четвертого элемента И соединен с нулевым входом первого триг гера и со JBTOpbw входом первого эле824 мента ИЛИ, выход которого подключен к установочному входу кольцевого регистра, второй выход которого соединен с входом блока индикации, выход второ триггера подключен к второму входу пятого элемента И, единичный вход второго триггера является .восьмым входом модели вершины, девятым входом которой является сдвиговый вход кольцевого регистра,, выход седьмого элемента И подключен к третьему входу первого элемента ИЛИ, вторые выходы всех моделей вершин соединены с входами многовходового элемента ИЛИ, вькод которого подключён к седьмым входам всех моделей вершин, к входу первого элемента НЕ, к второму входу блока управления и к первому входу первого элемента И, выход которого соединен с шестыми . входами моделей вершин, первые выход;л моделей вершины подключены к входам второго элементаИ, выход которого соединен с входом второго элемента ИЕ и третьим-входом блока управлений, второй выход которого подключен к девятым входам моделей вершин, вторые входы которых соединены с третьим выходом блока управления, четвертый и пятый входы которого соответственно подключены к пятому и третьему входам всех моделей«вершин, выход первого элемента НЕ соединен с четвертым входом всех моделей вершин, выход второго элемента НЕ подключен к второму входу первого элемента И, . На фиг. 1 предоставлена блок-схема устройства для исследования графов;, на фиг, 2 - схема блока управления; на фиг. 3 - пример графа; на фиг. 4поразрядно показайо содержимое кольцевых регистров. Устройство для исследования графов содержит модель 1 i .-ой вершины исследуемого .графа, блок 2 управления, сдвиговый регистр 3, второй 4 и первый 5 элементы И, элемент РШИ 6, второй. 7 и первый 8 элементы НЕ, в состав каждой модели 1 вершины входят, второй 9 и первый JO триггеры, шестой, первый, седьмой, пятый, второй, третий и четвертый элементы И 11-17, первый, второй и третий элементы РШИ 18-20, первый и второй элементы НЕ. 21 и 22, кольцевой регистр 23, блок 24 индикации, входы и выходы модели вершин и блока управления являются полюсами 25-44. Блок 2 управления (фиг. 2) содержит эххементы ШШ 45 и 46, элементы И 47-52, элементы ITE 53-55, генератор 56 импульсов и триггер 57. Получение решения задачи на устройстве производится в результате выбора в произвольном порядке Xj вер шины графа, определения множества вершин С. S,nrxv формирования макси мальных полных подграфов, которое состоит из проверки множества С на возможность включения его в формируемые максимальные полные подграфы и пометки вершин, входящих в эти подграфы. При этом под S подразумевается л-ый максимальный полный подгра графа, а ГУ - отображение вершины Х;| в графе. Произвольный выбор вершин Х осуществляет сдэиговый регистр 3, разря ные выходы которого в произвольном порядке соединены с полюсами 28 моделей Ц вершин. Множества вершин С формируются в результате совместной работы всех мо делей 1; вершин, которые соединены между собой полюсами 25 и 26 согласно конфигурации исследуемого графа. При этом в каждой модели используются элемент И 14, элемент НЕ 21, элемент ИЛИ 20, триггер 9 и кольцевой регистр 23. Одновременн-о с определением множества С, происходит его проверка на возможность включения в максимальный . полный подграф. При этом возможно вы полнение следующих условий: , 1 1 С 2i ; С, Выполнение первого условия свиде тельствует о том, что в максимальный полный подграф S. включается вершина ИГ в результате формируется S максимальный полный подграф. Вьтолнение второго и третьего условий свидетельствует о том, что в формируемый S , максимальный полный подграф включается без изменения Sj подграф. Кроме того, при выполнении третьего условия формируется специальное множество вершин. В это множество вершин относят вершины С и вершину Х. После того как сформирован S подграф, в него доцолнител но включают те вершины из специального множества, которые не являются его элементами. Проверку условий осуществляют эле менты И 4 и ИЛИ 6. Специальное множество вершин формируется элементами И 5 и НЕ 7 и в каждой модели 1 ;j триг гером 10, элементами НЕ 8, И 15 и 16 l-f-f 26 Для пометки вершин входящих в максимальный полный подграф, испольг уются элементы И 12 и 13, элемент ИЛИ 18 и кольцевой регистр 23 в каддоЛ модели Ц . При этом для пометки вершин, принадлежащих формируемому подграфу, используются разрядил кольцевых регистров 23 всех моделей 1. Наличие единицы в том или ином разряде этого регистра одной из моделей 1 свидетельствует о принадлежности этой вершины тому или иному максимальному полному подграфу. В результате проверки элементы И 4 и ИЛИ 6 выдают сигналы, которые пост пают в блок 2 управления, который по этим сигналам выдает на свои выходные полюса синхронизирующие импульсы, обеспечивающие синхронную работу всех моделей I - вершин и регистрацию результата решения. Устройство работает следуюпщм образом. Первоначально посредством полюсов 26 и 25 модели вершин коммутируются между собой в соответствии с конфигу- . рацией исследуемого графа. При этом считается, что полюс 25 является входом мо;п1ели, а полюс 26 выходом. Сдвиговый регистр 3 и кольцевые регистры 23 всех моделей вершин обнуляются, а триггеры 9 и 10 устанавливаются в нулевое состояние. Ус- . тановочные шины на фиг. 1 не показаны, I. Решение задачи на устройстве (фиг.З) начинается с момента подачи импульса блоком 2 управления, который работает следующим образом: в ис содном состоянии триггер 57 находится в нуле. На полюса 43 и 42 поступают сигналы с элементов И 4 и ИЛИ 6 на полюсе 42 сигнал отсутствует, на полюсе 43 - присутствует. Импульс ГИ 1 из генератора 56 импульсов через элемент И 47 поступает на полюс 39 блока управления и далее на вход сдвигового регистра 3, одновременно этот импульс через элемент ИЛИ 45 поступает на счетный вход триггера 57 и устанавливает его в единичное состояние.. Единичное состояние триггера 57 выдает разрешение на полюс 36, которое далее поступает на полюса 29 моделей вершин и на вход элемента И 49. На другие входы элемента И 49 поступает разрешение с полюса 43, с выхода элемента НЕ 54 и импульсы ГИ 2 с выхода генератора 56 импульсов. Эти импульсы через элемент И 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. Этот импуль поступая в модели h верший} производит сдвиг кольцевого регистра 23 только на один разряд. Импульсом с п люса 39 на вход регистра 3 обеспечивается выбор произвольной моделч 1 и достигается то, что навыходе первого разряда сдвигового регистра 3 п является сигнал) который поступает на полюс 28 модели 1, соединенной с выходом этого разряда. С Прлюса 28 с нал постзшает на вход элементов И 11 13 и 15. Дня этих элементов он служи разрешением на прохождение через них сигналов. Одновременно с этим импуль сом блок 2 управления выдает импульс на полюс 36 и серию одиночных импуль сов, число которых равно емкости кол цевого регистра 23 модели, йа полюс 3 С полюса 36 импульс поступает на. полюс 29 всех моделей 1 I В вырранной модели импульс с полюса 29 через элемент И 11 проходит на полюс 26, Далее этот, импульс с полюса 26 посту пает на полюса 25 моделей,которые сое динены с выбранной моделью согласно конфигурации графа (фиг. 3) , содержа щей вершины 58-65. 2 - 8 Если предположить, что выбранной моделью 1 .J является модель, соответствующая вершине 65 графа, то импульс с полюса 26 вершины 65 модели поступает на полюса 25 зершИн 59, 60 и 63 моделей. .В этих моделях импульс с полюса 25 поступает на вход триггера 9 и устайарливает его в единичное состояние, что дает возможность проходиtь сигналам через элемент И I4i Серия же одиночных импульсов с полюса 37 блока 2 управления поступает на полюс 27 всех моделей 1 и далее на входы кольцевых регистров 23. В процессе поступления этой серии одиночных импульсов происходит изменение сигналов на выходах элементов И ШШ..6.. В.первоначальный момент, когДа не сформирован..ни один максималыащ .полный подграф, на: выходе элемента ИЛИ 6 сигнал отсутствует, а на выходе элемента И.4 присутствует. Достигается это тем, что в процессе действия сеРин одиночньк ш шульсов на выходе первого разряда кол1 цевого регистра 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 устанавливаются в нулевое состояние. Такими моделями в данный момент являются MOt дели вершин 59, 60,и 63 графа. Одновременно с импульсом, вьщанным на полюс 41 блока 2 управления, последний вьщает импульсы на полюса 39 и 36 и серию одиночных импульсов на полк)с 37. Этим обеспечивается выбор очередной модели Ц. Предположим, что следующей выбран ной моделью, является соответствующая вершине 64 графа (фиг. З). При этом триггеры 9 моделей 1, соответствующих вершинам 59, 60, 62 и 63 гра- . фа, оказываются установленными в еди ничное состояние. В результате поступления серии одиночных импульсов происходит изменение сигнала только на выходе элемента И 4, так как ранее включенная модель вершины (в данном случае 65) вьщает сигнал на выходе первого разряда кольцевого регистра 23. Этот сигнал не проходит через элемент И 14 потому что триггер .9 этой модели находится в нулевом состоянии и не изм няет значение сигнала на полюсе 33. Однако сигнал с выхода первого разряда кольцевого регистра 23 этой модели поступает на вход элемента НЕ 2 и изменяет через элемент ИЛИ 20 значение сигнала на полюсе 34. Соответственно изменяется сигнал на выходе элемента И 4 и полюсе 43. блока 2 управ ления, что соответствует вьтолнению второго условия. При этом блок 2 управления вьщае-л один импульс на полю 37, чем обеспечивает сдвиг кольцевых регистров 23 во всех моделях I на один, разряд .и импульс на полюс 41. Импульсном, поступающим на полюс 4, выбранная модель включается в другой максимальный полный подграф и тригге ры 9, ранее установленные в единичное состояние, устанавливаются в нул вое. В данном примере вершины 65 и 6.4 относятся к pasHbtM максимальным .полным подграфам, о чем свидетельствуют единицы, занесенные в их кольце вые регистры в разные разряды. После этого блок 2 управления сно выбирает очередную модель 1 вершины как описано ранее. Предположи, что такой моделью .яв ется модель, соответствующая вершине 63 графа. В результате триггер 9 в моделях соответствующих вершинам 58, 59, 61,- 64, 65 графа установлены единичное состояние. В процессе пост пления серии одиночных импульсов на ° полюсах 27 моделей 1. происходит два раза изменение сигналов на выходах элементов И 4 и ИЛИ 6. Первый -раз это происходит при совпадении сигналов, снимаемых с единичного выхода триггера 9 и первого разряда кольцевого регистра 23, на элементе И 14 в модели Ц, которая соответствует вершине 65 графа, второй раз - в модели 1, которая соответствует вершине 64 графа. В этом случае на .полюсе 34 сигнал отсутствует, а на полюсе 33 указанных моделей сигнал появляется. Одновременно происходит изменение сигналов на выходах элементов И 4 и ИЛИ 6 и, следовательно, на по.пюсах 43 и 42 блока 2 управления. При этом на nor люсе появляется сигнал, а на полюсе 43 - отсутствует, что соответствует выполнению третьего условия. Одновременно с этш. на выходе элемента И 5 появляется сигнал., который поступает на полюс 35 всех моделей 1 .. Этот сигнал с полюса 35 поступает на вход элементов И 15 и 16. Каждый раз, как только выполняется третье условие, блок управления вьщает импульсы на полюс 40, которые поступают на полюс 32 всех моделей Этот импульс в выбранной очереднойраз регистром 3 модели проходит через элементы И 13, ИЛИ 18 и поступает на вход первого разряда кольце-:вого регистра 23, где он фиксируется. Такой моделью в данном случае является модель,, которая соответствует верщине 63 графа. В этой модели в кольцевой регист р 23 заносится по импульсу в те же разрядь, что и в разрядах кольцевых регистров 23 моделей, соответствующих вершинам 64 и 65. В моделях 1., в которых происходит совпадение сигналов на элементе И 14 импульс с полюса 32 поступает через элементы И 16, ИЛИ 19 на вход триггера 10 и устанавливает его в единичное состояние. По мере поступления серии одиночных импульсов на полюс 27 всех модеей происходит описанный выше процесс и исправляются сигналы на выходах элементов И 4, ИЛИ 6, т.е. на выходе элемента И 4 прису гствует сигнал, а на выходе элемента ИЛИ 6 - отсутствует. Как только это происходит, блок 2 управления выдает лмпульс на полюс 4 Ц который поступает на полюс 44 всех моделей 1. Импульс устанав- ливает триггер 9 в нулевое состояние 6 моделях, в которых они установлен состояние. Импульс в в единичное этом случае поступает на вход элемента И 17 и проходит через этот э мент только в тех случаях, в которы триггер 10 находится в единичном со тоянии. В дайном случае такими моде лями являются модели, которые соотв ствуют вершинам 63, 64 и 65 графа.. этих моделях этот импульс сбрасывает триггер 10 в нулевое состояние к поступает через элемент ИЛИ 18 на вход первого разряда кольцевого регистра 23, где фиксируется. В дальнейшем весь процесс работы устройства повторяется аналогично описанному ранее до тех пор, пока на выходе сдвигового регистра 3 не является сигнал, который поступает на полюс 38 блока 2 уп15авления и сигнализирует о конце решения задач К этому моменту все максимальные полные подграфы сформированы. Принадлежность моделей и, следовательно, вершин графа к тому или иному м симальному полному подграфу определяется наличием единиц в соответств ющих разрядах кольцевых регистров 23. В нашем примере такими подграфа ми являются . {59, 63, 65}; {64, 62}; {58, 59, 61, 63 {58, 59, 60. 59, 60, 64 На фиг. 4 поразрядно показано со держимое кольцевых регистров 23 лодалей 1 (римскими цифрами отмечены номера разрядов кольцевых регистров греческими цифрами - номера кольцевых регистров моделей и соответству ют номерам вершин приведенногй графа) . Предлага емое устройство по сравнению с известным дает возможность определять максимальные полные подграфы в графе. Решение этой задачи тесно связано с решением таких прак тических важных задач, как опредение связных частей схемы в задачах технического проектирования схем вы числительньгх устройств, группировка слов в блоки в информахдаонных си темах, определение максимального множества совместимых состояний и минимизация числа состояний при синте зе, дискретных автоматов, определение минимального числа рабочих ячее программы в ЭЦВМ. 2 12 Формула изобретения Устройство для исследования графов, содержащее регистр, вход и первый выход которого подключены соответственно к первому выходу и входу блока управления, и модели вершин, соединенные между собой согласно топологии исследуемого графа, причем каждая модель вершины содержит первый элемент И, выход которого подключен к первому входу первого элемента ИЛИ, первый элемент НЕ, второй и третий элементы И, выходы которых соединены со входами второго элемента ИЛИ, выход которого подключен к единичному входу первого триггера, выход которого соединен с первым входом четвертого элемента И, второй триггер , пятый и шестой элементы И и блок индикации, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения максимальных полных подграфов, в него введены много вх:одовой элемент ИЛИ, первый и второй элементы И, первый и второй элементы НЕ, а в каждую модель вершины введены третий элемент ШШ, седьмой элемент И и кольцевой регистр, причем в каждой модели вершины первый выход кольце-, вого регистр подключен к первому входу пятого элемента И и к входу первого элемента НЕ, выход которого соединен с первым входом третьего элемента ШШ, выход которого является первым выходом модели вершины, выход пятого элемента И является вторым выходом модели вершины и подключен к второму входу третьего элемента ИЛИ и к первому входу третьего элемента И,первый вход шестого элемента И соединен с первыми входами первого, седьмого и второго элементов И и является первым входом модели вершины вторым входом которой является второй вход шестого элемента И, выход которого является третьим выходом модели вершины, второй вход первого элемента И соединен с нулевым входом второго триггера, со вторым входом четвертого элемента И и является третьим входом модели вершины, четвертым входом которой является третий вход пеового элемента И, второй вход седьмого элемента И соединен со вторьп входами второго и третьего элементов И и является пятым входом модели вершины, третий вход второго элемента И соединен с третьим входом третьего элемента И, входом второго элемента НЕ и является 53 шестым входом модели вершины, седьмы входом которой является третий вход седьмого элемента И, четвертый вход которого подключен к выходу второго, элемента НЕ, выход четвертого-элемен та И соединен с нулевым входом перво :го триггера и со входом первого элемента ИЛИ, выход которого подключен к установочному входу кольцевого рег стра, второй выход которого соеди- нен с входом блока индикации, выход второго триггера подключен к второму входу пятого элемента И единичный вход второго триггера является восьмьм входом модели вершины, девятым входом которой является сдвиговый вход кольцевого регистра, выход седьмого элемента И подключен к третьему входу первого элемента ИЛИ, вторые выходы всех моделей вершин .соединены с входами многовходового элемента ИЛИ, выход которого подключен к седьмым входам всех моделей вершин, к входу первого элемента НЕ к второму входу блока управления и к первому входу первого элемента И, выход которого соединен с шестыми входами моделей вершин, первые выходы моделей вершины подключены к входам второго элемента И, выход которого соединен с входом второго элемента НЕ и третьим входом блока управления, второй выход которого подключен к девHTbiMj-входам моделей вершин, вторые входы которых соединены с третьим выходом блока управления, четвертый и пятый входы которого соответственно подключены к пятому и третьему входам всех моделей вершин, выход первого элемента НЕ соединен с четвертый входом всех моделей вершин, выход второго элемента НЕ подключен к второму входу первого элемента И. Источники информации, принятые во внимание при экспертиэе 1.Авторское св адетельство СССР № 408312, кл. G 06 F 15/20, 1974. 2.Авторское свидетельство СССР № 643880, кл. G 06 F 15/20, 1975 (прототип).

i

tsJ

tit

1Й Rii ftiiHK Siiij: F l

M,4

Ф

i WL

w

(A

и

ai

иъ.З

S8 S3 ВО SI 62. S3 St

J Ж Ж

ж т

ж ж:

УЖ

ff

ФигЛ