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

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

Целью изобретения является снижение аппаратурных затрат.

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

Устройство ДJJЯ исследования гра- Ьов (фиг.1) содержит блок 1 моделирования графа, блок 2 управления, группы 3-5 элементов ИЛИ, группы 6-9 элементов И, элемент И 10, группы 11-13 триггеров, элементы ИЛИ 14 и 15, регистр 16 сдвига, вход 17 задания начальной вершины графа, вход 18 задания топологии графа, вход 19 пуска устройства, выход 20 признака окончания работы устройства, входы 21, 22 задания режима работы, выход 23 при- знака окончания ввода информации.

Блок моделирования графа содержит вход 24 разрешения записи информации и состоит из идентичных моделей вер- иин 25.

Модель вершины блока моделирования содержит первьш информационный выход 26, первый, информационный вход 27, второй информационньй вход 28, зторой информационньй выход 29, вход 30 разрешения записи, элементы И 31- 33., триггер 34.

I Устройство реализует следующие функции: ввод данных о топологии исследуемого графа, вьщеление максимальных сильно связанных подграфов графа, определение входных (выходных 1:ершин подграфа.

; В описании работы устройства символами Y, ,.., Yg обозначены сигналы 4а соответствующих выходах блока уп- р авления.

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

1. Режим ввода данных о топологии .

Режим ввода задается подачей пос- 1 оянного потенциала на вход 21. По Сигналу Y с входа 17 устройства записывается 1 в первый разряд регистра 16. По сигналу Y информация с Е1хода 18 устройства заносится через з1лементы ИЛИ 5 группы в триггеры 11 фуппы. Информация в блок 1 моделирования заносится построчно. Сигнал Yj

0

5

0

5

0

5

0

5

0

5

открывает элемент И 7 и проходит на первую группу входов блока 1. Сигнал Y открывает элементы И 8 группы и информация с выходов триггеров 11 группы поступает на вторую i-pynny входов блока 1 моделирования. Сигнал YJ разрешает заг1ись в модели вершин. Таким образом, по сигналам Yj, Y, Y. записывается информация первой строки блока 1 моделирования.

Сигнал Y.7 произведет сдвиг 1 в регистре 16, подготавливая тем самым возможность записи во вторую строку блока 1 моделирования. Как только будут введены все п строк, появится сигнал на выходе 23 признака окончания ввода информации.

2. Режим вьвде ления максимальных сильно связанных подграф.

Устройство реализует алгоритм нахождения максимальных сильно связанных подграфов графа G(X), основанный на нахождении прямого (ХК) и обратного Г(ХК) транзитивных замыканий некоторой .вершины графа ХК с последующим образованием их пересечения Г-(ХК) П Г-(ХК). Подготовка устройства к работе заключается в подаче постоянного потенциала вход 22 устройства.

По сигналу с входа 19 происходит сброс устройства в исходное состояние и запуск блока управления. По сигналу Y , который управляет вводом информации с входа 17 устройства, в регистр 16 сдвига записывается 1 только в К-й разряд, который соответствует К-й вершине графа, являющейся начальной для формирования первого ;подграфа.

Сигнал Y открывает элемент 7 и поступает на К-й вход первой группы блока 1 моделирования. Если триггер 34 модели вершины К-й строки находится в единичном состоянии, то сигнал через вход 28, элемент И 31 и выход 26 проходит на соответствующий выход второй группы блока 1 и через элемент ИЛИ 4 группы устанавливает соответствующий триггер 12 группы в .единичное состояние. Так формируется прямое транзитивное замыкание первого порядка (Kj) . Кроме того, сигнал с К-го разряда регистра 16 поступает через элементы ИЛИ 4 и 5 и устанавливает в единичное состояние соответственно триггеры 12, и 11ц, тем самым формируя f (Хк)иХк.

Сигнал Y4 открывает элемент 8| и

поступает на К-й вход второй группы блока 1 моделирования. Если триггер 34 ячейки К-го столбца находится в единичном состоянии, то сигнал через вход 27 модели вершины графа, элемен И 33 и выход 29 проходит на входы установки в единицу триггеров 11 группы. Таким образом, на данном шаге образуется обратное транзитивное замыкание первого порядка вершины Х т.е. Г ЧХц) их (триггер 11ц установлен в единичное состояние на пре- дьщущем шаге).

По сигналу Yj откроются элементы И 7 группы, на первые входы которых через элементы ИЛИ 3 группы поступают единичные сигналы с выходов соответствукщих триггеров 12 К-го разряда 20 метке вершин.

15 вершин максима подграфов закл го-либо максим ного подграфа (Х)

регистра 16 сдвига. Аналогично установятся в единичное состояние тригге- ры 12, соответствующие найденному прямому транзитивному замыканию второго порядка ) и ) U Х,. 25

По сигналу У откроются элементы i И 8 группы, соответствукщие триггерам 11, установленным в единичное состояние. Тдким образом будет найдено r-4Xj и

г- (х)

и X

К

Рассмотренные шаги циклически повторяются до. тех пор, пока их число не превысит длины максимального пути графач Далее сигнал Y открывает те. элементы И 9 группы, на вторые и третьи входы которых поступают единичные сигналы с вьрсодов соответствующих триггеров 11 и 12. Тем самым реализуется пересечение найденного прямого и обратного транзитивных замыканий С(Х,) Г (Х)П Г СХр. Номера переключающихся в единичное состояние триггеров 13 группы соответствуют номерам вершин графа, объединенных в - первый максимальный сильно связанньй подграф С(Х,()„

Сигнал Y-, произведет сдвиг в регистре 16 сдвига,, например в Р-й разряд, и установит триггеры 11 и 12 в нулевое состояние.

Если Р-я вершина уже вошла в какой-либо подграф, то единичный сигнал с выхода триггера 13р поступает на вход элемента 6р, проходит и через элемент ИЛИ 14 поступает на вход

управления сдвигом регистра 16. Про-, исходит еще один сдвиг и снова проверка условия, входит ли рассматриваемая вершина подграф.

30

ВИЯМ (Х (X) П С(

Первые поме входными верши но связанных п выходными.

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

Сигналы Y формации с вхо ственно. С вхо ция о подграфе вершин о подгр 18 - о подграф д0 вершин.о подгр

(Y) открьш

35

Y.

45

50

55

и по входам пе блока 1 устана сматриваемым в руются в тригг сигналу YJ про меров входных триггерах 13.

Формула

Устройство фов, содержаще графа, блок уп га и первую гр вые входы кото дам соответств сдвига, вход р рого соединен

т ,

14100514

Пока не закончатся с выхода элемента ИЛИ

работу блока управления,

Проверка на окончание работы производится элементом И 10, который выдает сигнал 20 окончания работы, если все триггеры 13 группы установлены в единичное состояние, Сигнал окончаНИН работы подается на вход сброса блока управления.

3. Режим определения входных (выходных) вершин подграфов.

Определение входных и выходных

вершин максимальных сильно связанных подграфов заключается в выборе какого-либо максимального сильно связанного подграфа С(Хц), в определении (Х) и Г-ЧтС С(-Х,) и в по0 метке вершин.

5

удовлетворякнцих усло- .1

0

ВИЯМ (Х,) ПС(Х.) и Г (X) П С(Х).

Первые помеченные вершины являются входными вершинами максимальных сильно связанных подграфов, а вторые - выходными.

Подготовка устройства к работе заключается в подаче на входы 21, 22 устройства постоянного потенциала. Запуском работы устройствас служит, сигнал с входа 19, который сбрасывает в ноль все регистры, триггеры, счетчики.

Сигналы Y иYj разрешают ввод информации с входов 17 и 18 соответственно. С входа 17 вводится информация о подграфе (X,) (для выходных вершин о подграфе С(Хк), а с входа 18 - о подграфе С(Хк) (для выходных д0 вершин.о подграфе (X()). Сигнал

(Y) открьшает элементы 7 (8) И

5

Y.

45

0

5

и по входам первой (второй) группы блока 1 устанавливает смежные к рассматриваемым вершины, которые фиксируются в триггерах 12 (11) -группы. По сигналу YJ производится фиксация номеров входных (выходных) вершин на триггерах 13.

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

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

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

О триггеров третьей группы, входом пуска блока управления и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом первого элемента ИЛИ, а выход соединен с входами установки в О триггеров первой и второй групп, вход управления сдвигом регистра сдвига соединен с входом блокировки .блока управления л. с выходом первого элемента ИЛИ, первый вход которого соединен с вы- {одами элементов И первой группы,

торой выход блока управления соеди- ieH с входами синхронизации триггеров второй группы, входы установки в 1 соторьгк соединены с выходами соответ- :твующих элементов ИЛИ третьей груп- ш, а выходы - с первыми входами эле- leHTOB И третьей и четвертой групп,

ретий выход блока управления соеди- 1ен с первыми входами элементов И второй группы, выходы которых соеди

5

0

5

0

5

0

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

J7

18

. П

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

/7

фиг 2

фие.З