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

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

1

Изобретение относится к вычислительной технике к является усовершенствованием известного устройства

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

вход модели вершины графа соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к первому и второму входам модели вершины графа, выходы первого и второго элементов И соединены соответственно с первыми входами первого и второго элементов или, выходы которых подключены к

0 единичным входам первого и второго триггеров, единичный выход первого триггера подключеа к первому входу четвёртого элемента И и к входу первого формирователя импульсов,

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

0 третий вход третьего элемента И соединен с вторым входом второго элемента И и с первым входом модели вершины графа, выход третьего элемента И соединен с вторым входом

5 второго элемента ИЛИ, единичный выход второго триггера подключен к входу формирователя1 импульсов, к первому входу шестого элемента И и к второму входу четвертого элемента

D И, выход которого соединен с первым входом пятого элемента И и через элемент НЕ подключен к первому выходу модели вершины графа, третий вход которой соединен с вторым входом пятого элемента И, выход которого подключен к входу счетчика 1мпульсов, выход которого соединен с блоком индикации, .выход второго формирователя импульсов подключен к третьему выходу модели вершины графа и к втор.ому входу шестого элемента И, третий вход которого соеди нен с вторым входом первого элемента И и с вторым входом модели вершины графа, выход шестого элемента И подключен к второму входу первого элемента ИЛИ 1 . Указанное устройство позволяет выделить все максимальные сильно св занные подграфы в графе. Однако устройство не позволяет найти число внешне-внутреннего разделения вершины , определяемого выражением S (х ) d (х.,-,) +d (X.J-, х ) , где к - множество вершин исследуемо го графа; d(x,x.j-) и d(x;,) - соответственно веса расстояний меж ду х; и х: вершинами в прямом и обратном направлениях Цель изобретения - расширение функциональных возможностей устройства для исследования графов за сче возможности решения задач структурного анализа графов/ а именно обеспечение дополнительной возможности определения числа внешне-внутреннего разделения вершин. Эта цель достигается тем, что в устройство для исследования графов по авт. св. № 643880 в.каждую модель вершины графа дополнительно введены восьмой и девятый элементы И, третий элемент ИЛИ и второй счет чик импульсов, выход которого подключен к второму входу блока индикации,, выходы восьмого и девятого элементов И соединены соответственно с входами третьего элемента ИЛИ, выход которого подключен к входу .второго счетчика импульсов, входы восьмого элемента И соединены соответственно с нулевым выходом второг Tpijrrepa, с первым и пятым входами модели вершины графа, входы девятог элемента И подключены соответственн к нулевому выходу первого триггера,., к второму и пятому входам модели графа, пятый вход которой соединен с управляющим входом блока управлен На чертеже схематически представ лено устройство. Устройство содержит модели Ij,- l вершин исследуемого графа, блок 2 управления, (сдвиговой) регистр 3, элементы 4). В состав каждой модели вершины входят триггеры 5 и б, элементы И 7 14, элементы ИЛИ 15-17, элемент НЕ 18, счетчики 19 и 20 импульсов, формирователи 21 и 22 одиночного импульса, блок 23 индикации, полюса (входы и выходы) 24-31 модели вершины графа, полюса (вход и выходы) 32-37 блока управления. Нахождение числа внешне-внутреннего разделения определяется для произвольной вершины и включает в себя нахождение числа внешнего разделения, а затем - числа внутреннего разделения вершины х-. Устройство работает следующим образом.i, Первоначально посредством полюсов 24 и. 25 модели вершин коммутируются между собой в соответствии с конфигурацией исследуемого графа. Сдвиговой регистр 3 и счетчики 19 и 20 импульсов обнуляются. Триггеры 5 и б всех моделей вершин устанавливаются в нулевое состояние (установочные шины не показаны), Первоначально в графе выбирается произвольная вершина Х: и для нее определяются все числа внешнего разделения. Выбор произвольной вершины х производит блок 2iуправления. Для этого блок 2 управления выдает импульс через полюс 36 на вход сдвигового регистра 3. Продемонстрируем это на примере выбора модели Ijf вершины. На выходе первого разряда сдвигового регистра 3 появляется разрешение, которое поступает на один из входов элемента И модели 1. Разрешение проходит через элемент И модели 1 , так как на втором ее входе есть разрешение с полюса 26 модели 1 вершины, и поступает на полюс 29 модели вершины, чем обеспечивается ее выбор. Одновременно с выбором вершины х блок 2 управления выдает разрешение на полюса 28 и импульсы генератора импульсов ГИ (не показан) на полюса 31 всех моделей 1 вершины. Импульсы ГИ, пройдя элемент И 14 и элемент ИЛИ 17, поступают на вход счетчика 20 импульсов и накапливаются в нем. Прохождение импульсов ГИ через элемент И 14 обеспечивается разрешениями, которые снимаются с нулевого выхода триггера 5 и с полюса 28 модели вершины. Число импульсов, накопленных счетчиком 20, определяет величину числа внешнего разделения между выбранной вершиной х и вершиной, которая может быть достигнута из вершины . При этом в счетчик выбранной вершины заноимпульсов, так как выбор модели вершины х.,- сопровождается установкой ее триггера 5 в единичное состояние, что достигается разрешением, поступающим на полюс 29 модели вершины, через элементы И 9 и ИЛИ 15 на единичный вход этого триггера. В результате с входа эле мента И 14 снимается разрешение. В остальные модели вершин в счеТ чики 20 заносятся соответственно: в модели вершин, связанных непосредственно с выбранной, по одному импульсу; в счетчики 20 моделей вершин, связанных с выбранной через одну вершину, по два импульса и т.д Такое занесение импульсов в каждую из последующих моделей вершин обеспечивает импульс, сформированный в выбранной модели вершины х формирователем 21 одиночного импульса Этот импульс, распространяясь по сети с полюса 24 через элементы И 7 .и ИЛИ 15, устанавливает триггер 5 в единичное состояние и повторяется формирователями 21 одиночного импульса в каждой модели вершины, которые доступны из выбранной. Определение числа внутреннего ра деления вершины происходит блоком 2 управления в результате сняти разрешения с полюсов 28 и выдачи разрешения на полюса 30 всех моделе 1 вершин. При этом импульс ГИ с полюса 31 через элементы И 13 и ИЛИ 17 поступает на вход счетчика 20 импульсов и накапливается в нем Число импульсов ГИ, поступивших на вход счетчика 20, соответствует величине числа внутреннего разделения а общее число импульсов, накопленных счетчиком 20, определяет величину числа, внешне-внутреннего разделения вершины XJ и вершин которые достигаются из вершины х и . из которых достигается эта вершина Прохождение импульсов ГИ через элемент И 13 обеспечивается разрешениями, которые снимаются с нулевого выхода триггера 6 и полюса 30 При этом в счетчики 20 моделей вершин, по аналогии, как и при определении числа внешнего разделения, заносится определенное число импульсов, в выбранную модель веримпульсов. шины х; заносится так как момент определения числа внутреннего разделения сопровождается установкой триггера б в выбранной модели в единичное состояни Это происходит разрешением с полюс 30 через элементы И 10 и ИЛИ 16, которое поступает на единичный вход тригг а 6. В остальные модели вершин число импульсов, занесенных в счетчик 20 определяется распрастранением импульса, сформированного формирователем 22 одиночного импульса выбранной модели. Этот импульс, распространяясь по сети с полюса 25 через элемент И 8 и ИЛИ 16, устанавливает триггеры б в единичное состояние и повторяется формирователями 22 одиночного импульса в каждой модели, из которых может быть достигнута выбранная вершина. Модели вершин, для которых определено число внешне-внутреннего разделения, о чем свидетельствует единичное сЬстояние триггеров 5 и 6, из дальнейшего.рассмотрения исключаются. Это происходит в результате того, что разрешения с единичных выходов триггеров 5 и 6 поступают на входы элемента И 11 и с его выхода на вход элемента НЕ 18. Инверсия этого разрешения поступает через полюс 26 на один из входов элементов И моделей 1 - lj,4TO обеспечивает и:: блокировку. В дальнейшем устрой.ство переходит к определению числа внешне-внутреннего разделения вершин, для которых оно не было определено. Процесс осуществляется аналогично описанному выше. Предварительно необходимо установить триггеры 5 и 6 в нулевое состояние и обнулить счетчики 20 импульсов моделей вершин, у которых оба триггера 5 и 6 одновременно не находятся в единичном состоянии. Множество моделей вершин моделируемого графа группируются по подмножествам, что позволяет выделить относительно каких первоначально выбранных вершин х для них определено число внешне-внутреннего разделения. Для этого производится пометка вершин. Она производится импульсом блока 2 управления через полюс 35 на полюс 27 всех моделей вершин. Этот импульс, пройдя элемент И 12 в моделях вершин, у которых триггеры 5 и 6 одновременно находятся в единичном соётоянии, поступает на вход счетчика 19 и запоминается в нем. Процесс определения числа внешневнутреннего разделения для всех вершин прекращается тогда, когда на полюсе 32 блока 2 управления с выхода сдвигового регистра 3 не появляется сигнал. Номер пода1ножества, к которому относится вершина, и величина числа внешне-внутреннего разделения индицируется блоком 23 индикации, входы которого подключены к выходагл счетчиков 19 и 20, Введение в известное устройство ополнительно новых двух элементов И, элемента ИЛИ и счетчика импульсов, включенных в определенную схему, позволяет существенно расширить ее функциональные возможности: дает возможность дополнительно определять число внешне-внутреннего разделения. Формула изобретения Устройство для исследования графов по авт.св. 643880 о т л и 1аю1цееся тем, что, с це 1ью расширения функциональных возможя ностей решения задач структурного анализа графов, в каждую модель вершины графа дополнительно введены восьмой и девятый элементы И, тре.тий элемент ИЛИ и второй счетчик импульсов, выход которого подключен к второму входу блока индикации, выходы восьмого и девятого элементов И соединены соответственно с , входами третьего элемента ИЛИ, выхо которого подключен к входу второго счетчика.импульсов, входы восьмого элемента И соединены соответственно

J5 3 35

50(29«1 28

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

Источники информации, принятые во внимание при экспертизе

1. Авторское.Свидетельство СССР 643880, кл. G 06 F 15/20, 1975 (прототип).