Устройство для исследования подмножеств графа

,. 3) И 9 48электротехннчес ,И,Ульянова ЛеВ.С.Князьковолокайнен етельство СССР Р 15/20, 1977. ельство СССР Р 15/20, 1984. ко 4,зле- аФ СЛЕДОВАНИЯ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ НИЕ ИЗОБР А ВТОРСКОМУ СВИ(21) 4090582/24-24 (22) 18.07.86 (46) 30.12.87. Бюл (71) Ленинградский ких институт им. В нина/(57) Изобретение относится к вычислительной технике и предназначенодля решения задачи на графах, в частности для вьделения максимальныхвнутренне устойчивых подмножеств,не являющихся собственными подмножествами никакого другого внутреннеустойчивого подмножества. Цель изобретения - повышение быстродействияустройства при вьделении максимальных внутренне устойчивых подмножеств.Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу3 из Р х Р моделей ребер, где Рличество вершин в графе, триггерыэлементы И 5, первуюгруппу из Р1363236 ментов ИЛИ 6, группу из Р регистров7 сдвига, регистр 8 сдвига, элементИЛИ 9, четвертый элемент 10 задержки,третий элемент 11 задержки, второйэлемент 2 задержки, первый элемент13 задержки, вторую группу из Р элементов ИЛИ 14, группу из Р элементовИ 15 и вход 16 пуска устройства. Используя генератор 2 импульсов и регистр 8 сдвига, устройство обеспечивает последовательный анализ всехстрок матрицы 3 моделей ребер напредмет исключения из формируемогомаксимального внутренне устойчивогоподмножества всех вершин, инцидентных рассматриваемой. Для этого сигИзобретение относится к вычисли- тельной технике и может быть использовано для решения на графах задач выделения максимальных внутренне устойчивых подмножеств, не являющихся собственным подмножеством никакого другого внутренне устойчивого подмножества.Целью изобретения является повыше ние быстродействия устройства при выделении максимальных внутренне устойчивых подмножеств.На чертеже представлена функциональная схема предлагаемого устройства.Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 из Р х Р моделей ребер, где Р - количество вершин в графе, триггеры 4, элементы И 5, первую группу из Р элементов ИЛИ 6; .группу из Р регистров 7 сдвига, регистр 8 сдвига, элемент ИЛИ 9, четвертый элемент 10 задержки, третий элемент 11 задержки, второй элемент 12 задержки, первый элемент 13 задержки, вторую группу из Р элементов ИЛИ 14, группу из Р элементов И 15 и вход 16 пуска устройства.Устройство работает следующим образом.В матрице 3 моделей ребер содержится информация о топологии графа, при этом соответствующие триггеры налы с выходов открытых элементовИ 15, проходя через открытые элементы И 5, элементы ИЛИ 6 на информационные входы регистров 7, устанавливают первые входы указанных регистров 7 в единичное состояние, что соответствует исключению вершины изформируемого подмножества. По оконча.нии анализа всех строк матрицы 3 характеристика максимального внутреннеустойчивого подмножества, содержащего первую вершину графа, записана в(Р + 1)-х разрядах регистров 7, а характеристика подмножества, содержащего Р-ю вершину графа, - во вторыхразрядах регистров 7. 1 ил. установлены в единичное состояние согласно матрице смежности графа.С поступлением сигнала на вход 16 устройства первые разряды всех регистров 7 устанавливаются в нулевое состояние, первый разряд регистра 8 - в единичное состояние.Сигнал с первого разряда информационного регистра 8 проходит элеменИЛИ 14и ИЛИ 6 , 6 и обеспечивает зане 1сение первой строки матрицы 3 моделей ребер в первые разряды регистров 7.Этот же сигнал через элемент ИЛИ9, элемент 10 задержки и элементыИЛИ 14 , 14, проходит через теэлементы И 15, на первые входы которых поступают единичные сигналы с ин Формационных выходов регистров 7.Далее указанный сигнал проходит через открытые элементы И 15 и производит анализ на связность только техвершин графа, которые неинцидентны с.25заданной в данном цикле, т.е. в рассматриваемом случае - с первой,Анализ строк матрицы 3 моделейребер, соответствующих открытым элементам И 15, на предмет исключенияиз формируемого максимального внутренне устойчивого подмножества всехвершин, инцидентных рассматриваемой,заключается в том, что сигналы с выходов открытых элементов И 15, прохо 3 13632дя через открытые элементы И 5, элементы ИЛИ 6 на информационные входырегистров 7, устанавливают первыеразряды указанных регистров 7 в еди 5ничное состояние, что соответствуетисключению вершины из формируемогомаксимального внутренне устойчивогоподмножества.Сигнал с выхода элемента 11 задержки производит сдвиг информациив регистрах 7, а сигнал с выхода элемента 13 задержки, величина временизадержки которого больше суммы времени задержек от элементов 1 О и 11, запускает генератор 2 импульсов.Работа устройства состоит из Рциклов (Ртактов генератора импульсов). В каждом цикле выделяется одномаксимальное внутренне устойчивое 20подмножество, обязательно содержащеевершину, номер которой совпадает сномером разряда информационного выхода регистра 8, установленного в единичное состояние. Искомое множество 25формируется в первых разрядах регистров 7 за четыре шага.На первом шаге импульс с генератора 2 производит сдвиг информациив регистре 8. Появившийся на втором ЗОвыходе регистра 8 сигнал проходитпементы ИЛИ 14И 15 И 5.у5, ИЛИ 6, 6, и йа втором шагер 1пройзводит запись второй строки матрицы 3 моделей ребер в первые разряды регистров 7. На третьем шаге сигнал с выхода элемента 10 задержкипоступает в матрицу 3 моделей ребер,через открытые элементыИ 15 15на входы элементов И 5 соответствую Ощих строк матрицы.Если хотя бы один триггер 4 в рассматриваемой строке находится в единичном состоянии, единичный сигналс его выхода проходит через открытый 45элемент И 5, элемент ИЛИ 6 и устанавливает первый разряд соответствую щего регистра 7 в состояние "1"На четвертом шаге сигнал с выходаэлемента 11 задержки производит сдвиг 5 Оинформации в регистре 7.Второй импульс с выхода генератора 2 производит сдвиг информации врегистре 8Единичный потенциал появляется на третьем выходе регистра, иработа устройства повторяется.,(Р)-й импульс генератора 2 запускает формирование Р-го максимальноговнутренне устойчивого подмножества 36 4графа и через элемент 12 задержки останавливает генератор 2.1На этом работа устройства заканчивается. В одноименных Р-х старших разрядах регистров 7 записана,информация о выделенных максимальных внутренне устойчивых подмножествах вершин, содержащих все вершины графа. Причем характеристика максимального внутренне устойчиваого подмножества, содержащего первую вершину графа, записана в (Р + 1)-х разрядах регистров 7; характеристика подмножества, содержащего вторую вершину, в Р-х разрядах; характеристика подмножества, содержащего Р-ю вершину, во вторых разрядах регистров 7. Вершина графа входит в максимальное внутренне устойчивое подмножество вершин графа, если в регистре 7, соответст- . вующем данной вершине, в разряде, соответствующем данному максимальному внутренне устойчивому подмножеству вершин, записан "О", и не входит, если записана "1".Формула изобретенияУстройство для исследования подмножеств графа, содержащее матрицу из Р х Р моделей ребер, где Р - количество вершин в графе, генератор импульсов, две группы из Р элементов ИЛИ, группу из Р элементов И, группу из Р регистров сдвига, регистр сдвига и три элемента задержки, причем каждая модель ребра матрицы содержит элемент И и триггер, выход которого подключен к первому входу элемента И той же модели ребра матрицы, выход элемента И М-й модели ребра (М = 1Р) К-й строки (К=1Р) матрицы подключен к К-му входу М-го элемента ИЛИ первой группы, выход которого подключен к информационному входу М-го регистра сдвига группы, выход которого. подключен к первому входу М-го элемента И группы, выход. которого подключен к вторым входам всех элементов И моделей ребер М-й строки матрицы, вход пуска устройства подключен к установочному входу регистра сдвига, к установочным входам всех регистров сдвига группы и к входу элемента задержки, выход которого подключен к входу пуска гене. - ратора импульсов, выход которого под" ключен к входу признака сдвига реСоставитель А.Мишин.Техред М.Дидык . Корректор О.Кравцова Редактор А Маковская Тираж 671 Подписное ВНИИПИ Государственного комитета СССР) по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Заказ 6364/42 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 5 136 гистра сдвига, М-й разряд информационного выхода которого подключен к первому входу М-го элемента ИЛИ второй группы, выход которого подключен к второму входу М-го элемента И, Р-й разряд информационного выхода регистра сдвига подключен к входу второго элемента задержки, выход которого 1подключен к входу останова генератора импульсов, выход третьего элемента задержки подключен к входам признака сдвига всех регистров сдвига группы, о т л и ч а ю щ е е с я тем,3236 6что, с целью повьшения быстродейст.вия устройства при выделении максимальных внутренне устойчивых подмножеств, в него введены элемент ИЛИ и 5четвертый элемент задержки, причемМ-й разряд информационного выходарегистра сдвига подключен к М-мувходу элемента ИЛИ, выход которогоподключен к входу четвертого элемента задержки, выход которого подключен к входу третьего элемента задержки и к вторым входам всех элементовИЛИ второй группы.