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

Изобретение относится к вычислительной технике и может быть использовано для исследования сечений в неориентированных графах.Цель изобретения - расширениефункциональных возможностей устройства за счет определения минимальногосечения в графе,На фиг.1 представлена Функциональная схема предложенного устройства,10на фиг 2 - временная диаграмма работы его блока синхронизации, на Фиг,З -пример топологии графа,Устройство содержит блок 1 синхронизации, матрицу из ВР триггеров 2,15где В - количество вершин в графе;,Р - количество ребер в графе, матрицуиз В, Р элементов И Згруппу из В элементов И 4, счетчик 5, первый элементИ 6, группу из Р блоков 7 сложения помодулю два, первый регистр 8, сумматор 9, второй регистр 10, третий регистр 11, блок 12 сравнения, блок 13элементов И, второй элемент И 14 иэлемент 15 задержки.Кроме того, на Фиг.1 введены цифровые обозначения 16 - вход начальной установки устройства 17,18 в входы задания М-го ребра графа (М=1Р), инцидентного К-й вершине графа(К=1,. ,В); 19 - вхоц пуска устройства; 20 - вход задания состава верн начального сечения графа. устройтва, 21 - выход состава ребер ми"имального сечения графа устройст"а; 22 - выход количества ребер винимальном сечении графа устройства;7 Гн3-2 о - первыивторой, третий и четертый выходы блока 1 синхронизации.Устройство работает следующим образом,Пусть требуется найти ьинкмальноеечекие в графе (фиг.3) .Перед началом работы на вход 20устройства подают нулевой код, на вход 4516 начальной установки - импульс единичного уровня. При этом усганавливайтся в нулевое состояние все триггеры 2 и счетчик 5, в регистр 10 заносится максимальный код На входы17 первого, второго и третьего триггеров 2 первой строки матрицы, первого, второго, четвертого и пятоготриггеров 2 второй строки матриць итретьего, четвертого и пятого триггеров 2 третьей строки матрицы подаютИмпульсы единичного уровня в При этомуказанные триггеры переходят в единичное состояние (таким образом, задают топологию графа в соответствии с матрицей смежности графа). На Фиг.З номера вершин указаны цифрами без скобок, номера ребер - цифрами в скобках. На вход 19 пуска устройства подают импульсный сигнал единичного уровня, При этом блок синхронизации начинает вырабатывать последовательность импульсов в соответствии с временной диаграммой, представленной на Фиг.2, Блок 1 формирует импульс на выходе 23, При этом содержимое счетчика 5 становится равным единице. Через время Т 1, достаточное для окончания операции суммирования в счетчике 5, блок 1:вырабатывает сигнал единичного уровня на выходе 24. При этом на выходе первого, второго и третьего блоков / сложения по модулю два появляются сигналы единичного уровня9 на выходе сумматора 9 - код числа 3 . (количество ребер в сечении между подграфом, состоящим из одной первой вершины, и подграфом, состоящим из остальных вершин графа). Через время Т 2, достаточное для выполнения опе" рации сложения по модулю два и операции суммирования, блок 1 вырабатывает импульсный сигнал единичного уровня на выходе 25. При этом код числа 3 (с выхода сумматора 9) записывается в регистр 11. Блок 12 сравнения вырабатывает признак больше или равно (так как код в регистре 10больше кода в регистре 11). Через время ТЗ, достаточное для окончания операции записи в регистр 11 и операции сравнения, блок 1 вырабатывает импульс на выходе 26 При этом код числа 3 записывается в регистр 10, в ,регистр 11 записывается код 11100 (состав ребер первого сечения), Далее работа устройства протекает аналогично: по второму импульсу на выходе 26 блока 1 коды в регистрах 8, 10 не изменятся (так как количество ребер второго сечения между подграФом, состоящим из одной второй вершины, и подграфом, состоящим из остальных вершин, равно четырем и больше количества ребер в предыдущем сечении), по третьему импульсу в регистрах 8, 10 будут зафиксированы коды 3 и 00111 соответственно, почетвертому - 3 и 00111, по пятому содержимое регистров не изменится - 3 и 11100, По седьмому импульсу на выходе 23 блока 1 последний будет ос-, тавлен. При этом в регистрах 8, 103 14 будет храниться соответственно количество и состав последнего минималь" ного сечения в графе.В случае, если необходимо определить количество ребер в сечении между двумя подграфами определенного состава, на вход 20 устройства перед начальной установкой подают код состава вершин, отключают цепь выхода 23 блока 1 и запускают устройство. Таким образом, устройство выполняет операцию стягивания ребер, т.е, исключение всех ребер между заданными узлами грайа и превращения этих узлов в один общий узел. Формула изобретения Устройство для анализа параметров графа, содержащее матрицу из Вх Р триггеров, где В - количество вершин в графе, Р - количество ребер в графе, матрицу из В х Р зле ме нт он И, группу из В элементов И, первый регистр и блок синхронизации, вход пуска которого является входом пуска устройства, причем вход начальной установки устройства подключен к входам установки в "0" всех триггеров матрицы, вход задания М-го ребра графа (М=1, ,Р), инцидентного К-й вершине графа (К=1В) устройства, подключен ,к входу установки в "1" М-го триггера К-й строки матрицы, выход которого подключен к первому входу М-го элемента И К-й строки матрицы, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального сечения в графе, в него введены счетчик, два элемента И, второй и третий регистры, сумматор, блок элементов И, блок сравнения, элемент задержки и группа из Р блоков сложения но модулю два, причем вход начальной установки устройства подключен к входу установки максимально 65891 чго кода второго регистра и к входупризнака записи счетчика, К-й разрядинформационного выхода которого подключен к К-му входу первого элемента 5,И, и к первому входу К-го элементаИ группы, выход которого подключенк вторым входам всех элементов И К-йстроки матрицы, выход М-го элементаИ К-й строки матрицы подключен кК-му входу М-го .блока сложения помодулю два, выход которого подключенк входу М-го слагаемого сумматора ик М-му разряду информационного входапервого регистра, выход которого является выходом состава ребер минимального сечения графа устройства,выход сумматора подключен к информационному входу третьего регистра, вы"ход которого подключен к информационному входу блока элементов И и к первому информационному входу блока сравнения, выход признака сравнения "Больше" или "Равно" которого подключен к 25 первому входу второго элемента И ик управляющему входу блока элементовИ, выход которого подключен к информационному входу второго регистра,выход которого является выходом количества ребер в минимальном сеченииграфа устройства и подключен к второму информационному входу блока сравнения, выход первого элемента И подключен к входу останова блока синхронизации, первый выход которого под кпючен к суммирующему входу счетчика,информационный вход которого являетсявходом задания состава вершин начального сечения графа, второй выход блока синхронизации подключен к вторым входамвсех элементов И группы, третий выходблока синхронизации подключен к входу признака записи третьего регистра,четвертый выход блока синхронизацииподключен к второму входу второго 45 элемента И, выход которогс подключенк входу элемента задержки, выход которого подключен к входам гризнаковзаписи первого и второго регистров,1465891 орректор И.Демчик актор Х.Келеме сное каз 948 Гос изводственно-издательский комбинат "Патент", г. Ужгород, Ул. Гагарина 10 Составитель А.МишинТехред А. Кравчук Тираж 667 рственнаго комитета по изобретен 113035, Москва, Ж, Раушскаяи и открытиям при ГКНТ наб., д. 4/5