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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

1 А1 (So4С06F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСКОМ У СВИДЕТЕЛЬСТВУ

3) ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4191996/24-24 (22) 04.02 ° 87 (46) 15.03.89. Бюп. Ф t0 (72) В.Л.Львов, А.Я.Ярмьпп и ДЛ.Гиллер (53) 681 333 (088.8) (56) Авторское свидетельство СССР

Ф 888134, кл. G 06 F 15/36, 1981.

Авторское свидетельство СССР

Н 1408441, кл. G 06 Р 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть исполь зовано для исследования сечений rpaфа. Целью изобретения является расширение функциональных возможностей устройства за счет определения минимального сечения в графе. Перед началом работы задают топологию графа в виде матрицы инцидентности. После пуска устройство обеспечивает опрос строк матрицы для всех возможных комбинаций вершин графа, при этом элементы одноименных столбцов матрицы складываются по модулю два, что позволяет получить элементы матрицы сечений графа. Если новое сечение меньше предыдущего, то информация о нем (состав и количество ребер) запоминаются в соответствующих регистрах.

3 ил.

1465891

Изобретение относится к вычислительной технике и может быть исполь(зовано для исследования сечений в неориентированных графах.

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

На фиг.1 представлена функциональная схема предложенного устройства, I0 . на фиг.,2 — временная диа.грамма работы его блока синхрокизации» на фиг.3— пример т on ол огии r p аф а, Устройство содержит блок 1 синхронизации, матрицу из В Р триггеров 2, 15 где  — количество вершин в графе;, P — - количество ребер в графе, матрицу из В, Р элементов И 3„ группу из В элементов И 4, счетчик 5, первый элемент

И 6, группу из Р блоков 7 сложения по модулю два, первьпЪ регистр 8, сумматор 9, второй регистр 10, третий регистр 11, блок 12 сравнения, блок 13 элементов И, второй элемент И 14 и элемент I5 задержки.

Кроме того, на фиг.1 введены цифровые обозначения . 16 — вход началь( ной установки устройства„17,18 — входы задания М-ro ребра графа (М=1,..., P), инец".дентного к-й вершине графа (К=1» ° в „,В); 19 - вход пуска усгроиства; 20 — вход задания состава вер<н начального сечения графа устройтва, 21 — выход состава ребер миимального сечения графа -тстройста, 22 — выход количества ребер в инимальном сечении графа устройства; r

3-2о — первыи„второй, третий и четертый выходы блока 1 синхронизации.

Устройство работает следующим об- 40 разом.

Пусть требуется найти ьинкмальное ечекие в графе (фиг.3) .

Перед началом работы:на вход 20 устройства подают нулевой код, на вход45 (6 начальной установки — импульс единичного уровня. При этом усганавливаются в нулевое состояние все триггеры 2 и счетчик 5, в р егистр 10 заНосится максимальный код„ Яа входы

17 первого, второго и третьего триггеров 2 первой строки матрицы» первого, второго, четвертого и пятого триггеров 2 второй строки матриць| и третьего, четвертого и пятого тригге- 55 ров 2 третьей строки матрицы подают (Импульсы единичного ÎÂHí в При этом указанные триггеры переходят в единичное состояние (таким образом, задают топологию графа в соответствии с матрицей смежности графа). На фиг.3 номера вершин указаны цифрами без скобок, номера ребер — цифрами в скобках. На вход 19 пуска устройства подают импульсный сигнал единичного уровня. При этом блок синхронизации начинает вырабатывать последовательность импульсов в соответствии с временной диаграммой, представленной на фиг.2. Блок 1 формирует импульс на выходе 23. При этом содержимое счетчика 5 становится равным единице. Через время Т1, достаточное для окончания операции суммирования в счетчике

5, блок 1 вырабатывает сигнал единичного уровня на выходе 24. При этом на выходе первого, второго и третьего блоков 7 сложения по модулю два появляются сигналы единичного уровня

» на выходе сумматора 9 — код числа 3 . (количество ребер в сечении между подграфом, состоящим из одной первой вершины, и подграфом, состоящим из остальных вершин графа) . Через время

Т2, достаточное для выполнения опе" рации сложения по модулю два и операции суммирования, блок 1 вырабатывает импульсный сигнал единичного уровня на вьгходе 25. При этом код числа 3 (с выхода сумматора 9) записывается в регистр I1. Блок 12 сравнения вырабатывает признак больше или равно (так как код в регистре 10 ° больше кода в регистре 1I). Через время ТЗ, достаточное для окончания операции записи в регистр 11 и операции сравнения, блок 1 вырабатывает импульс на выходе 26.. При этом код числа 3 записывается в регистр 10, в ,регистр 11 записывается код 11100 (состав ребер первого сечения), Далее работа устройства протекает аналогично: по второму импульсу на выходе 26 блока 1 коды в регистрах 8, 10 не изменятся (так как количество ребер второго сечения между подграфом, состоящим из одной второй верппены» и подграфом, состоящим из остальных вершин, равно четырем и больше количества ребер в предыдущем сечении), по третьему импульсу в регистрах 8, 10 будут зафиксированы коды 3 и 001 I1 соответственно, почетвертому — 3 и 00111, по пятому содержимое регистров не изменится - 3 и 11100. По аедьмому:пепульсу на выходе 23 блока 1 последний будет ос-. тавлен. При этом в регистрах 8, 10

3 3А будет храниться соответственно количество и состав последнего минималь" ного сечения в графе.

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

23 блока 1 и запускают устройство.

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

1 узлов в один общий узел.

Формула изобретения

Устройство для анализа параметров графа, содержащее матрицу из В» P триггеров, где  — -количество вершин в графе, Р— количество ребер в графе, матрицу из В х Р элемент он И, группу из В элементов И, первый регистр и блок синхронизации, вход пуска которого является входом пуска устройства, причем вход начальной установки устройства подключен к входам установки в "0" всех триггеров матрицы, вход задания М-ro ребра графа (M=1, ...,P), инцидентного К-й вершине графа (К=1,...,В) устройства, подключен .к входу установки в "1" М-ro триггера К-й строки матрицы, выход которого подключен к первому входу М-ro элемента И К-й строки матрицы, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального сечения в графе, в него введены счетчик, два элемента И, второй и третий регистры, сумматор, блок элементов И, блок сравнения, элемент задержки и группа из Р блоков сложения но модулю два, причем вход начальной установки устройства подключен к входу установки максимально65891 4 го кода второго регистра и к входу признака записи счетчика, К-й разряд информационного выхода которого подключен к К-му входу первого элемента

5 ,И, и к первому входу К-го элемента

И группы, выход которого подключен к вторым входам всех элементов И К-й строки матрицы, выход М-го элемента

И К-й строки матрицы подключен к

К-му входу М-го .блока сложения по модулю два, выход которого подключен к входу M-го слагаемого сумматора и к М-му разряду информационного входа первого регистра, выход которого является выходом состава ребер минимального сечения графа устройства, выход сумматора подключен к информационному входу третьего регистра, вы" ход которого подключен к информационному входу блока элементов И и к гервому информационному входу блока сравнения, выход признака сравнения "Больше" или "Равно" которого подключен r;

25 первому входу второго элемента И и к управляющему входу блока элементов

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

45 элемента И, выход которогс подключен к входу элемента задержки, выход которого подключен к входам гризнаков записи первого и второго регистров, 1465891

Сост а вит ель А. Мишин

Техред A. Кравчук

Корректор И.Демчик

Редактор N.Келемеш

Заказ 948/50 Тираж б67 Подписное

ВНКЮИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

° и

Производственно-издательский комбинат "Патент", r, Ужгород, ул. Гагарина„101