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

 

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

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

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

РЕСПУБЛИК

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

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ . КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4129216/24-24 (22) 18.07.86 (46) 15..07.88. Бюл. У 26 (71) Ленинградский электротехнический институт им. В.И.Ульянова (Ленина) (72) Т.В.Волченская, В.С.Князьков, В.С.Дудкин и Д.П.Пуолокайнен (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 643880, кл. G 06 F 15/20, 1975.

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

В 1134946, кл. G 06 F 15/20, 1985.

„„SU„„1410051 А1 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах. Целью изобретения является снижение аппаратурных затрат. Устрой-. ство позволяет проводить разбиение графа на максимальные сильно связанные подграфы, а также находить входные и выходные вершины подграфа. 3 ил °

1410051

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

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

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

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

Модель вершины блока моделирова- 30 ия содержит первый информационный

ыход 26, первый. информационный вход

7, второй информационный вход 28, торой информационный выход 29, вход

0 разрешения записи, элементы И 31—

3, триггер 34.

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

40 ершин подграфа.

В описании работы устройства сим««олами Y, ..., Yg обозначены сигналы

« а соответствующих выходах блока управления.

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

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

« рафа.

Режим ввода задается подачей пос « оянного потенциала на вход 21. По с игналу У> с входа 17 устройства заг исывается "1" в первый разряд регис тра 16. По сигналу У« информация с входа 18 устройства заносится через з лементы ИЛИ 5 группы в триггеры 11 г|руппы. Информация в блок 1 моделирования заносится построчно. Сигнал Yg

I открывает элемент И 7 и проходит на

1 первую группу входов блока 1. Сигнал

У открывает элементы И 8 группы и информация с выходов триггеров 11 группы поступает на вторую группу входов блока 1 моделирования. Сигнал

У разрешает запись в модели вершин.

Таким образом, по сигналам Y, Y,,Y

41 записывается информация первой строки блока 1 моделирования.

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

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

Г+(ХК) П Г (ХК). Подготовка устройства к работе заключается в подаче постоянного потенциала на вход 22 устройства.

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

Сигнал У открывает элемент 7 и

k поступает на К-й вход первой группы блока 1 моделирования. Если триггер

34 модели вершины К-й строки находится в единичном состоянии, то сигнал через вход 28, элемент И 31 и выход

26 проходит на соответствующий выход второй группы блока 1 и через элемент ИЛИ 4 группы устанавливает соответствующий триггер 12 группы в единичное состояние. Так формируется прямое транзитивное замыкание первого порядка Г (К„). Кроме того, сигФ1 нал с К-ro разряда регистра 16 поступает через элементы ИЛИ 4„и 5> и устанавливает в единичное состояние соответственно триггеры 12 и 11, тем самым формируя Г (Хк)УХ„.

1410051

Сигнал У< открывает элемент 8 и поступает на К-й вход второй группы блока 1 моделирования. Если триггер

34 ячейки К-ro столбца находится в

5 единичном состоянии, то сигнал через вход 27 модели вершины графа, элемент

И 33 и выход 29 проходит на входы установки в единицу триггеров 11 группы. Таким образом, на данном шаге образуется обратное транзитивное замыкание первого порядка вершины Х, т.е. Г "(Х„) UX„ (триггер 11, установлен в единичное состояние на предыдущем шаге). 15

По сигналу Y откроются элементы

И 7 группы, на первые входы которых через элементы ИЛИ 3 группы поступают единичные сигналы с выходов соответствующих триггеров 12 К-го разряда 2р регистра 16 сдвига. Аналогично установятся в единичное состояние тригге. ры 12, соответствующие найденному прямому транзитивному замыканию второго порядка Г (Х ) U Г+"(Х ) U Х>.

По сигналу У откроются элементы

И 8 группы, соответствующие триггерам 11, установленным в единичное состояние. Таким образом будет найдено Г- (X„) U Г (Хк) U Х„. . 30

Рассмотренные шаги циклически повторяются до.тех пор, пока их число не превысит длины максимального пути графа» Далее сигнал У открывает те элементы И 9 группы, на вторые и третьи входы которых поступают единичные

35 сигналы с выходов соответствующих триггеров 11 и 12. Тем самым реализуется пересечение найденного прямого и обратного транзитивных замыканий С(Х ) = Г+ (Х,„)Д Г (Х,). Номера переключающихся в единичное состояние триггеров 13 группы соответствуют номерам вершин графа, объединенных в первый максимальный сильно связанный 45 подграф С(Х <) .

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

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

Пока не закончатся сдвиги, сигнал с выхода элемента ИЛИ 14 блокирует работу блока управления.

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

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

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

r" (С С (Х )) и r- taiC(X„)3 и в пометке вершин, удовлетворяющих условиям Г+1 С С(Хк)1 П С(Х„) и Г (С1С(Х„)) П С(Х„).

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

Запуском работы устройства служит: сигнал с входа 19, который сбрасывает в ноль все регистры, триггеры, счетчики.

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

18 — о подграфе С(Хк) (для выходных вершин.о подграфе GKC(X )). Сигнал

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

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

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

051

5 1410 управления, блок моделирования графа ( содержит и моделей-вершин, где и— число вершин исследуемого графа, о т, л и ч а ю щ е е с я тем что с цеl Ф

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

И, вторые входы первой группы элементов И соединены с выходами соответствующих триггеров третьей группы и входамн элемента И, выход которого является выходом признака окончания работы устройства и соединен с входом . сброса блока управления, вход пуска устройства соединен с входом сброса регистра сдвига, входами установки нлн в 20 в 0 триггеров третьей группы, входом пуска блока управления и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом первого элемента ИЛИ, а выход соединен 25 с входами установки в "0" триггеров первой и второй групп, вход управления сдвигом регистра сдвига соединен с входом блокировки .блока управления с выходом первого элемента ИЛИ, ервый вход которого соединен с выодами элементов И первой группы, торой выход блока управления соедиен с входами синхронизации триггеров торой группы, входы установки в "1" оторых соединены с выходами соответ35 твующих элементов ИЛИ третьей група выходы - с первыми входами элеентов И третьей и четвертой групп, . ретий выход блока управления соеди40 ен с первыми входами элементов И которой группы, выходы которых соедииены с входами первой группы блока моделирования графа, а вторые входы элементов И второй группы соединены с выходами соответствующих элементов

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

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

И четвертой группы соединены с входами установки в " 1" триггеров третьей группы.

1ч10051

1410051

Составитель И.Ершов

Техред A.Êðàâ÷óê Корректор M,Äeì÷Hê

Редактор О.Спесивых

Заказ 3482/46

Тираж 704 Под пис ное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4