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

 

УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФА НА ПОДГРАФЫ, содержащее генератор тактовых импульсов, первую и вторую группы элементов И, первую группу элементов ШШ, первьй элемент И, первую и вторую группы триггеров ,, блок отображения графа, первый и второй счетчики, первый элемент задержки, группу дифференцирующих элементов, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения определения номеров вершин каждого подграфа, в устройство введены пять регистров сдвига, два дешифратора, три буферных .регистра, узел коммутации , третья и четвертая группы элементов И, п блоков узлов перебора (п - число вершин графа), каждый из которых состоит из триггера, двух элементов И и элемента ИЛИ, шифратор , блок сложения-вычитания, первая и вторая схемы сравнения, второй , третий, четвертый и пятый элементы задержки, четьфе элемента ШШ, элемент НЕ, вторая и третья группы элементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок, буферный матричный запоминающий блок и блок индикации, причем выход генератора тактовых импульсов соединен с входами первого и второго счетчиков, выходы первого счетчика соединены с входами первого дешифратора , выходы второго счетчика через первый буферный регистр соединены с входами второго дешифратора, выходы которого соединены с первыми входами элементов И первой и четвертой групп, вторые входы элементов И первой группы объединены и подключены к выходу второго элемен (Л та И, сдвигающему входу первого регистра сдвига и объединенным единичным входам триггеров второй груп :пы, выходы элементов И первой группы соединены с первыми входами соответствующих элементов ИЛИ первой группы , выходы второго регистра сдвига . 00 соединены с управляющими входами соф ответствующих элементов буферного 4 Од матричного запоминающего блока и через узел коммутации с вторьп да входаh (i ми элементов ИЖ первой группы,, выход калодого элемента ,ИЛИ первой грУппы соединен с информационными входами буферного матричного запоминающего блока и единичным входом соответствующего триггера первой группы триггеров, нулевые входы триггеров первой группы объединены и соедине .ны с объединенными первыми входами элементов ШШ третьей группы, входами установки в нуль первого и второ ,госчетчиков, первого и второго регистров сдвига, первым входом пер

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

3 5р С 06 F 15/20

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

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTl41 (21) 3466793/18-24 (22) 07 ° 07.82 (46) 15.04.84. Бюл. ¹ 14 (72) В.M.Ãëóøàíü, В.И.Курейчик и Л.И.Щербаков (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР № 549810, кл. G 06 F 15/20, 1974.

2. Авторское свидетельство СССР № 679998, кл. С 06 G 7/48, 1977.

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

N - 656073, кл. G 06 F 15/36, 1976 (прототип) . (54)(57) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ

ГРАФА HA ПОДГРАФЫ, содержащее генератор тактовых импульсов, первую и вторую группы элементов И, первую группу элементов ИЛИ, первый элемент И, первую и вторую группы триггеров, блок отображения графа, первый и второй счетчики, первый эле-мент задержки, группу дифференцирующих элементов, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения определения номеров вершин каждого подграфа, в устройство введены пять регистров сдвига, два дешифратора, три буферных, регистра, узел коммутации, третья и четвертая группы элементов И, и блоков узлов перебора (n — число вершин графа), каждый из которых состоит из .триггера, двух элементов И и элемента ИЛИ, шифратор, блок сложения-вычитания, первая и вторая схемы сравнения, второй, третий, четвертый и пятый эле» менты задержки, четыре элемента ИЛИ, „„SU„„. 1086434 A элемент НЕ, вторая и третья группы элементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок, буферный матричный запоминающий блок и блок индикации, причем выход генератора тактовых импульсов соединен с входами первого и второго счетчиков, выходы первого счетчика соединены с входами первого дешифратора, выходы второго счетчика через первый буферный регистр соединены с входами второго дешифратора, выходы которого соединены с первыми входами элементов И первой и четвертой групп, вторые входы элементов И первой группы объединены и подключены к выходу второго элемента И, сдвигающему входу первого регистра сдвига и объединенным единичным аходам триггеров второй груп пы, выходы элементов И первой группы соединены с первыми входами сооТветствующих элементов ИЛИ первой группы, выходы второго регистра сдвига соединены с управляющими входами соответствующих элементов буферного матричного запоминающего блока и через узел коммутации с вторыми входами элементов ИЛИ первой группы, выход каждого элемента,ИЛИ первой группы соединен с информационными входами буферного матричного запоминающего блошка и единичным входом соот-ветствующего триггера первой группы триггеров, нулевые входы триггеров первой группы объединены и соедине,ны с объединенными первыми входами элементов ИЛИ третьей группы, входами установки в нуль первого и второ,го счетчиков, первого и второго регистров сдвига, первым входом пер1086434 вого элемента ИЛИ и выходом второго элемента ИЛИ, единичный выход каждого триггера первой группы соединен с первыми входами элементов ИЛИ и первого элемента И соответствующего узла перебора, вторым входом соответствующего элемента ИЛИ тре" тьей группы и,соответствующим входом первого элемента И, второй вход элемента ИЛИ каждого узла перебора соединен с соответствующим выходом первого дешифратора, вторые входы первых элементов И узлов перебора объединены и подключены к выходу третьего элемента ИЛИ, выход первого регистра сдвига соединен с вторым входом первого элемента ИЛИ, входом второго регистра сдвига, входом вычитания флока сложениявычитания и через первый элемент задержки с первым входом третьего элемента ИЛИ, второй вход которого является входом задания исходного состояния устройства, выход. элемента ИЛИ каждого узла -перебора. соединен с первым входом второго элемента И узла перебора, второй вход которого соединен с нулевым выходом триггера узла перебора, единичный вход которого соединен с выходом первого элемента И узла перебора, а нулевой вход — с выходом соответствующего элемента ИЛИ третьей группы, выходы вторых элементов И узлов перебора соединены с первыми входами соответствующих элементов И третьей группы, вторые входы которых соединены с нулевыми выходами соответствующих триггеров второй группы, нулевые входы которых подключены к выходам соответствующих элементов И четвертой группы и через дифференцирующие элементы к входам четвертого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторые входы элементов И четвертой группы объединены и подключены к выходу первого счетчика, управляющему входу четвертого регистра сдвига и первому входу второго элемента И, третьи входы элементов И четвертой группы объединены и подключены к нулевому выходу триггера и через последова.тельно соединенные четвертый элемент задержки и элемент НЕ к второму входу второго элемента И, единичный вход триггера соединен с выходом четвертого регистра сдвига, информационные входы которого соединены с соответствующими выходами-третьего регистра сдвига, установочные входы которого соединены с входом установки исходного состояния устройства, первыми входами элементов ИЛИ второй группы, первым входом второго элемента ИЛИ и через пятый элемент задержки с входом сброса третьего буферного регистра и входом сложения блока сложениявычитания, вход третьего регистра сдвига соединен с нулевым входом .триггера, через третий элемент зацержки с установочными входами четвертого регистра сдвига, входом пятого регистра сдвига, разрешающим входом второй схемы сравнения, выходом первого элемента И и через второй элемент задержки с вторым входом второго элемента ИЛИ, второй вход каждого элемента ИЛИ второй группы соединен с выходом соответствующего элемента И третьей группы, а выход — с соответствующим входом блока отображения графа, выходы которого соединены с входами шифратора, выходы шифратора соединены с первыми входами первой схем сравнения, входами блока сложения-вычита ния и первыми входами соответствующих элементов И второй группы, выходы которьас соединены с входами второго буферного регистра, выходы второго буферного регистра подключены к вторым входам первой схемы сравнения, выход которой соединен с объединенными вторыми входами элементов И второй группы и входом перезаписи первого буферного регистра, выходы блока сложения-вычитания соединены с входами третьего буферного регистра и первыми входами второй схемы сравнения, выход которой соединен с входом перезаписи третьего буферного регистра и управляющим входом матричного запоминающего блока, информационные входы которого соединены с информационными выходами буферного матричного запоминающего блока, выходы матрич нЬго запоминающего блока соединены с входами блока индикации, разрешающий вход которого подключен к выходу пятого регистра сдвига, а выходы третьего буферного регистра соединены с вторыми входами второй схемы срав- . нения.

1 1

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

Известно устройство для исследования графов, содержащее .узел перебо ра сочетаний, две группы элементов ЗАПРЕТ, наборное поле, два пороговых элемента, узел управления выбором направления, триггер, элемент И, генератор и мультивнбратор(11

Однако это устройство не позволяет решать задачу разбиения графа на подграфы.

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

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

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

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

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

З0 входами соответствующих последовательно соединенных ключей, выход каждого из элементов ИЛИ соединен с входом элемента И (31.

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

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

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

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

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

5 из которых состоит из триггера, двух элементов И и элемента ИЛИ, шифратор, блок сложения-вычитания, первая и вторая схемы сравнения, второй, третий, четвертый и пятый элементы задержки, четыре элемента ИЛИ, элемент НЕ, вторая и третья группы элементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок, буферный матричный запоминающий блок и блок индикации, причем выход генератора тактовых импульсов соединен с входами первого и второго счетчиков, выходы первого счетчика соединены с входами первого дешифратора, выходы второго счетчика через первый буферный регистр соединены с входами второго дешифратора, выходы которого соединены с первыми входами элементов И первой и четвертой групп, вторые входы элементов И пер-. вой группы объединены и подключены к выходу второго элемента И, сдвигающему входу первого регистра сдвига и объединенным единичным входам зо триггеров второй группы, выходы элементов И первой группы соединены с первыми входами соответствующих элементов ИЛИ первой группы, выходы второго регистра сдвига соединены с управляющими входами соответствующих З5 элементов буферного матричного запоминающего блока и через; узел коммутации с вторыми входами элементов ИЛИ первой группы, выход каждого элемента ИЛИ первой группы соединен с информационными входами буферного матричного запоминающего блока и единичным входом соответствующего триггера первой группы триггеров, нулевые входы триггеров первой группы объединены и соединены с объединенными первыми входами элементов ИЛИ третьей группы, входами установки в нуль первого и второго счетчиков, первого и второго регистров сдвига, ® .первым входом первого элемента ИЛИ и выходом второго элемента ИЛИ, единичный выход каждого триггера первой группы соединен с первыми входами элементов ИЛИ и первого эле- 5 мента И соответствующего узла перебора, вторым входом соответствующего элемента ИЛИ третьей группы и соот434 ветствующим .входом первого элемента И, второй вход элемента ИЛИ каждого узла перебора соединен с соответствующим выходом первого дешифратора, вторые входы первых элементов И узлов перебора объединены и подключены к выходу третьего элемента ИЛИ, выход первого регистра сдвига соединен с вторым входом первого элемента ИЛИ, входом второго регистра сдвига, входом вычитания блока сложения-вычитания и через первый элемент задержки с первым входом третьего элемента ИЛИ, второй вход которого является входом задания исходного состояния устройства, выход элемента ИЛИ каждого узла перебора соединен с первым входом второго элемента И узла перебора, второй вход которого соединен с нулевым выходом триггера узла перебора, единичный вход которого соединен с выходом первого. элемента И узла перебора, а нулевой вход — с выходом соответствующего элемента ИЛИ третьей группы, выходы вторых элементов И узлов перебора соединены с первыми входами соответствующих элементов И третьей группы, вторые входы которых соединены с нулевыми выходами соответствующих триггеров второй группы, нулевые входы которых подключены к выходам соответствующих элементов И четвертой группы и через дифференцирующие элементы к входам четвертого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторые входы элементов И четвертой группы объединены и подключены к выходу первого счетчика, управляющему входу четвертого регистра сдвига и первому входу второго элемента И, третьи входы элемен-. тов И четвертой группы объединены и подключены к нулевому выходу триггера и черезпоследователъно соединенные четвертый элемент задержки и элемент НЕ к второму входу второго элемента И, единичный вход триггера соединен с выходом четвертого регистра сдвига, информационные входы которого соединены с соответствующими выходами третьего регистра сдвига, установочные входы которого соединены с входом установки исходного состояния устройства, первыми входами элементов ИЛИ второй группы, первым вхо1086434

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

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

t0

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

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

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

На фиг. 3 приведена структурная схема устройства; на фиг. 2 — при1086434

8 мер графа1 на фиг. 3 — возможный вариант построения блока отображения графа, приведенного на фиг. 2.

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

1О сдвига 13, буферный матричный блок 14, группу триггеров 15„-15„, группу элементов ИЛИ 16, -16„, элемент ИЛИ 17, группу элементов ИЛИ 18 -, -18„, группу элементов И .191-19„, блоки 201-20 узлов перебора, элемент И 21, регистр сдвига 22, элемент задержки 23, элемент ИЛИ 24, элемент ИЛИ 25, блок 26 сложениявычитания, группу элементов И 27„- 20

-27, группу триггеров 28„-28h группу элементов И 29„-29„, группу триггеров 301-30, группу дифференцирующих элементов 31. -31,,элемент ИЛИ 32, триггер 33, элемент задержки 34, элемент НЕ 35, регистр сдвига 36, вход 37 установки исходного состояния устройства, группу элементов ИЛИ 381-38„, элемент задержки 39, буферный регистр 40, элемент задерж- 30 ки 41, регистр сдвига 42, схему сравнения 43, элемент задержки 44, блок 45 отображения графа, шифратор 46, схему сравнения 47, группу элементов И 48 -48п, буферный регистр 49, матричный запоминающий блок 50 и блок 51 индикации.

Возможный вариант построения блока 45 отображения графа, изображенного на фиг. 2, приведен на фиг.3.40

Каждому ребру графа соответствует двухвходовой элемент И 45 ° „i = 1, 2, 3, 4, 5.Каждый вход этого элемента И соединен с одним из входов блока, отображающих вершины графа, 45 в соответствии с топологией исходного графа.

Для подготовки устройства к работе выход переполнения счетчика 2 устанавливается на тот разряд, котоpbfA соответствует заданному числу вершин в исходном графе, а выход переполнения регистра сдвига 22 устанавливается на тот разряд, который . соответствует числу вершин подграфа с максимальной их мощностью. Блок 45 отображения графа настраивается на заданную топологию графа, для чеro входы блока, соответствующие вершинам графа, гибкими перемычками соединяются с соответствующими входами элементов И 45,. (фиг.3), Входы и выходы остальных многоразрядных узлов и блоков рассчитываются на максимальное число вершин и ребер в графе и соединяются между собой жестко.

Перед началом работы счетчики 2 и 3, регистры сдвига 10, 13, 22, 36 и 42, триггеры 15 -15„, буферные регистры 5 и 49 устайавлйваются в нулевое состояние. В буферный, регистр 40 записывается код (11...1),.

Узлом коммутации 12 k выходов регистра сдвига 13 в соответствующем порядке подключаются к единичным входам соответствующих триггеров 15„-15„, обеспечивая выбор по одной базовой вершине для каждого ( подграфа. Порядок подключения выходов регистра сдвига 13 к триггерам 15„-15„ определяется тем, какие вершины графа должны быть базовыми для соответствующих подграфов и в каком порядке будут формироваться подграфы. Например, если граф с числом вершин n = 30 необходимо разбить на три подграфа (т.е. к = 3) и базовыми вершинами должны быть 5-я, 11-я и 15-я, то подключая первый выход регистра сдвига 13 к триггеру 155, второй Выход — к триггеру 15„„ и третий выход — к триггеру 15 >, последовательно формируют первый подграф с 5-й базовой вершиной, второй подграф с 11-й базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии единичный потенциал будет только на одном, первом выходе регистра сдвига 13, т.е. формируется первый подграф, и перед началом работы только первый выход регистра сдвига 13 подключен к одному из триггеров 151-15„(в со-, ответствии с примером к 5-му триггеру 15 ) .

При подаче сигнала на шину уста.новки исходного состояния одновременно на все входы блока 45 отображения графа поступают единичные сигналы (см. фиг. 3), и на соответствующих выходах, в зависимости от конкретной топлогии графа, появляют/ ся единичные сигналы, число которых равно общемУ числу ребер, входящих в данный граф. Это число преобразу9,1086434

0

45 числом ребер.

В следующем цикле перебора всех вершин единичный сигнал подается в каждом такте уже на три вершины:

55 постоянно на.две — выбранную в преется шифратором 46 в соответствующий код и записывается в блок сложениявычитания 26 по сигналу, подаваемому на вход "Сложение", т.е. этот код складывается с нулевым кодом блока сложения-вычитания. По окончании формирования очередного подграфа из кода этого числа вычитается код числа внутренних (между вершинами, входящими в данный подграф) связей 1 каждого из подграфов.

Устройство работает следующим образом. .Каждый тактовый импульс, поступая с генератора 1 на счетчик 2, поочередно подключает каждый выход дешифратора 4 к соответствующему входу блока 45 отображения графа, т.е. подает поочередно на все п вершин графа единичный потенциал. В соответствии с этим в первом такте единичный потенциал подается на 5-ю вершину (пятый вход блока 45) как базовую для первого подграфа с 1-го выхода регистра сдвига 13 через узел коммутации 12, элемент ИЛИ 11, взведенный триггер 15,, элемент ИЛИ 18 Э элемент И 27, на втором входе которого постоянно присутствует единичный потенциал с триггера 28, далее через элемент И 29, на второй вход которого постоянно подается единичный потенциал с триггера 30, и далее через элемент ИЛИ 38 на пятый вход блока 45. Кроме того, в первом такте единичный потенциал подается и на 1-й вход блока 45 с первого выхода счетчика 2 через дешифратор 4, элемент ИЛИ 181 и так далее по описанной выше цепочке, только с индексом 1. Поэтому единичный потенциал присутствует на 1-м и 5-м входах блока 45, на соответствующих выходах блока 45 отображения графа появляются единичные потенциалы, т.е. соответствующих ребер, которые связывают 1-ю и 5-ю вершины. Чйсло ребер, инцидентных 1-й и 5-й вершинам, преобразуется шифратором 46 в соответствующий код, который сравнивается с кодом, поступающим на схему сравнения 47 с буферного регистра 49. В первом такте в регистре 49 записан код 00...0. Если код шифратора 46 больше кбда регистра 49, то схема сравнения 47 вырабатывает на своем выходе единичный сигнал, по которому код шифратора 46 через элемент И блока 48 переписывается в буферный регистр 49, а в буферный регистр 5 из счетчика 3 переписывается код номера вершины, в данном случае первой вершины (код 00...01) . Во втором такте единичный потенццал подается на 5-ю о вершину и на 2-ю вершину. Если число ребер, связывающих 2-ю и 5-ю вершины, меньше числа ребер, связывающих 1-ю и 5-ю вершины, то на выходе схемы сравнения 47 единичный сигнал не вырабатывается и содержимое счетчика 3 и регистра 49 не изменяется.

В противном случае сигнал вырабатывается, в буферный регистр 49 переписывается код, соответствующий числу ребер, связывающих „2-ю и 5-ю вершины, а в буферный регистр 5 код 00...10.

Таким образом, через и тактов все п выходов дешифратора 4 оказываются поочередно подключенными к входам блока 45 отображения графа, а в буферный регистр 5 записывается код номера вершины, имеющей с базовой (в примере — с 5-й) вершиной наибольшее число ребер. Следующий тактовый импульс формирует на выходе переполнения счетчика 2 единичный сигнал, который через открытый элемент И 9 продвигает единицу в регистр сдвига 22 и подает сигнал разрешения на элементы И 8 -8, так как на другой вход элемента И 9 подается инверсный сигнал с установленного в исходное состояние триггера 33. В результате этого единичный сигнал с того выхода дешифратора 6, который соответствует вершине,максимальным числом ребер связанной с 5-й;вершиной, поступает на соответствующий триггер блока 15

-15„и переводит его в единичное состояние до окончания формирования первого варианта разбиения графа на подграфы. Это означает, что в первый подграф вошли уже две вершины: базовая (5-я вершина) и вершина, связанная с ней наибольшим дыдущем цикле и базовую, и поочередно — на каждую из всех оставшихся.

По окончании этого цикла аналогич1086434

12 но предыдущему циклу выбирается вершина, имеющая максимальное число ребер, с двумя вершинами, выбранными в предыдущем цикле.

5

Процесс формирования первого подграфа окончится, когда в него войдет заданное число вершин. Признак этого — появление единичного сигнала на выходе регистра сдвига 22, кото- 10 рый поступает на регистр сдвига 13 и продвигает единицу на его второй выход, к которому подключен триггер 15 базовой вершины второго подграфа. Сигнал с выхода регистра 22 поступает через элемент задержки 23 и схему ИЛИ 24 на все вторые входы элементов И 19„-19, через элемент ИЛИ 25 (обнуляет) устанавливает в исходное состояние буферный 20 регистр 49, поступает на вход "Вычитание" блока 26 сложения-вычитания, в котором хранится код суммарного числа связей исходного графа.

Из этого кода вычитается код числа связей, соединяющих вершины, выбранные (включенные) в первый подграф.

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

При поступлении сигналов на вторые. входы элементов И 19. -19„, 35 на первые входы которых поданы единичные сигналы с триггеров 151-15>, соответствующих вершинам, отобранным в первый подграф, на выходе со- 40 ответствующих элементов И 19„-19> появляется единичный сигнал, который перебрасывает соответствующие триггеры 281-28>, поэтому закрываются соответствующие им элементы И 271—

-27» и на связанные с этими элементами входы блока 45 через соответст-. вующие открытые элементы И 29„-29„ и элементы ИЛИ 38„-38„ единичные сигналы поступать не будут, т.е. .отобранные в первый подграф вершины

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

Так как единичный сигнал присутствует уже на втором выходе регистра сдвига 13, то он подается на вторую базовую вершину, и аналогично рассмотренному выше формируется второй подграф. После окончания формирования второго подграфа на выходе регистра 22 появляется сигнал, который продвигает единицу в регистре 13 на третий выход. По следующему тактовому импульсу начинается формирование третьего подграфа и т.д, до тех пор, пока не будут сформированы все графы. Это значит, что ащцая вершина графа включена в какой-либо из подграфов, т.е. на выходе каждого из триггеров 15 -15 и присутствует единица, поэтому появляется сигнал на выходе элемента И 21, который поступает на.разрвшающий вход схемы сравнения 43. Этот сигнал разрешает сравнение кода, записанного в буферном регистре 40 (перед сравнением, после окончания первого разбиения, в нем записан максимально возможный код 11...1), с кодом, находящимся в блоке 26 сложения-вычитания и соответствующим числу связей между подграфами графа. Если код буферного регистра 40 больше кода блока 26 сложения-вычитания, то схема сравнения 43 вырабатывает сигнал, по которому код блока 26 сложения-вычитания переписы.вается в буферный регистр 40, а содержимое буферного матричного запоминающего блока 14 переписывается в матричнй запоминающий блок 50. Это означает, что запомнилось лучшее из предшествующих разбиений, т.е. какие вершины вошли в какой подграф и число связей между подграфами при таком разбиениф. Если же. содержимое буферного регистра 40 меньше содержимого блока 26 сложения-вычитания, то на выходе схемы сравнения сигнал не появляется и содержимое блоков 40 и 50 не изменяется.

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

Группа элементов, в которую входят регистры сдвига 10 и 36, группа элементов И 7 -7, группа триггеров 30„-30„, груйпа дифференцирующих элементов 31.,-31,, элемент ИЛИ 32, триггер 33, элементы задержки 34 и,41 и элемент НЕ 35, обеспечивает

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

Это достигается путем блокировки 5 вершины, которая была выбрана в первом варианте разбиения, в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в начале 1О формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой, будет выбрана другая .вершина, имеющая с базовой максимальное число связей, за 15 исключением вершины, которая бнла выбрана в первом варианте разбиения как максимально связанная, но которая в начале формирования второго варианта заблокирована. По окой- 20 чанни формирования первого варианта разбиения сигнал с И 21 прежде, чем поступить на вход элемента. ИЛИ 17 и привести все устройство в исходное состояние, перед началом формирования второго варианта разбиения. поступает на вход регистра сдвига 36 и продвигает единицу на его первый выход (верхний по схеме) 1 взводит триггер 33 и через элемент 30 задержки 41 поступает на регистр сдвига 10 по которому происходит перезапись информации из регистра 36 в регистр 10, но уже в инверсном коде. В регистре 36 по-прежнему остается код 100...0, а в регистре 10 — код 00...01,, который определяет время, на которое заблокирована перезапись информации из деши@ратора б в триггеры 15 -15, 4p

ll так как эта блокщМовка обеспечивается отсутствием сигнала на первом входе элемента И 9 через после-довательно соединенные триггер 33, элемент задержки 34 и элемент НЕ 35.

Сигнал с элемента И 21 через элемент задержки 44 поступает на вход элемента ИЛИ 17, который приводит устройство в исходное состояние.

Второй вариант разбиения начинается по очередному импульсу с ГТИ 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В качестве этой. вершины выбирается та же вершина, что и в первом разбиении (признак окончания выбора этой вершины — сигнал с выхода переполнения счетчика 2), однако она не включается в первый подграф (не взведен соответствующий триггер блока 15„-15„), так как .элемент И 9 по одному из входов заблокирован инверсным сигналом с нулевого выхода триггера 33. По этому же сигналу со счетчика 2 продвигается единица на выход переполнения регистра сдвига 10, в результате чего перебрасывается триггер 33 и разблокирует элемент И 9, т.е. после выбора следующей вершины (появления импульса на выходе счетчика 2) она включена в подграф. Во время выбора этой вершины вершина, выбранная на предыдущем шаге как максимальным числом связанная с базовой, должна быть заблокирована на входе блока 45 отображения графа, т.е. не должна участвовать в переборе вершин при поиске максимально связанной с базовой во втором варианте разбиения для того, чтобы она опять не быпа выбрана в подграфе . и процесс разбиения не пошел бы по той же ветви, что и при первом разбиении, т.е. чтобы не повторилось первое разбиение.

Блокировка этой вершины осуществляется следующим образом.

Перед началом поиска второго варианта разбиения включена (взведен триггер 33) только блокировка включения в подграф максимально связанной с базовой вершины, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вершины находится в буферном регистре 5, ее код подается на первые входы соответствующих элементов И 7 -7> на вторые входы которых подается сигнал с триггера 33.

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

1086434

16

15 блок элементов И 7,1-7, так как уже продвинута "единица" на выход переполнения регистра сдвига 10 и,. перебросив триггер в нулевое состояние, разблокирует цепь переза- 5 писи в триггеры 15„-15„.и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины.

Поэтому на выходе элемента И .9 появляется сигнал, который взводит все триггеры 30 -30, разблокировав тем самым заблокированную вершину. Кроме того, по появлению хотя бы одного импульса на выходах элементов И 7 -7„ сигналом с выхода элемента ИЛЙ 32 происходит обнуление буферного регистра 49 для того, чтобы во втором. шаге второго варианта разбиения сравнение проис ходило с кодом 00...0, а,не с кодом числа связей заблокированной вершины, В результате получают новый вариант разбиения графа на подграфы, лучший из которых запоминается в матричном запоминающем блоке. По окончании формирования второго варианта разбиения в регистр сдвига 36 будет записана и сдвинута еще одна единица.

Инверсный код регистра 36 переписывается в регистр сдвига 10 и определяет время блокировки включения вершины в подграф (взведение одного из триггеров 151-15 ), а также число вершин, которые необходимо блокировать на входе блока 45 отображения графа (исключать mr из просмотра).

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

43.

1086434

6

7r

j7

1086434

}086434

Ъ ф

Составитель С.Назаров

Техред М.Надь Корректор В.Гирняк

Редактор Л.Веселовская

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

Заказ 2243/46 .. - Тираж 699 Подписное

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

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