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

СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) (11) 51) 4 С 0615 ПИСАНИЕ ИЗОБРЕТЕН ЪХБ)1. О.ных в оз обеспеч графа н фы. Уст н ения возможности разбиенияа минимально связанные подграройство обеспечивает возможасть задавать объемы подграфов и определять вершины, обладающие максимальным числом связей с вершинами, включенными в Йормируемый подграф. С этой целью информация о топологии исследуемого графа заносится в матрицу, после чего инициируется один из входов задания начальной вершины первого подграфа устройства. Аппаратные средстваустройства обеспечивают последовательный опрос триггеров мат- рицы ианализ связностивыбираемых подграфов, Коды номеров вершин подграфа, Е обладающего минимальной связностью, заносятся в блок памяти. 1 ил.С: юл. У 31 Я.И,Скорин во СССР1982.СССРО, 1982.НИЯ ГРАФА к вычисбыть изированновки й аппара- обретенкциональГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ РАЗБИВНА ПОДГРАФ(57) Изобретение относитсялительной технике, можетиспользовано при автомат м решении задач комплементов радиоэлектронуры в блоки. Целью я является Расширение ф жностей устройства за счет1 13323Изобретение относится к вычислительной технике и может быть использовано при автоматизированном решении задач компоновки элементов радио 5электронной аппаратуры в блоки,Целью изобретения является расширение функциональных возможностейустройства за счет обеспечения возможности разбиения графа на минимально связанные подграфы.На чертеже представлена Функциональная схема устройства для разбиения графа на подграфы,В состав устройства входит матричная модель 1 графа, содержащая Тстрок и М столбцов триггеров2-1,1 2-М,Т и элементов И 31,1 З-М,Т группу сумматоров4-1, , 4-Т, группу элементов ИЛИ 205-1 5-М, группу коммутаторов6-1 6-М, группу триггеров 2-1, 7-М, группу элементовНЕ 8-1 8-М, дешифратор 9, первый счетчик 10, элемент 11 задержки, 25элемент И 12, генератор 13 тактовыхимпульсов, вход 14 задания количества вершин в подграфе устройства, шифратор 15, второй счетчик 16, выход17 признака выделения дерева с заданным количеством вершин устройства, два коммутатора 18 и 19, шестьключей 2025, элементы ИЛИ 26,схема 27 сравнения, блок 28 памяти,два регистра 29 и 30, вход 31-1 3531-М задания начальной вершины первого подграфа устройства.Устройство работает следующим образом.Первоначально в нулевое состояниеприводятся все триггеры 7-1, , 7-Мгруппы, счетчики 10 и 16, регистры29 и 30, блок 28 памяти ключи 20 -23 закрыты, ключ 24 открыт, коммутаторы 6-1, , 6-М устанавливаются в 45состояние, при котором их выходыподключены к выходам соответствующихтриггеров 7-1 /-М, Информация отопологии моделируемого графа заносится путем установки соответствую Ощих триггеров 2-1 2-М в единичное состояние. Соответствующий триггер 2-кр (к,р=М) формирователядуги определяется пересечением К-йстроки (К-номер начальной вершинымодулируемой ветви графа) с р-мстолбцом (р-номер конечной вершинымоделируемой ветки графа). Заданиеначальной вершины первого подграфа 29 2осуществляется подачей на соответствующий вход 31 единичного сигнала,который, проходя через элементИЛИ 5, поступает на вход шифратора15, который Формирует на своих выходах двоичный код номера заданной начальной вершины, Сигнал задания начальной вершины после прохождениячерез соответствующие элементы ИЛИ 5и 26 открывает ключ 20,обеспечиваятем самым запись двоичного кода номера начальной вершины в блок 28 памяти,осуществляет запуск генератора 13и увеличивает содержимое счетчика 10на единицу. Одновременно сигнал свыхода соответствующего элементаИЛИ 5 устанавливает в единичное состояние триггера 7-К, обеспечивая темсамым возможность для прохождения свыхода триггеров 2-К 1 2-К,Мсигнала матричной модели графа, соответствующей начальной вершине насумматоре 4-К, а также запрещает выбор строки, соответствующей начальнойвершине в качестве кандидата на включение в первый подграф, Последнеедостигается за счет инвертирования вэлементе НЕ 8-К сигнала с выходатриггера 7-К, соответствующего включенной в первый подграф начальнойвершине. Следствием этих действийявляется Формирование на выходе К-госумматора 4-К (К-не равно номеру начальной вершины) двоичных кодов количества связей К-й вершины с включенной в первый подграф начальнойвершиной. Тактовые импульсы от генератора 13 через открытый ключ 24обеспечивают последовательное подключение к выходам схемы 27 сравнения и ключа 25 выходов сумматоров4-К, а также синхронное подключениек одному из входов элемента 12-М спомощью коммутатора 18 выходов элементов НЕ Я-К, Кроме того, тактовыеимпульсы поступают на счетчик 16,на выходе которого образуется двоичный код номера импульса в интервалеотдо М (код номера аннулируемойвершины), схема 27 производит равнение содержимого регистра 30 с содержимым подключенного через коммутатор 19 сумматора 4-К . Если первоеоказывается меньше второго и вершина, соответствующая подключенномусумматору 4-К еще не включена в формируемый подграф (на выходе соответствующего элемента НЕ 8-К отсутст5 10 15 20 25 30 35 40 45 50 55 з 133 вует единичный сигнал), то сигнал с выхода блока 27 после прохождения через элемент И 12 разрешает запись в регистр 30 содержимого подключенного к блоку 27 сумматора 4-К. Одновременно сигнал с выхода блока 27 разрешает запись в регистр 29 через ключ 23 двоичного кода номера соответствующей вершины графа. После завершения цикла просмотра всех М вершин в регистре 30 присутствует максимальное значение количества связей одной из вершин, не включав- шихся ранее в первый подграф, а в регистре 29 зафиксирован двоичный код номера этой вершины. факт окончания этого цикла фиксируется счетчиком 16, который формирует на выходе признака переполнения сигнал, разрешающий передачу из регистра 29 в дешифратор 9 кода номера вершины, максимально связанной с вершинами, включенными в формируемый подграф. Этот же сигнал после задержки в элементе 11 на время, необходимое для передачи информации из регистра 29 в дешифратор 9 осуществляет обнуление содержимого регистров 29 и 30, а также счетчика 16. Поступивший в дешифратор 9 код вершины преобразуется в сигнал на одном из его выходов, который после прохождения через элемент ИЛИ 5 устанавливает один из триггеров 7-1 7-М в единичное состояние, обеспечивая тем самым возможность для прохождения сигналов с выхода триггеров 2-1.2 М одного из столбцов матричной модели, соответствующего включенной в подграф вершине, на сумматор 4, а также запрещает выбор строки, соответствующей включенной вершине, в качестве кандидата на включение в подграф. Ло аналогии со случаем начальной вершины производится запись в блок 28 кода номера очередной включаемой в первый подграф вершины, а содержимое счетчика 1 О увеличивается на единицу. Цикл работы устройства для выбора и включения в подграф последующих вершин аналогичен. Аналогично осуществляется задание начальной вершины подачей сигнала на один из входов 31 устройства. Если в первый подграф включено заданное количество вершин, то на выходе счетчика 10 формируется сигнал, поступающий на выход 17 устрой 23294 ства и запрещающий прохождение тактовых импульсов от генератора 13,и разрешает прохождение через ключ2 сигналов с выходов триггеров7- 7-М на управляющие входысоответствующих коммутаторов 6-16-М. В этом случае коммутаторы6-1.. 6-М, на управляющие входыкоторых поступили единичные сигналы(коммутаторы, соответствующие включенным в первый подграф вершинам),устанавливаются в состояние, прикотором к их выходам подключены выходы соответствующих элементов8-1.8-М НЕ, исключая тем самым .из рассмотрения при последующем анализе связи вершин 6, уже включенныхв сформированный подграф. Для формирования второго подграфа в счетчике1 О устанавливается граничное значение, равное суммарному объему первого и второго подграфов. В этом случае сигнал на выходе счетчика Оаннулируется открывая путь для прохождения по схеме устройства тактовых импульсов от генератора 13 иустройство функционирует аналогичнослучаю формирования первого подграфа. Результатом работы устройстваявляется накопление в блоке 28 кедовномеров вершин в порядке их включения в подграфы. Формула изобретения Устройство для разбиения графа на подграфы, содержащее генератор тактовых импульсов, первый счетчик, элемент задержки, элемент И, группу триггеров, группу элементов ИЛИ, дешифратор и матричную модель графа, каждый узел которой включает элемент И и триггер, выход которого подключен к первому входу элемента И того же узла матричной модели графа, выходы всех элементов ИЛИ группы подключены к информационным входам соответствующих триггеров группы, о тл и ч а ю щ е е с я тем, что, с целью расширения Функциональных воэможностей устройства за счет возможности разбиения графа на минимально связанные подграфы, в него введены два коммутатора, группа коммутаторов,группа элементов НЕ, группа сумматоров, два регистра, элемент ИЛИ, второй счетчик, схема сравнения, шифратор, блок памяти и шесть ключей, 1332329причем первые входы элементов ИЛИ группы являются входами задания начальной вершины первого подграфа устройства, выход К-го элемента ИЛИ группы (К М, где М - количест 5 во вершин в моделируемом графе) подключен к К-му информационному входу шифратора, информационный выход которого подключен к информацинному входу 1 О первого ключа, выход которого подключен к информацинному выходу блока памяти, информационный вход первого счетчика является входом задания количества вершин в подграфе устройст ва, выход признака переполнения первого счетчика подключен к управляющим входам второго и третьего ключей и является выходом признака выделения дерева с заданным количеством вершин устройства, выход элемента ИЛИ подключен к управляющему входу первого ключа к счетному входу первого счетчика и к входу пуска генератора тактовых импульсов, выход которого 25 подключен к информационному входу третьего ключа, выход которого подключен к управляющим входам первого и второго коммутаторов и к счетному входу второго счетчика, информацион- ЗО ный выход которого подключен к информационному входу четвертого ключа, выход которого подключен к информационному входу первого регистра, выход которого подключен к информационному входу пятого ключа, выход которого подключен к информационному вхооду дешифратора, К-й выход которого подключен к второму входу К-го элемента ИЛИ группы, выход К-го тригге б ра группы подключен к К-му информационному входу второго ключа, к первому информационному входу К-го коммутатора группы и к входу К-го элемента НЕ группы, выход которого под-.ключен к второму информационному входу К-го коммутатора группы, к К-муинформационному входу первого коммутатора и к вторым входам элементов1 всех узлов К-й строки матричноймодели графа, выход К-го коммутатора группы подключен к третьим входамэлементов И всех узлов К-го столбцаматричной модели графа, выход элемента И К-го узла Р-й строки матричноймодели графа(Р=1 М) подключен квходу К-го слагаемого Р-го сумматора группы, выход которого подключенк Р-му информационному входу второгокоммутатора, выход которого подключен к первому информационному входусхемы сравнения и к управляющему вхо-ду шестого ключа, выход которогоподключен к информационному входувторого регистра, выход которогоподключен к второму информационномувходу схемы сравнения, выход признаканеотрицательного результата которойподключен к первому входу элемента И,выход первого коммутатора подключенк второму входу элемента И, выходкоторого подключен к информационномувходу шестого ключа и к управляющемувходу четвертого ключа, выход признака переполнения второго счетчикаподключен к управляющему входу пятого ключа и к входу элемента задержки, выход которого подключен к входам установки в 0 второго счетчикаи первого и второго регистров.1332329 Составитель А.МишиТехред Л.Сердюков Реда енко ректор И.Иуск Заказ 3834/45 одписно В 3035 г.ужгород ул,Проектная, 4 оизводственно-полиграфическое предприятие Тираж б 72 ИИПИ Государственног делам изобретени осква, Ж, Рауш