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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 09) 34 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ скин ый, двух ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЗФ(71) Таганрогский радиотехниче институт им. В,Д.Калмыкова (53) 681.333(088.8)(56) 1. Авторское свидетельство СССР У 549810, кл. С 06 Р 15/20, 1974.2. Авторское свидетельство СССР В 679998, кл. С 06 С 7/48, 1977.3. Авторское свидетельство СССР У 656073, кл. С 06 Р 15/36, 1976 (прототип) .(54)(57) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФА НА ПОДГРАФЫ, содержащее генератор тактовых импульсов, первую и вторую группы элементов И, первую группу элементов ИЛИ, первый элемент И, первую и вторую группы триг" геров, блок отображения графа, первый и второй счетчики, первый эле,мент задержки, группу дифференцирующих элементов, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения определения номеров вершин каждого подграфа, в устройство введены пять регистров сдвига, два дешифратора, три буферных .регистра, узел коммутации, третья и четвертая группы элементов И, и блоков узлов перебора(и - число вершин графа), кажд из которых состоит из .триггера элементов И и элемента ИЛИ, шифратор, блок сложения-вычитания, первая и вторая схемы сравнения, второй, третий, четвертый и пятый элементы задержки, четыре элемента ИЛИ,элемент НЕ, вторая и третья группыэлементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок,буферный матричный запоминающийблок и блок индикации, причем выходгенератора тактовых импульсов соединен с входами первого и второгосчетчиков, выходы первого счетчикасоединены с входами первого дешифратора, выходы второго счетчика черезпервый буферный регистр соединеныс входами второго дешифратора, выходы которого соединены с первымивходами элементов И первой и четвертой групп, вторые входы элементов И первой группы объединены иподключены к выходу второго элемента И, сдвигающему входу первогорегистра сдвига и объединенным единичным аходам триггеров второй группы, выходы элементов И первой группы соединены с первыми входами соответствующих элементов ИЛИ первой группы, выходы второго регистра сдвигасоединены с управляющими входами соответствующих элементов буферногоматричного запоминающего блока и через узел коммутации с вторыми входами элементов ИЛИ первой группы, выход каждого элемента,ИЛИ первой группы соединен с информационными входами буферного матричного запоминающего блошка и единичным входом соответствующего триггера первой группытриггеров, нулевые входы триггеровпервой группы объединены и соедине,ны с объединенными первыми входамиэлементов ИЛИ третьей группы, входами установки в нуль первого и второ,го счетчиков, первого и второго регистров сдвига, первым входом перблок элементов И 7,1-7, так как уже продвинута "единица" на выход переполнения регистра сдвига 10 и, перебросив триггер в нулевое состояние, разблокирует цепь переза писи в триггеры 15-15.и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины. Поэтому на выходе элемента И .9 появляется сигнал, который взводит все триггеры 30-30, разблокировав тем самым заблокированную вершину. Кроме того, по появлению хотя бы одного импульса на выходах элементов И 7 -7 сигналом с выхода элемента ИЛЙ 32 происходит обнуление буферного регистра 49 для того, чтобы во втором шаге второго варианта разбиения сравнение происходило с кодом 000, а,не с кодом 20 числа связей заблокированной вершины,В результате получают новый вариант разбиения графа на подграфы,лучший из которых запоминается вматричном запоминающем блоке. По окончании формирования второго вариантаразбиения в регистр сдвига 36 будетзаписана и сдвинута еще одна единица.Инверсный код регистра 36 переписывается в регистр сдвига 10 и определяет время блокировки включениявершины в подграф (взведение одногоиз триггеров 151-15 ), а также числовершин, которые необходимо блокировать на входе блока 45 отображенияграфа (исключать их из просмотра).Таким образом, осуществляется выборновой ветви разбиения и каждое последующее разбиение никогда не повторяет предыдущее, а выбор из нихлучшего варианта разбиения по критерию минимума суммарного числа связей между подграфами графа осу ществляется по описанному выше принципу схемой сравнения43.1086434 иг,ирня 43/46. Тираж 699 ВНИИПИ Государственного комитета по делам изобретений и открыт 113035, Москва, Ж"35, Раушская нвого элемента ИЛИ и выходом второго элемента ИЛИ, единичный выход каждого триггера первой группы соединен с первыми входами элементов ИЛИ и первого элемента И соответствующего узла перебора, вторым входом соответствующего элемента ИЛИ тре" тьей группы и,соответствующим вхо.дом первого элемента И, второй вход элемента ИЛИ каждого узла перебора соединен с соответствующим выходом первого дешифратора, вторые входы первых элементов И узлов перебора объединены и подключены к выходу третьего элемента ИЛИ, выход первого регистра сдвига соединен с вторым входом первого элемента ИЛИ, входом второго регистра сдвига, входом вычитания рлока сложения- вычитания и через первый элемент задержки с первым входом третьего элемента ИЛИ, второй вход которого является входом задания исходного состояния устройства, выход. элемента ИЛИ каждого узла перебора, соединен с первым входом второго элемента И узла перебора, второй вход которого соединен с нулевым выходом триггера узла перебора, единичный вход которого соединен с выходом первого элемента И узла перебора, а нулевой вход - с выходом соответствующего элемента ИЛИ третьей группы, выходы вторых элементов И узлов перебора соединены с первыми входами соответствующих элементов И третьей группы, вторые входы которых соединены с нулевыми выходами соответствующих триггеров второй группы, нулевые входы которых подключены к выходам соответствующих элементов И четвертой группы и через дифференцирующие элементы к входам четвертого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторые входы элементов И четвертой группыобъединены и подключены к выходупервого счетчика, управляющему входучетвертого регистра сдвига и первому входу второго элемента И, третьивходы элементов И четвертой группыобъединены и подключены к нулевомувыходу триггера и через последовательно соединенные четвертый элемент задержки и элемент НЕ к второму входу второго элемента И, единич"ный вход триггера соединен с выходом четвертого регистра сдвига, информационные входы которого соединены с соответствующими выходами третьего регистра сдвига, установочные входы которого соединены с входом установки исходного состояния устройства, первыми входами элементов ИЛИвторой группы, первым входом второго элемента ИЛИ и через пятый элемент задержки с входом сброса третьего буферного регистра и входом сложения блока сложения- вычитания, вход третьего регистра сдвига соединен с нулевым входом триггера, через третий элемент зацержки с установочными входами четвертого регистра сдвига, входом пятого регистра сдвига, разрешающим входом второй схемы сравнения, выходом первого элемента И и через второй элемент задержки с вторым входом второго элемента ИЛИ, второй вход каждого элемента ИЛИ второй группы соединен с выходом соответствующего элемента И третьей группы, а выход - с соответствующим входом блока отображения графа, выходы которого соединены с входами шифратора, выходы шифратора соединены с первыми входами первой схем сравнения, входами блока сложения-вычита ния и первыми входами соответствующих элементов И второй группы, выходы которьйс соединены с входами второго буферного регистра, выходы второго буферного регистра подключены к вторым входам первой схемы сравнения, выход которой соединен с объединенными вторыми входами элементов И второй группы и входом перезаписи первого буферного регистра, выходы блока сложения-вычитания соединены с входами третьего буферного регистра и первыми входами второй схемы сравнения, выход которой соединен с входом перезаписи третьего буферного регистра и управляющим входом матричного запоминающего блока, информационные входы которого соединены с информационными выходами буферного матричного запоминающего блока, выходы матрич-ного запоминающего блока соединены с входами блока индикации, разрешающий вход которого подключен к выходупятого регистра сдвига, а выходы третьего буферного регистра соединеныс вторыми входами второй схемы срав-,нения.086434 2жения графа, входом соответствующего триггера вершин и первым входом элемента ИЛИ блока элементов ИЛИ и 1Устройство относится к вычислительной технике и может быть исполь"зовано для построения сцепиализированных вычислительных устройств,предназначенных для решения задачикомпоновки электронных схем.Известно устройство для исследования графов, содержащее .узел перебора сочетаний, две группы элементов ЗАПРЕТ, наборное поле, два пороговых элемента, узел управления выбором направления, триггер, элемент И, генератор и мультивнбратор 11Однако это устройство не позволяет решать задачу разбиения графана подграфы.Известно также устройство для определения числа деревьев графа;содержащее блок перебора сочетаний,запоминающие триггеры, первый входкаждого из которых соединен с соответствующим выходом блока переборасочетаний, элементы ИЛИ, выход каждого из которых соединен с вторымвходомосоответствующего запоминающего триггера, управляемые ключевыесхемы, ключи, первыми входами соединенные с выходами запоминающих триггеров и управляемых ключевых схем,счетчики дуг, схему сравнения, входами соединенную с выходами счетчиков дуг, выходы которых соединеныс выходами ключей, последовательносоединенные счетчик цепей,.элемент НЕ и элементы И, выход схемысравнения соединен с входом счетчика цепей, выход которого соединенс вторьии выходами ключей 2.Недостатком устройства являетсяневозможность его применения для решения задачи компоновки электронныхсхем,Наиболее близким к предлагаемомупо техническому решению является устройство для моделирования. характеристик графа, содержащее шину запуска генератора им-,пульсов, подключенную к генераторуимпульсов, шину окончания испытания,соединенную с выходом элементов Ии генератором импульсов, выход которого соединен с входом счетчика ичерез элемент задержки с входамиключей, второй вход каждого из которых соединен с единичным выходомсоответствующего триггера вершиныи одним из входов соответствующегоключа вершины, второй вход каждогоиз которых соединен с блоком отобра выходом соответствующего ключа, нулевой выход каждого из триггероввершин соединен с входами соответствующего ключа и вторым входом элемента ИЛИ, а также через последовательно соединенные блок дифференци О рирования, ключи и счетчик с распределителем, к другому входу которогоподключена шина опроса, а каждыйиз выходов соединен со счетчикомчастей графа, шина установки триггЬ ров вершин соединена с каждым из,триггеров и ключом, другой вход каждого из триггеров вершин соединенс шинами результатов розыгрыша вершин, шина установки триггеров ре О бер соединена с каждым из. входовустановки триггеров ребер, другойвход каждого из которых соединен сшинами результатов розыгрыша ребер,выход каждого из этих триггеров 25 через ключи ребер соединен с блокомотображения графа, шина отсутствиявершин в розыгрыше подключена к выходу последовательно соединенныхключей, входы ключей соединены свходами соответствующих последовательно соединенных ключей, выходкаждого из элементов ИЛИ соединенс входом элемента И 31.Однако известное устройство мо,жет быть использовано только для решения задачи анапиза числа подграфов и размера каждого подграфа, ноне может быть использовано при решении задач синтеза, т,е. разбиении 4 О исходного связного графа на подграфы с оптимизацией числа связей между подграфами и определением номеров вершин в каждом подграфе.Целью изобретения является рас ширение функциональных возможностейустройства путем обеспечения определения номеров вершин каждого подграфа.Указанная цель достигается тем,что в устройство для разбиения графа на подграфы, содержащее генератор тактовых импульсов, первую ивторую группу элементов И, первуюгруппу элементов ИЛИ, первый элемент И, первую и вторую группы триггеров, блок отображения графа, первый и второй счетчики, первый элемент задержки, группу дифференцирующих элементов, введены пять регист10863ров сдвига, два дешифратора, трибуферных регистра, узел коммутациитретья и четвертая группы элементов И, и блоков узлов перебора(и - .число вершин графа), каждый5из которых состоит из триггера,двух элементов И и элемента ИЛИ,шифратор, блок сложения-вычитания,первая и вторая схемы сравнения,второй, третий, четвертый и пятыйэлементы задержки, четыре элемента ИЛИ,элемент НЕ, вторая и третья группыэлементов ИЛИ, триггер, второй элемент И, матричный запоминающий блок,буферный матричный запоминающийблок и блок индикации, причем выходгенератора тактовых импульсов соединен с входами первого и второго счетчиков, выходы первого счетчика соединены с входами первого дешифратора, выходы второго счетчика черезпервый буферный регистр соединеныс входами второго дешифратора, выходы которого соединены с первыми входами элементов И первой и четвертойгрупп, вторые вхоДы элементов И пер-.вой группы объединены и подключенык выходу второго элемента И, сдвигающему входу первого регистра сдвига и объединенным единичным входамтриггеров второй группы, выходы элементов И первой группы соединены спервыми входами соответствующих элементов ИЛИ первой группы, выходы второго регистра сдвига соединены суправляющими входами соответствующих З 5элементов буферного матричного запоминающего блока и через, узел коммутации с вторыми входами элементов ИЛИпервой группы, выход каждого элемента ИЛИ первой группы соединен синформационными входами буферногоматричного запоминающего блока и единичным входом соответствующего триггера первой группы триггеров, нулевые входы триггеров первой группыобъединены и соединены с объединенными первыми входами элементов ИЛИтретьей группы, входами установкив нуль первого и второго счетчиков,первого и второго регистров сдвига, 5 Опервым входом первого элемента ИЛИи выходом второго элемента ИЛИ,единичный выход каждого триггерапервой группы соединен с первымивходами элементов ИЛИ и первого элемента И соответствующего узла перебора, вторым входом соответствующегоэлемента ИЛИ третьей группы и соот 434ветствующим входом первого элемента И, второй вход элемента ИЛИ каждого узла перебора соединен с соответствующим выходом первого дешифратора, вторые входы первых элементов И узлов перебора объединены и подключены к выходу третьего элемента ИЛИ, выход первого регистра сдвига соединен с вторым входом первого элемента ИЛИ, входом второго регистра сдвига, входом вычитания блока сложения-вычитания и через первый элемент задержки с первым входом третьего элемента ИЛИ, второй вход которого является входом задания исходного состояния устройства, выход элемента ИЛИ каждого узла перебора соединен с первым входом второго элемента И узла перебора, второй вход которого соединен с нулевым выходом триггера узла перебора, единичный вход которого соединен с выходом первого. элемента И узла перебора, а нулевой вход - с выходом соответствующего элемента ИЛИ третьей группы, выходы вторых элементов И узлов перебора соединены с первыми входами соответствующих элементов И третьей группы, вторые входы которых соединены с нулевыми выходами соответствующих триггеров второй группы, нулевые входы которых подключены к выходам соответствующих элементов И четвертой группы и через дифференцирующие элементы к входам четвертого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторые входы элементов И четвертой группы объединены и подключены к выходу первого счетчика, управляющему входу четвертого регистра сдвига и первому входу второго элемента И, третьи входы элемен-. тов И четвертой группы объединены и подключены к нулевому выходу триггера и черезпоследователъно соединенные четвертый элемент задержки и элемент НЕ к второму входу второго элемента И, единичный вход триггера соединен с выходом четвертого регистра сдвига, информационные входы которого соединены с соответствующими выходами третьего регистра сдвига, установочные входы которого соединены с входом установки исходного состояния устройства, первыми входами элементов ИЛИ второй группы, первым вхо45 50 55 дом второго элемента ИЛИ и черезпятый элемент задержки с входомсброса третьего буферного регистраи входом сложения блока сложениявычитания, вход третьего регистрасдвига .соединен с нулевым входомтриггера, через третий элементзадержки с установочными входамичетвертого. регистра сдвига, входомпятого регистра сдвига, разрешающимвходом второй схемы сравнения, выходом первого элемента И и черезвторой элемент задержки с вторымвходом второго элемента ИЛИ, второйвход каждого элемента ИЛИ второйгруппы соединен с выходом соответствующего элемента И третьей группы,а выход - с соответствующим входомблока отображения графа, выходыкоторого соединены с входами шифратора, выходы шифратора соединеныс первыми входами первой схемысравнения, входами блока сложениявычитания и первыми входами соответствующих элементов И второй группы,выходы которых соединены с входамивторого буферного регистра, вьмодывторого буферного регистра подключены к вторым входам первой схемы.сравнения, выход которой соединенс объединенными вторыми входамиэлементов И второй группы и входомперезаписи первого буферного регистра, выходы блока сложения-вычитаниясоединены с входами третьего буферного регистра и первыми входамивторой схемы сравнения, выход кото-.рой соединен с входом перезаписитретьего буферного регистра и управляющим входом матричного запоминающего блока, информационные входы ко-.торого соединены с информационнымивьмодами буферного матричного запоминающего блока, выходы матричногозапоминающего блока соединены с входами блока индикации, разрешающийвход которого подключен к выходупятого регистра сдвига, а вьмодытретьего буферного регистра соединены с вторыми входами второй схемысравнения. Каждый вход блока отображенияграфа соответствует вершине графа,а каждый выход-ребру между любойпарой вершин. Топология исходногографазадается блоком отображенияграфа таким образом, что при подачена его входы единичного сигнала он 5 10 5 20 25 30 35 появится на тех выходах, которыесоответствуют ребрам, соединяющимвершины, на которые были поданыединичные сигналы. Это позволяетв каждом такте работы устройстваосуществлять выбор той вершины графа, которая имеет наибольшее (наименьшее) число связей с множествомвершин, выбранных в предыдущемтакте. Кроме того, в исходном состоянии с помощью узла коммутациивыбирается некоторое число вершин,равное заданному числу подграфов,каждая из которых .является базовойв соответствующем подграфе и к которой в процессе работы устройстваприсоединяются другие вершины графа.Процесс формирования каждого изподграфов графа заканчивается посигналу с выхода переполнения первого регистра сдвига, так как числоразрядов регистра равно числу вершинграфа, которые должны быть объединены в один подграф. Формированиевсех подграфов графа осуществляетсяпоследовательно и после окончанияпроцесса исходный граф будет разбитна заданное число подграфов слокально-минимальным числом связей междуними. Полученный результат разбиенияграфа на подграфы будет записан вматричный запоминающий блок и отображен на блоке индикации, а суммарноечисло связей - в третьем буферномрегистре. На следующем шаге оптимазации из рассмотрения исключаютсяте вершины каждого из подграфов,которые были выбраны на первом шагеоптимизации в качестве вершин, имеющих максимальное число связей с базовой вершиной каждого из подграфов.В качестве новой вершины для каждого из подграфов. выбирается следующая по максимальной связности с базовой вершиной, Далее процесс формирования подграфов полностью аналогичен описанному. По получении разбиения после второго шага оптимизации производится сравнение результатов первого и второго шагов по суммарному числу связей между подграфами графа. В матричный запоминающий блок и в третий буферный регистр записываются результаты лучшего из двух полученных разбиений по минимуму указанного критерия. Далее процесс оптимизации протекает аналогично.На фиг. 1 приведена структурная схема устройства; на фиг, 2 - пример графа 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 -,-27 п, группу триггеров 28-28 п, группу элементов И 29-29, группу триггеров 301-30 , группу дифференцирующих элементов 31. -31 элемент ИЛИ 32,триггер 33, элемент задержки 34,элемент НЕ 35, регистр сдвига 36,вход 37 установки исходного состояния устройства, группу элементов ИЛИ 38-38, элемент задержки 39,буферный регистр 40, элемент задержки 41, регистр сдвига 42, схему сравнения 43, элемент задержки 44,блок 45 отображения графа, шифратор 46, схему сравнения 47, группуэлементов И 48-48 п, буферный ре- З 5гистр 49, матричный запоминающийблок 50 и блок 51 индикации.Возможный вариант построенияблока 45 отображения графа, изображенного на фиг. 2, приведен на фиг.3.40Каждому ребру графа соответствуетдвухвходовой элемент И 45 ,1 = 1,2, 3, 4, 5.Каждый вход этого элемента И соединен с одним из входовблока, отображающих вершины графа, 45в соответствии с топологией исходного графа,1Для подготовки устройства к работе выход переполнения счетчика 2 устанавливается на тот разряд, который соответствует заданному числу вершин в исходном графе,.а выход переполнения регистра сдвига 22 устанавливается на тот разряд, который . соответствует числу вершин подграфа с максимальной их мощностью, Блок 45 отображения графа настраиваетсяна заданную топологию графа, для чего входы блока, соответствующие вершинам графа, гибкими перемычками соединяются с соответствующими входами элементов И 45,. (фиг.3), Входы и выходы остальных многоразрядных узлов и блоков рассчитываются на максимальное число вершин и ребер в графе и соединяются между собой жестко.Перед началом работы счетчики 2 и 3, регистры сдвига 10, 13, 22, 36 и 42, триггеры 151-15, буферные регистры 5 и 49 устайавлйваются в нулевое состояние. В буферный, регистр 40 записывается код (111),. Узлом коммутации 12 М выходов регистра сдвига 13 в соответствующем порядке подключаются к единичным входам соответствующих триггеров 15-15, обеспечивая выбор по одной базовой вершине для каждого(подграфа. Порядок подключения выходов регистра сдвига 13 к триггерам 15-15 определяется тем, какие вершины графа должны быть базовыми для соответствующих подграфов и в каком порядке будут формироваться подграфы. Например, если граф с числом вершин п = 30 необходимо разбить на три подграфа (т,е. к = 3) и базовыми вершинами должны быть 5-я, 11-я и 15-я, то подключая первый выход регистра сдвига 13 к триггеру 155, второй выход - к триггеру 15 й третий выход - к триггеру 15, последовательно формируют первый подграф с 5-й базовой вершиной, второй подграф с 11-й базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии единичный потенциал будет только на одном, первом выходе регистра сдвига 13, т.е. формируется первый подграф, и перед началом работы только первый выход регистра сдвига 13 подключен к одному из триггеров 151-15 (в со-, ответствии с примером к 5-му тригге- РУ 15).При подаче сигнала на шину уста.новки исходного состояния одновременно на все входы блока 45 отображения графа поступают единичные сигналы (см, фиг. 3), и на соответствующих выходах, в зависимости от конкретной топлогии графа, появляют/ся единичные сигналы, число которыхравно общемУ числу ребер, входящихв данный граф, Это число преобразуется шифратором 46 в соответствующийкод и записывается в блок сложения"вычитания 26 по сигналу, подаваемомуна вход "Сложение", т.е. этот кодскладывается с нулевым кодом блокасложения-вычитания. По окончанииформирования очередного подграфаиз кода этого числа вычитается кодчисла внутренних (между вершинами,входящими в данный подграф) связей 1каждого из подграфов,0 15 20 25 35 40 45 числом ребер. В следующем цикле перебора всехвершин единичный сигнал подаетсяв каждом такте уже на три вершины:55постоянно на две - выбранную в преУстройство работает следующим образом..Каждый тактовый импульс, поступая с генератора 1 на счетчик 2, поочередно подключает каждый выход дешифратора 4 к соответствующему входу блока 45 отображения графа, т.е. подает поочередно на все п вершин графа единичный потенциал. В соответствии с этим в первом такте единичный потенциал подается на 5-ю вершину (пятый вход блока 45) как базовую для первого подграфа с 1-го выхода регистра сдвига 13 через узел коммутации 12, элемент ИЛИ 11, взведенный триггер 15 элемент ИЛИ 18 элемент И 27 , на втором входе которого постоянно присутствует единичный потенциал с триггера 285, далее через элемент И 29, на второй вход которого постоянно подается единичный потенциал с триггера 30, и далее через элемент ИЛИ 385 на пятый вход блока 45. Кроме того, в первом такте единичный потенциал подается и на 1-й вход блока 45 с первого выхода счетчика 2 через дешифратор 4, элемент ИЛИ 181 и так далее по описанной выше цепочке, только с индексом 1. Поэтому единичный потенциал присутствует на 1-м и 5-м входах блока 45, на соответствующих выходах блока 45 отображения графа появляются единичные потенциалы, т.е. соответствующих ребер, которые связывают 1-ю и 5-ю вершины. Чйсло ребер, инцидентных 1-й и 5-й вершинам, преобразуется шифратором 46 в соответствующий код, который сравнивается с кодом, поступающим на схему сравнения 47 с буферного регистра 49. В первом такте в регистре 49 записан код 000. Если код шифратора 46 больше кода регистра 49, то схема сравнения 47 вырабатывает на своем выходе единичный сигнал, по которому код шифратора 46 через элемент И блока 48 переписывается в буферный регистр 49, а в буферный регистр 5 из счетчика 3 переписывается код номера вершины, в данном случае первой вершины (код 0001) . Во втором такте единичный потенццал подается на 5-юо вершину и на 2-ю вершину. Если число ребер, связывающих 2-ю и 5-ю вершины, меньше числа ребер, связывающих 1-ю и 5-ю вершины, то на выходе схемы сравнения 47 единичный сигнал не вырабатывается и содержимое счетчика 3 и регистра 49 не изменяется. В противном случае сигнал вырабатывается, в буферный регистр 49 переписывается код, соответствующий числу ребер, связывающих 2-ю и 5-ю вершины, а в буферный регистр 5 код 0010.Таким образом, через и тактов все п выходов дешифратора 4 оказываются поочередно подключенными к входам блока 45 отображения графа, а в буферный регистр 5 записывается код номера вершины, имеющей с базовой (в примере - с 5-й) вершиной наибольшее число ребер. Следующий тактовый импульс формирует на выходе переполнения счетчика 2 единичный сигнал, который через открытый элемент И 9 продвигает единицу в регистр сдвига 22 и подает сигнал разрешения на элементы И 8-8, так как на другой вход элемента И 9 подается инверсный сигнал с установленного в исходное состояние триггера 33. В результате этого единичный сигнал с того выхода дешифратора 6, который соответствует вершине,максимальным числом ребер связанной с 5-й;вершиной, поступает на соответствующий триггер блока 151 -15 и переводит его в единичное состояние до окончания формирования первого варианта разбиения графа на подграфы. Это означает, что в первый подграф вошли уже две вершины: базовая (5-я вершина) и вершина, связанная с ней наибольшим дыдущем цикле и базовую, и поочередно - на каждую из всех оставшихся,По окончании этого цикла аналогично предыдущему циклу выбираетсявершина, имеющая максимальное число ребер, с двумя вершинами, выбранными в.предыдущем цикле. 45 5Процесс формирования первого подграфа окончится, когда в него войдет заданное число вершин, Признак этого - появление единичного сигнала на выходе регистра сдвига 22, кото рый поступает на регистр сдвига 13 и продвигает единицу на его второй выход, к которому подключен триггер 15 базовой вершины второго подграфа. Сигнал с выхода регистра 22 поступает через элемент задержки 23 и схему ИЛИ 24 на все вторые входы элементов И 19-19 , через элемент ИЛИ 25 (обнуляет) устанавливает в исходное состояние буферный 20 регистр 49, поступает на вход "Вычитание" блока 26 сложения-вычитания, в котором хранится код суммарного числа связей исходного графа. Из этого кода вычитается код числа 25 связей, соединяющих вершины, выбранные (включенные) в первый подграф. Элемент задержки 23 необходим для того, чтобы успеть произвести выше описанную операцию вычитания прежде, чем произойдет сброс сигналов с входов блока 45 отображения графа, соответствующих вершинам, включен" ным в первый подграф.При поступлении сигналов на вторые. входы элементов И 19. -19,35 на первые входы которых поданы единичные сигналы с триггеров 151-15 соответствующих вершинам, отобранным в первый подграф, на выходе со ответствующих элементов И 19-19 появляется единичный сигнал, который перебрасывает соответствующие триггеры 281-28, поэтому закрываются соответствующие им элементы И 271 - -27 д, и на связанные с этими элементами входы блока 45 через соответст-, вующие открытые элементы И 29-29 и элементы ИЛИ 38-38 ъ единичные сигналы поступать не будут, т.е, ф .отобранные в первый подграф вершины50 блокируются до конца получения первого варианта разбиения и не .участвуют в формировании оставшихся подграфов.Так как единичный сигнал присутствует уже на втором выходе регистра сдвига 13, то он подается на вторую базовую вершину, и аналогично рассмотренному выше формируетсявторой подграф. После окончанияформирования второго подграфа на выходе регистра 22 появляется сигнал,который продвигает единицу в регистре 13 на третий выход. По следующему тактовому импульсу начинаетсяформирование третьего подграфа ит.д, до тех пор, пока не будут сформированы все графы. Это значит, чтовалдая вершина графа включена в какой-либо из подграфов, т.е. на выходе каждого из триггеров 15 -15лприсутствует единица, поэтому появляется сигнал на выходе элемента И 21, который поступает на.разрвшающий вход схемы сравнения 43, Этотсигнал разрешает сравнение кода, записанного в буферном регистре 40(перед сравнением, после окончанияпервого разбиения, в нем записанмаксимально возможный код 111),с кодом, находящимся в блоке 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, обеспечиваетвыбор новой ветви разбиения графа на подграфы с тем, чтобы процесс разбиения на втором цикле разбиения не пошел по уже проделанному пути, Это достигается путем блокировки 5 вершины, которая была выбрана в первом варианте разбиения, в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в .начале формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой, будет выбрана другая .вершина, имеющая с базовой максимальное число связей, за 15 исключением вершины, которая бнла выбрана в первом варианте разбиения как максимально связанная, но которая в начале формирования второго варианта заблокирована. По окой чанни формирования первого варианта разбиения сигнал с И 21 прежде, чем поступить на вход элемента ИЛИ 17 и привести все устройство в исходное состояние, перед началом форми рования второго варианта разбиения. поступает на вход регистра сдвига 36 и продвигает единицу на его первый выход (верхний по схеме) 1 взводит триггер 33 и через элемент 30 задержки 41 поступает на регистр сдвига 10, по которому происходит перезапись информации из регистра 36 в регистр 10, но уже в инверсном коде. В регистре 36 по-прежнему остается код 1000, а в регистре 10 - код 0001,. который определяет время, на которое заблокирована перезапись информации из дешифратора б в триггеры 15 -15 , 4 рпф так как эта блокщМрвка обеспечивается отсутствием сигнала на первом входе элемента И 9 через после- . довательно соединенные триггер 33, элемент задержки 34 и элемент НЕ 35, 45Сигнал с элемента И 21 через элемент задержки 44 поступает на вход элемента ИЛИ 17, который приводит устройство в исходное состояние. Второй вариант разбиения начинается по очередному импульсу с ГТИ 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В качестве этой вершины выбирается та же вершина, что и в первом разбиении (признак окончания выбора этой вершины - сигнал с выхода переполнения счетчика 2), однако она не включается в первыйподграф (не взведен соответствующийтриггер блока 15-15), так какэлемент И 9 по одному из входов заблокирован инверсным сигналом с нулевого выхода триггера 33. По этомуже сигналу со счетчика 2 продвигается единица на выход переполнениярегистра сдвига 10, в результатечего перебрасывается триггер 33 иразблокирует элемент И 9, т.е.после выбора следующей вершины (появления импульса на выходе счетчика 2)она включена в подграф. Во времявыбора этой вершины вершина, выбранная на предыдущем шаге как максимальным числом связанная с базовой,должна быть заблокирована на входеблока 45 отображения графа, т,е,не должна участвовать в переборевершин при поиске максимальносвязанной с базовой вовтором варианте разбиения для того, чтобы онаопять не быпа выбрана в подграфеи процесс разбиения не пошел быпо той же ветви, что и при первомразбиении, т.е, чтобы не повторилось первое разбиение. Блокировка этой вершины осуществляется следующим образом.Перед началом поиска второго варианта разбиения включена (взведен триггер 33) только блокировка включения в подграф максимально связанной с базовой вершины, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вершины находится в буферном регистре 5, ее код подается на первые входы соответствующих элементов И 7 -7, на вторые входы которых подается сигнал с триггера 33. Поэтому после окончания первого просмотра по сигналу со счетчика 2 происходит установка соответствующего триггера в нулевое состояние, таким образом, эта вершина не участвует в процессе перебора вершин во втором шаге второго варианта разбиения. После окончания этого шага в буферный регистр 5 записывается кбд вершины, максимальным числом связей соединенной с базовой, за исключением заблокированной, Однако код этой вершины не проходит через