Устройство для анализа параметров графа Советский патент 1989 года по МПК G06F15/173 

г.з

5

10

1465891

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

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

На фиг.1 представлена функодональ- ная схема предложенного устройства; на фиг.2 - временная диаграмма работы его блока синхрониза ;™; на фиг.3- пример топологии графа.

Устройство содержит блок 1 синхронизации, матрицу из триггеров 2 где В - количество вершин в графеs Р - количество ребер в графе, матрицу из ВгР элементов И 3, гртопу из В элементов И 4, счетчик 5, первый элемент И Ь, группу из Р блоков 7 сложения по модулю два, первьй регистр 8, сумматор 9, второй регистр 10, третий регистр 11, блок 12. сравнения, блок 13 элементов И, второй элш.1ент И 14 и элемент 15 задержки.

Кроме того, на фиг.1 введены циф- ровые обозначения 16 - вход началь- |Нои установки устройства., 17,18 -входы задания М-го ребра графа (,„. Р), -инщэдентного К-й вершине графГ 30 (,..„,в); 19 - вход пуска устройства; 20 - вход задания состава вер- шк начального сечения графа устройства, 21 - выход cocTaiea ребер минимального сечения графа устройства; 22 - выход кол гчества ребер в шнимальном сечении графа устройства; iJ-2o первьй второй, третий и чет- .вертый .вькоды блока 1 сннхронизации.

дают топологию графа в соответствии с матрицей смежности графа). На фиг номера вершин указаны цифрами без скобок, номера ребер - цифрами в ско ках. На вход 19 пуска устройства по дают импульсный сигнал единичного уровня„ При этом блок синхронизации начинает вырабатывать последовательность импульсов в соответствии с вр менной диаграммой, представленной на фиг.2. Блок t формирует импульс на выходе 23„ При этом содержимое счетчика 3 становится равным единице. Че рез время Т1, достаточное для оконча ния операции сумтрования в счетчике 5, блок 1 вырабатывает сигнал единич ного уровня на вькоде 24. При этом на выходе первого, второго и третьего блоков 7 сложения по модулю два появляются-сигналы единичного уровня на выходе сумматора 9 - код числа 3 (количество ребер в сечении мевду подграфом, состоящим из одной первой вершины, и подграфом, состоящим из остальных вершин графа). Через время 1, достаточное для вьтолнения операции сложения по модулю два и операции суммирования, блок 1 вьрабаты- вает импульсный сигнал единичного уровня на выходе 25. Пда этом код числа 3 (с выхода сумматора 9) запи- сьшается в регистр 11. Блок 12 сравнения вьграбатьгоает признак больше или равно (так как код в регистре 10 больше кода в регистре 11). Через время ТЗ, достаточное для окончания операции записи в регистр 11 и операции сравнения, блок 1 вырабатывает импульс на выходе 26.. При этом код

20

25

T-v.i. liJriOCHJ tl «

Устройство работает слеяу.юпщм об-40 читя Т . - (азом.числа 3 записьгоается в регистр 10, в

Пусть требуется найти етнкмальное Р ™стр 11 записывается код 11100

Ьечекие в графе (фиг.З),Состав ребер первого сечения). Далее

Перед Ha4ajioM работы на вход 20Работа устройства протекает аналогичiri::s:L«° rLs™ i°; f-™« --° -™r,.

- J . j Jict ИЛОД:

fb начальной установки - импульс еди- ite4Horo уровня. При этом устанавлива- ится в нулевое -состояние все триггеры 2 и счетчик 5, в регистр 10 заносится . максимальньгй код. На входы 17 первого, второго и третьего триггеров 2 первой строки матрицы, первого, второго, четвертого и пятого триггеров 2 второй строки матрицы и

не изменятся (так как количество ребер второго сечешя между подграфом, состоящим из одной второй вершины, и подграфом, состоящим из ос- 50 тальных вершин, равно четырем и больше количества ребер в предьщущем сечении) , по третьему импульсу в регистрах 8, 10 будут зафиксированы коды 3 и 00111 соответственно, почетт ретьего, четвертого и пятого тригге-, веотому - я « nn i--. рюв 2 третьей строки матрицы подают « ,11, по штому со ймпул сы единичного уровня При ГЮО « изменится - 3

указанные триггеры переходят I ед.Г хоД 2 блокП пГ Н1ичное состояние (такш. образом, за-тавлен П Г будет ос-.

iaauM, затавлен. Пун этом в регистрах 8, 10

5

10

0

дают топологию графа в соответствии с матрицей смежности графа). На фиг 3 номера вершин указаны цифрами без скобок, номера ребер - цифрами в скобках. На вход 19 пуска устройства подают импульсный сигнал единичного уровня„ При этом блок синхронизации начинает вырабатывать последовательность импульсов в соответствии с временной диаграммой, представленной на фиг.2. Блок t формирует импульс на выходе 23„ При этом содержимое счетчика 3 становится равным единице. Через время Т1, достаточное для окончания операции сумтрования в счетчике 5, блок 1 вырабатывает сигнал единичного уровня на вькоде 24. При этом на выходе первого, второго и третьего блоков 7 сложения по модулю два появляются-сигналы единичного уровня на выходе сумматора 9 - код числа 3 (количество ребер в сечении мевду подграфом, состоящим из одной первой вершины, и подграфом, состоящим из остальных вершин графа). Через время 1, достаточное для вьтолнения операции сложения по модулю два и операции суммирования, блок 1 вьрабаты- вает импульсный сигнал единичного уровня на выходе 25. Пда этом код числа 3 (с выхода сумматора 9) запи- сьшается в регистр 11. Блок 12 сравнения вьграбатьгоает признак больше или равно (так как код в регистре 10 больше кода в регистре 11). Через время ТЗ, достаточное для окончания операции записи в регистр 11 и операции сравнения, блок 1 вырабатывает импульс на выходе 26.. При этом код

20

5

0 читя Т . - числа 3 записьгоается в регистр 10, в

,.

не изменятся (так как количество ребер второго сечешя между подграфом, состоящим из одной второй вершины, и подграфом, состоящим из ос- тальных вершин, равно четырем и больше количества ребер в предьщущем сечении) , по третьему импульсу в регистрах 8, 10 будут зафиксированы коды 3 и 00111 соответственно, почетвеотому - я « nn i--. « ,11, по штому со f ГЮО « изменится - 3

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

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

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

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

Устройство для анализа параметров графа, содержащее матрицу из триггеров, где В --количество вершин в графе, Р - количество ребер в графе, матрицу из Вх элементов И, группу из В элементов И, первьш регистр и блок -синхронизации, вход пуска которого является входом пуска устройства, причем вход начальной устано&ки устройства подключен к входам установки в О всех триггеров матрицы, вход задания М-го ребра графа (, ...,Р), инцидентного К-й вершине графа (,...,В) устройства, подключен .к входу установки в 1 М-го триггера К-й строки матрицы, выход которого подключен к первому входу М-го элемента И К-й строки матрицы, о т л и

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

40

го кода второго регистра и к входу признака записи счетчика, К-й разряд информационного выхода которого подключен к К-му входу первого элемента jH, и к первому входу К-го элемента И группы, выход которого подключен к BTopbiM входам всех элементов И К-й строки матрицы, выход М-го элемента И К-й строки матрицы подключен к входу М-го лока сложения по модулю два, выход которого подключен к входу М-го слагаемого сумматора и к М-му разряду информационного входа первого регистра, выход которого является выходом состава ребер минимального сечения графа устройства, выход сумматора подключен к информационному входу третьего регистра вы ход которого подключен к информацион ному входу блока элементов И и к пер вому информационному входу блока сра нения , выход признака сравнения Бол ше или Равно которого подключен к первому ВХОД5 второго элe ieнтa И и к управляющему входу блока элементов И, выход которого подключен к информационному входу второго регистра, выход которого является выходом коли чества ребер в минимальном сечении графа устройства и подключен к второ ьгу информационному входу блока сравнения, выход первого элемента И подключен к входу останова блока сннхро- низации5 первый выход которого подключен к cyм iиpз oщeмy входу счетчика, кнформационньй вход которого является входом задания состава вергиин начального графа5 второй выход блока син хронизации подключен к вторым входам всех элементов И , третий выход блока синхронизации подключен к входу признака записи третьего регистра; четвертьй выход блока синхронизации подключен к второму входу второго

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

0

5

0

5

0

0

го кода второго регистра и к входу признака записи счетчика, К-й разряд информационного выхода которого подключен к К-му входу первого элемента jH, и к первому входу К-го элемента И группы, выход которого подключен к BTopbiM входам всех элементов И К-й строки матрицы, выход М-го элемента И К-й строки матрицы подключен к входу М-го лока сложения по модулю два, выход которого подключен к входу М-го слагаемого сумматора и к М-му разряду информационного входа первого регистра, выход которого является выходом состава ребер минимального сечения графа устройства, выход сумматора подключен к информационному входу третьего регистра выход которого подключен к информационному входу блока элементов И и к первому информационному входу блока сравнения , выход признака сравнения Больше или Равно которого подключен к первому ВХОД5 второго элe ieнтa И и к управляющему входу блока элементов И, выход которого подключен к информационному входу второго регистра, выход которого является выходом количества ребер в минимальном сечении графа устройства и подключен к второ- ьгу информационному входу блока сравнения, выход первого элемента И подключен к входу останова блока сннхро- низации5 первый выход которого подключен к cyм iиpз oщeмy входу счетчика, кнформационньй вход которого является входом задания состава вергиин начального графа5 второй выход блока синхронизации подключен к вторым входам всех элементов И , третий выход блока синхронизации подключен к входу признака записи третьего регистра; четвертьй выход блока синхронизации подключен к второму входу второго

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

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

И

Saoo3

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

Составитель А.Мишин Техред А.Кравчук

Заказ 948/50

Тираж 667

БНЙИПИ Государственного комитета по кзобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35s, Раушская наб., д. 4/5

Корректор МоДемчик

Подписное