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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Указанная цель достигается тем, что в устройство для разбиения графа на подграфы, содержащее генератор тактовых импульсов, первую и вторую группу элементов И, первую группу элементов ШШ, элемент И, первую и вторую группы триггеров, блок отображения графа, первый и второй счетчики, первый элемент задержки, группу дифференцирующих элементов, введены пять регистров сдвига, два дешифратора, три буферных регистра, узел коммутации третья и четвертая группы элементов И, п блоков узлов перебора (п - число вершин графа), каждый из которых состоит из триггера, двух злементов И и элемента ИЛИ, шифратор, блок сложения-вьгчйтания, первая и вторая схемы сравнения, второй, третий, четвертый и пятьй элементы задержки,четыре элемента ИЛИ элемент НЕ, вторая и третья группы элементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок буферный матричный запомт нающий блок и блок индикации, -причем выход генератора тактовых импульсов соединен с входами первого и второго счет чиков, выходы первого счетчика соединены с входами первого дешифратора, выходы второго счетчика через первый буферный регистр соединены с входами второго дешифратора, выходы которого соединены с первыми входами элементов И первой и четвертой групп, вторые входы элементов И первой группы объединены и подключены к выходу второго элемента И, сдвиганицему входу первого регистра сдвига и объединенньм единичным входам триггеров второй группы, выходы элементов И первой группы соединены с первыми входами соответствукнцих элементов ИЖ первой группы, выходы вто рого регистра сдвига соединены с , управляющими входами соответствующих элементов буферного матричного запоминающего блока и через; узел коммутации с вторыми входами элементов ИЛ первой группы, выход каждого элемента ИЛИ первой группы соединен с информационньми входами буферного матричного запоминающего блока и еди ничным входом соответствующего триггера первой группы триггеров, нулевые входы триггеров первой группы объединены и соединены с объединенными первыми входами элементов ИЛИ третьей группы, входами установки в нуль первого и второго счетчиков, первого и второго регистров сдвига, первым входом первого элемента ИЛИ и выходом второго элемента ИЛИ, единичный выход каждого триггера первой группы соединен с первыми входами элементов ИЛИ и первого элемента И соответствующего узла перебора, вторым входом соответствующего элемента ИЛИ третьей группы и соответствующим входом первого элемента И, второй вход элемента ИЛИ каждого узла перебора соединен с соответствующим выходом первого дешифратора, вторые входы первых элементов И узлов перебора объединены и подключены к выходу третьего элемента ИЛИ, выход первого регистра сдвига соединен с вторым входом первого элемента ИЛИ, входом второго регистра сдвига, входом вычитания блока сложения-вычитания и через первьй элемент задержки с первым входом третьего элемента ИЛИ, второй вход которого является входом задания исходного состояния устройства, выход элемента ИЛИ каждого узла перебора соединен с первым входом второго элемента И узла перебора, второй вход которого соединен с нулевым выходом триггера узла перебора, единичный вход которого соединен с выходом первого, элемента И узла перебора, а нулевой вход - с выходом соответствующего элемента ИЛИ третьей группы, выходы вторых элементов И узлов перебора соединены с первыми входами соответствуннцих элементов И третьей группы, вторые входы которых соединены с нулевыми выходами соответствующих триггеров второй группы, нулевые входы которЬк подключены к выходам соответствующих злементов И четвертой группы и через дифференцирукяцие элементы к входам четвертого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторые элементов И четвертой группы объединены и подключены к выходу первого счетчика, управляющему входу четвёртого регистра сдвига и первому входу второго элемента И, третьи входы элементов И четвертой группы объединены и подключены к нулевому выходу триггера и черезпоследовательно соединенныечетвертый элемент задержки и элемент НЕ к второму входу второго элемента И, единичньй вход триггера соединен с выходом четвертого регистра сдвига, информационные входы которого соединены с соответствуинцими выходами третьего регистра сдвига, установочные входы которого соединены с входом установки исходного состояния устройства, первыми входами элементов ИЛИ второй группы, первым входом второго элемента ИЛИ и через пятый элемент задержки с входом сброса третьего буферного регистра и входом сложения блока сложениявычитания, вход третьего регистра сдвига соединен с нулевым входом триггера, через третий элемент задержки с установочными входами четвертого.регистра сдвига, входом пятого регистра сдвига, разрешающим входом второй схемы сравнения, выходом первого элемента Ни через второй элемент задержки с вторым входом второго элемента ИЛИ, второй вход каждого элемента ИЛИ второй группы соединен с выходом соответст вующего элемента И третьей группы, а выход - с соответствующим входом блока отображения графа, выходы которого соединены с входами шифратора, выходы шифратора соединены с первыми входами первой схемы сравнения, входами блока сложениявычитания и первыми входами соответ ствукяцих элементов И второй группы, выходы которьк соединены с входами второго буферного регистра, выходы второго буферного регистра подключены -к вторым входам первой схемы сравнения, выход которой соединен с объединенными вторыми входами элементов И второй группы и входом перезаписи первого буферного регист ра, выходы блока сложения-вычитания соединены с входами третьего буферного регистра и первыми входами второй схемы сравнения, выход которой соединен с входом перезаписи третьего буферного регистра и управ ляющим входом матричного запоминающего блока, информационные входы ко торого соединены с информационными выходами буферного матричного запоминающего блока, выходы матричного запоминающего блока соединены с вхо дами блока индикации, разрешакнций вход которого подклвочен к выходу Пятого регистра сдвига, а вькоды третьего буферного регистра соединены с вторыми входами второй схемы сравнения. Каждый вход блока отображения графа соответствует вершине графа, а каждый выход-ребру между любой парой вершин. Топология исходного графа задается блоком отображения графа таким образом, что при подач на его входы единичного сигнала он 4 появится на тех выходах, которые соответствуют ребрам, соединяющим вершины, на которые были поданы единичные сигналы. Это позволяет в каждом такте работы устройства осуществлять выбор той вершины графа, которая имеет наибольшее (наименьшее) число связей с множеством вершин, выбранных в предьщущем такте. Кроме того, в исходном состоянии с помощью узла коммутации выбирается некоторое число вершин, равное заданному числу подграфов, каждая из которых является базовой в соответствующем подграфе и к которой в процессе работы устройства присоединяются другие вершины графа. Процесс формирования каждого из подграфов графа заканчивается по сигналу с выхода переполнения первого регистра сдвига, так как число разрядов регистра равно числу вершин графа, которые должны быть объединены в один подграф. Формирование всех подграфов графа осуществляется последовательно и после окончания процесса исходный граф будет разбит на заданное число подграфов с локально-минимальным числом связей между ними. Полученный результат разбиения графа на подграфы будет записан в матричный запоминающий блок и отображен на блоке индикации, а суммарное число связей - в третьем буферном регистре. На следующем шаге оптима- зации из рассмотрения исключаются те вершины каждого из подграфов, которые быпи выбраны на первом шаге оптимизации в качестве вершин, имеющих максимальное число связей с базовой вершиной каждого из подграфов. В качестве новой вершины для кахдоо из подграфов „выбирается следунмцая по максимальной связности с базовой вершиной. Далее процесс формирования подграфов полностью аналогичен описанному. По получении разбиения после второго шага оптимизации производится сравнение результатов первого и в.торого шагов по суммарному числу связей между подграфами графа. В матричный запоминающий блок и в третий буферный регистр записываются результаты лучшего из двух полученных разбиений по минимуму указанного критерия. Далее процесс оптимизации протекает аналогично. На фиг. 1 приведена структурная схема устройства; на фиг. 2 - пример графаj на фиг. 3 - возможный вариант построения блока отображения графа приведенного на фиг. 2. Устройство содержит генератор 1 тактовых импульсов, счетчики 2 и 3, дешифратор 4, буферный регистр 5, дешифратор 6, группы элементов И и , элемент И 9, регистр сдвига 10, группу элементов ИЛИ 11-, -11, узел коммутации 12, регистр сдвига 13, буферный матричньй блок 14, группу триггеров , группу элементов ИЛИ , элемент ИЛИ 17, группу элементов ИЛИ 18 -18 , группу элементов И , блоки уэлов перебора, элемент И 21, регистр сдвига 22, элемент задержки 23, элемент ИЛИ 24, элемент ИЛИ 25, блок 26 сложениявычитания, группу элементов И 27 -27-, группу триггеров , груп пу элементов И , группу триг геров , группу дифференцирующих элементов ,элемент ИЛИ 3 триггер 33, элемент задержки 34, элемент НЕ 35, регистр сдвига 36, вход 37 установки исходного состояния устройства, группу элементов или , элемент задержки 39 буферньш регистр 40, элемент задерж ки 41, регистр сдвига 42, схему сра нения 43, элемент задержки 44, блок 45 отображения графа, шифратор 46, схему сравнения 47, группу элементов И 48,,-48, буферный регистр 49, матричный запоминающий блок 50 и блок 51 индикации. Возможный вариант построения блока 45 отображения графа, изображенного на фиг. 2, приведен на фиг. Каждому ребру графа соответствует двухвходовой элемент И 45,1 1, 2, 3, 4, 5.Каждый вход этого элемен та И соединен с одним из входов блока, отображающих вершины графа, в соответстйии с топологией исходного графа. Для подготовки устройства к рабо те выход переполнения счетчика 2 устанавливается на тот разряд, кото рый соответствует заданному числу вершин в исходном графе, а выход переполнения регистра сдвига 22 устанавливается на тот разряд, которы соответствует числу вершин подграфа с максимальной их мощностью.Блок 45 отображения графа настраивается на заданную топологию графа, для че ГО входы блока, соответствующие вершинам графа, гибкими перемычками соединяются с соответствующими входами элементов И 45 (фиг.З). Входы и выходы остальных многоразрядных узлов и блоков рассчитываются на максимальное число верщин и ребер в графе и соединяются между собой жестко. Перед началом работы счетчики 2 и 3, регистры сдвига 10, 13, 22, 36 и 42, триггеры , буферные регистры 5 и 49 устанавливаются в нулевое состояние. В буферный , регистр 40 записывается код (11 ... 1),. Узлом кo n yтaции 12 k выходов регистра сдвига 13 в соответствующем порядке подключаются к единичным входам соответствующих тригге- ров , обеспечивая выбор по одной базовой вершине для каждого подграфа. Порядок подключения выходов регистра сдвига 13 к триггерам определяется тем, какие вершины графа должны быть базовыми для соответствующих подграфов и в каком порядке будут формироваться подграфы. Например, если граф с числом вершин п 30 необходимо разбить на три подграфа (т.е. к 3) и базовыми вершинами должны быть 5-я, 11-я и 15-я, то подключая первый выход регистра сдвига 13 к триггеру 15с, второй выход - к триггеру 15 и третий выход - к триггеру , последовательно формир5тот первый подграф с 5-й базовой вершиной, второй подграф с 11-и базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии единичный потенциал будет только на одном, первом выходе регистра сдвига 13, т.е. формируется первый подграф, и перед началом работы только первый выход регистра сдвига 13 подключен к одному из триггеров , (в со-, ответствии с примером к 5-му триггеру 155). При подаче сигнала на шину установки исходного состояния одновременно на все входы блока 45 отображения графа поступают единичные сигналы (см. фиг. 3), и на соответствуюощх выходах, в зависимости от конкретной топлогии графа, появляются единичные сигналы, число которых равно общему числу ребер, входящих в данный граф. Это число преобразуется шифратором 46 в соответствующи код и записывается в блок сложениявычитания 26 по ёигналу, подаваемом на вход Сложение, т.е. этот код складывается с нулевым кодом блока сложения-вычитания. По окончании формирования очередного подграфа из кода этого числа вычитается код числа внутренних (между вершинами, входящими в данньй подграф) связей каждого из подграфов. Устройство работает следующим образом. .Каждьй тактовый импульс, поступа с генератора 1 на счетчик 2, поочередно подключает каждый выход дешиф ратора 4 к соответствующему входу блока 45 отображения графа, т.е. по дает поочередно на все п вершин гра фа единичньй потенциал. В соответст вии с этим в первом такте единичный потенциал подается на 5-ю вершину (пятый вход блока 45) как базовую для первого подграфа с 1-го выхода регистра сдвига 13 через узел коммутации 12, элемент ИЛИ 11с взведенный триггер 15,-, элемент ИЛИ 18 элемент И 27г, на втором входе которого постоянно присутствует единичньй потенциал с триггера 28, далее через элемент И 29, на второй вход которого постоянно подается единичный потенциал с триггера 30с и далее .через элемент ИЛИ 38 на пятый вход блока 45. Кроме того, в первом такте единичный потенциал подается и на 1-й вх.од блока 45 с первого выхода счетчика 2 через дешифратор 4, элемент ИЛИ 18,, и так далее по описанной выше цепочке только с индексом 1. Поэтому единич ный потенциал присутстйует на 1-м и 5-м входах блока 45, на соответст вующих выходах блока 45 отображения графа появляются единичные потенциа лы, т.е. соответствующих ребер, кот ) рые связывают 1-ю и 5-ю вершины. Чи ло ребер, инцидентных 1-й и 5-й вершинам, преобразуется шифратором 4 в соответствующий код, который срав нивается с кодом, поступающим на схему сравнения 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-йV вершиной, поступает на соответствующий триггер блока и переводит его в единичное состояние до окончания формирования первого варианта разбиения Графа на подграфы. Это означает, что в первьй подграф вошли уже две вершины: базовая (5-я вершина) и вершина, связанная с ней наибольшим числом ребер. В следующем цикле перебора всех вершин единичный сигнал подается в каждом такте уже на три вершины: постоянно на две - выбранную в предыдущем цикле и базовую, и поочередно - на каждую из всех оставшихся. По окончании этого цикла аналогично предьщущему циклу выбирается вершина, имекицая максимальное число ребер, с двумя вершинами, выбран ными в,-предыдущем цикле. Процесс формирования первого под графа окончится, когда в него войде заданное число вершин. Признак этого - появление единичного сигнала на выходе регистра сдвига 22, который поступает на регистр сдвига 13 и продвигает единицу на его второй выход, к которому подключен триггер 15 базовой вершины второго подграфа. Сигнал с выхода регистра 22 поступает через элемент задер ки 23 и схему ИЛИ 24 на все вторые входы элементов И 19-19., через элемент ИЛИ 25 (обнуляет) устанавли вает в исходное состояние буферный регистр 49, поступает на вход Вычитание блока 26 сложения-вычитания, в котором хранитсякод суммарного числа связей исходного графа. Из этого кода вычитается код числа связей, соединяющих вершины, выбран ные (включенные) в первый подграф. Элемент задержки 23 необходим для Tbroj успеть произвести вьше описы.нную операцию вычитания прежде чем -произойдет сброс сигналов с входов блока 45 отображения графа, соответствующих вершинам, включенным в первый подграф. При поступлении сигналов на вторые входы элементов И , ня первые входы которых поданы единичные сигналы с триггеров 15,-15, соответствующих вершинам, отобранным в первый подграф, на выходе соответствующих элементов И появляется единичный сигнал, которы перебрасывает соответствующие триггеры ., поэтому закрываются соответствующие им элементы И , и на связанные с этими элементами входы блока 45 через соответст вующие открытые элементы И и элементы ШШ единичные сигналы поступать не будут, т.е. отобранные в первый подграф вершины блокируются до конца получения первого варианта разбиения и не .участвуют в формировании оставшихся подграфов. Так как единичный сигнал присутствует уже на втором выходе регистра сдвига 13, то он подаётся на вторую базовую вершину, и аналогично рассмотренному выше формируется второй подграф. После окончания формирования второго подграфа на выходе регистра 22 появляется сигнал, который продвигает единицу в регистре 13 на третий выход. По следующему тактовому импульсу начинается фор1 р{рование третьего подграфа и т.д. до тех пор, пока не будут сформированы все графы. Это значит, что 1 аждая вершина графа включена в какой-либо из подграфов, т.е. на выходе каждого из триггеров 15-15 присутствует единица, поэтому появляется сигнал на выходе элемента И 21, который поступает на разрешающий вход схемы сравнения 43. Этот сигнал разрешает сравнение кода, записанного в буферном регистре 40 (перед сравнением, после окончания первого разбиения, в нем записан максимально возможный код 11... 1), с кодом, находящимся в блоке 26 сложения-вычитания и соответствующим числу связей между подграфами графа. Если код буферного регистра 40 больше кода блока 26 сложения-вычитания, то схема, сравнения 43 вырабатывает сигнал, по которому код блока 26 сложения-вычитания переписывается в буферный регистр 40, а содержимое буферного матричного запоминагацего блока 14 переписьшается в матричнй запоминающий блок 50. Это означает, что запомнилось лучшее из предшествующих разбиений, т.е. какие вершины вошли в какой подграф и число связей между подграфами при таком разбиени1. Если же. содержимое буферного регистра 40 меньше содержимого блока 26 сложения-вычитания, то на выходе схемы сравнения сигнал не появляется и содержимое блоков 40 и 50 не изменяется. Кроме того, сигнал с элемента И 21 поступает на регистр сдвига 42 и продвигает в нем единицу на один разряд ближе к выходу, появление единичного сигнала на котором приводит к выводу лучшего варианта разбиения на индикацию. Группа элементов, в которую входят регистры сдвига 10 и 36, группа элементов И 7., группа триггеров , группа дифференцирующих элементов ЗЦ-31, элемент ИЛИ 32, триггер 33, элементы задержки 34 и,41 и элемент НЕ 35, обеспечивает выбор новой ветви разбиения графа на подграфы с тем, чтобы процесс разбиения на втором цикле разбиения не пошел по уже проделанному пути. Это достигается путем блокировки вершины, которая бьша выбрана в пер вом варианте разбиения, в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в начале формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой,будет выбрана другая вершина, имеющая с базо вой максимальное число связей, за исключением вершины, которая бвша выбрана в первом варианте разбиения как максимально связанная, но которая в начале формирования второ го варианта заблокирована. По окойчании формирования первого варианта разбиения сигнал с И 21 прежде, чем поступить на вход элемента ИЛИ 17 и привести все устройство в исходное состояние, перед началом формирования второго варианта разбиения поступает на вход регистра сдвига 36 и продвигает единицу на его первьй выход (верхний по схеме), взводит триггер 33 и через элемент задержки 41 поступает на регистр .сдвига 10, по которому происходит перезапись информации из регистра 36 в регистр 10, но уже в инверс ном коде. В регистре 36 по-прежнему остается код 100...О, а в регист ре 10 - код 00...01, которьй определяет время, на которое заблокирована перезапись информации из дешифратора 6 в триггеры , так как эта блокировка обеспечивается отсутствием сигнала на первом входе элемента И 9 через последовательно соединенные триггер 33, элемент задержки 34 и элемент НЕ 35 Сигнал с элемента И 21 через эле мент задержки 44 поступает на вход элемента ИЛИ 17, который приводит устройство в исходное состояние. Второй вариант разбиения начинается по очередному импульсу с ГТИ 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В качестве этой вершины выбирается та же вершина, что и в первом разбиении (признак окончания выбора этой вершины - сигнал с выхода переполнения счетчика 2), од 414 нако она не включается в первьй подграф (не взведен соответствующий триггер блока 15.-15), так как элемент И 9 по одному из входов заблокирован инверсным сигналом с нулевого выхода триггера 33. По этому же сигналу со счегчика 2 продвигается единица на выход переполнения регистра сдвига 10, в результате чего перебрасывается триггер 33 и разблокирует элемент И 9, т.е. после выбора следующей вершины (появления импульса на выходе счетчика 2) она включена в подграф. Во время выбора этой вершины вершина, выбранная на предыдущем шаге как максимальным числом связанная с базовой, должна быть заблокирована на входе блока 45 отображения графа, т.е. не должна участвовать в переборе вершин при поиске максимально связанной с базовой во втором варианте разбиения для того, чтобы она опять не быпа выбрана в подграфе и процесс разбиения не пошел бы по той же ветви, что и при первом разбиении, т.е. чтобы не повторилось первое разбиение. Блокировка этой вершины осуществляется следующим образом. Перед началом поиска второго варианта разбиения включена (взведен триггер 33) только блокировка включения в подграф -максимально связанной с базовой вершины, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вершины находится в буферном регистре 5, ее код подается на первые входы соответствующих элементов И , на вторые входы которых подается сигнал с триггера 33. Поэтому после окончания первого просмотра по сигналу со счетчика 2 происходит установка соответствующего триггера в нулевое состояние, таким образом, эта вершина не участвует в процессе перебора вершин , во втором шаге второго варианта разбиения. После окончания этого шага в буферный регистр 5 записывается код вершины, максимальным числом связей соединенной с базовой, за исключением заблокированной. Однако код этой вершины не проходит через

блок элементов

так как

уже продвинута единица на выход переполнения регистра сдвига 10 и,перебросив триггер в нулевое состояние, разблокирует цепь перезаписи в триггеры и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины. Поэтому на вьрсоде элемента И 9 появляется сигнал, который взводит все триггеры ,, разблокировав- тем самым заблокированную вершину. Кроме того, по появлению хотя бы одного импульса на выходах элементов И 7/, сигналом с выхода элемента ИЖ-32 происходит обнуление буферного регистра 49 для того, чтобы во втором шаге второго ва1 ианта разбиения сравнение происходило с кодом 00...О, а .не с кодом числа связей заблокированной вершин

В результате получают новый вариант разбиения графа на подграфы,

лучший из которых запоминается в матричном запоминающем блоке. По окочании формирования второго варианта .разбиения в регистр сдвига 36 будет записана и сдвинута еще одна единица Инверсный код регистра 36 переписывается в регистр сдвига 10 и определяет время блокировки включения вершины в подграф (взведение o tHoro из триггеров ), а также число вершин, которые необходимо блокировать на входе блока 45 отображения графа (исключать их из просмотра). Таким образом, осуществляется выбор новой ветви разбиения и каждое последующее разбиение никогда не повторяет предыдущее, а выбор из них лучшего варианта разбиения по критерию минимума суммарного числа связей мезкду прдграфа№1 графа осу-ществляется по описанному выше принципу схемой сравнения 43. s V Ъ i Вторая nacfftb

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