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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик (11> 807313

1 (61) Дополнительное к авт.саид-ву 643880 (5 )м. к„.з (22) Заявлено 220379 (21) 2738974/18-24 с присоединением заявки М

G 06 F 15/20

Государственный комитет.СССР по делам изобретений и открытий (23) Приоритет

Опубликована 2302.81. Бюллетень 89 7 (5З) УДК 681.ззз (088. 8) Дата опубликования описания 2 30281 (72) Автор изобретения

Н.B. Федотов

file ГЬ»-,.„ М..У ЕХ»1Р ц

Институт электродинамики AH Украинской ССР ."ОтЕоg (! (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

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

По основному авт. св, 9 643880 известно устройство, содержащее модели нершин, соединенные между собой согласно топологии исследуемого графа, регистр, вход и первый выход которого подключены к первому выходу 1О и входу блока управления, второй, третий и четвертый выходы которого соединены соответственно с первым, вторым и третьим нходами моделей вершин, информационные ныходы ре- 15 гистра соединены с первыми входами элементов И группы, второй вход каждого из которых подключен к первому ныходу соответствующей модели вершины, выходы элементов И 20 группы подключены соответственно к четвертым входам моделей вершин, кажцая из которых содержит первый триггер, первый элемент ИЛИ, первый элемент И, второй триггер, первый 25 и второй формирователи импульсов, второй, третий, четвертый, пятый и шестой элемент И, второй элемент

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

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

И, выход которого соединен с первым

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

И подключен к второму входу первого элемента ИЛИ (lj .

Указанное устройство позволяет выделить все максимальные сильно связанные подграфы в графе.

Однако устройство не позволяет найти число внешне-внутреннего разделения вершины х, определяемого Р выражением

S (х„- ) = (d(х,,х)+d (х,х.; ) ), где х — множество вершин исследуемого графа1

Й (х, х ) и d (x., х.; ) — соответственно веса расстояний между х,. и х вершинами в пря- мом и обратном направлениях.

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

Эта цель достигается тем, что в устройство для исследования графов по авт. св. Р 643880 в каждую модель вершины графа дополнительно введены восьмой и девятый элементы

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

На чертеже схематически представлено устройство.

Устройство содержит модели 1„- 1> вершин исследуемого графа, блок 2 управления, (сдвиговой) регистр 3, элементы 4 — 4> .

В состав каждой модели вершины входят триггеры 5 и 6, элементы И 714, элементы ИЛИ 15-17, элемент

НЕ 18, счетчики 19 и 20 импульсов, формирователи 21 и 22 одиночного импульса, блок 23 индикации, полюса (входы и выходы) 24-31 модели вершины графа, полюса (вход и выходы)

32-37 блока управления.

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

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

Первоначально посредством полю15 сов 24 и. 25 модели вершин коммутируются между собой в соответствии с конфигурацией исследуемого графа.

Сдвиговой регистр 3 и счетчики

19 и 20 импульсов обнуляются. Тригге20 ры 5 и 6 всех моделей вершин устанавливаются в нулевое состояние (установочные шины не показаны), Первоначально в графе выбирается произвольная вершина х. и для нее опРеделяются все числа внешнего разделения. Выбор произвольной вершины х„ производит блок 2 управления.

Для этого блок 2 управления выдает импульс через полюс 36 на вход сдвигового регистра 3. Продемонстрируем это на примере выбора модели

1 вершины. На выходе первого разряда сдвигового регистра 3 появляется разрешение, которое поступает на один из входов элемента И модели 14 . Разрешение проходит через элемент И модели 1(, так как на втором ее входе есть разрешение с полюса 26 модели 1(вершины, и поступает на полюс 29. модели верши40 ны, чем обеспечивается ее выбор.

Одновременно с выбором вершины х блок 2 управления выдает разре1 шение на полюса 28 и импульсы генератора импульсов ГИ (не показан) на

4 полюса 31 всех моделей 1 - 1> вершины. Импульсы ГИ, пройдя элемент

И 14 и элемент ИЛИ 17, поступают на вход счетчика 20 импульсов и накапливаются в нем. Прохождение импуль® сов ГИ через элемент И 14 обеспечивается разрешениями, которые снимаются с нулевого выхода триггера 5 и с полюса 28 модели вершины. Число импульсов, накопленных счетчиком 20, определяет величину числа внешнего разделения между выбранной вершиной х„. и вершиной, которая может быть достигнута из вершины х„. При этом в счетчик выбранной вершины заносится 0 импульсов, так как выбор модели вершины х сопровождается установкой ее трйггера 5 в единичное состояние, что достигается разрешением, поступающим на полюс 29 модели вершины, через элементы И 9 д и ИЛИ 15 на единичный вход этого

807313 триггера. В результате с входа элемента И 14 снимается разрешение.

В остальные модели вершин в счет чики 20 заносятся соответственно: в модели вершин, связанных непосредственно с выбранной, по одному импульсу; в счетчики 20 моделей вершин, связанных с выбранной через одну вершину, по два импульса и т.д.

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

Этот импульс, распространяясь по сети с полюса 24 через элементы И 7 и ИЛИ 15, устанавливает триггер 5н единичное состояние и повторяется формирователями 21 одиночного импульса в каждой модели вершины, которые доступны из выбранной, 1 — 1 вершин. При этом импульс ГИ с полюса 31 через элементы И 13 и

ИЛИ 17 поступает на вход счетчика

20 импульсов и накапливается в нем.

Число импульсов ГИ, ноступинших на вход счетчика 20, соответствует ве25 личине числа внутреннего разделения, а общее число импульсов, накопленных счетчиком 20, определяет величину числа, внешне-внутреннего разделения вершины х„ и вершин, которые достигаются из вершины х„ и из которых достигается эта вершина.

Прохождение импульсов ГИ через элемент И 13 обеспечивается разрешениями, которые снимаются с нулевого выхода триггера 6 и полюса 30, При этом в счетчики 20 моделей вершин, по аналогии, как и при определении числа внешнего разде35

40 ления, заносится определенное число импульсов. В выбранную модель вершины х„ заносится 0 импульсов, так как момент определения числа ннутреннего разделения сопровождается установкой триггера б в выбранной модели в единичное состояние.

Это происходит разрешением с полюса

30 через элементы И 10 и ИЛИ 16,. которое поступает на единичный вход триггвра б.

В остальные модели вершин число импульсов, занесенных в счетчик 20, определяется распрастранением импульса, сформированного формирователем 22 одиночного импульса выбранной модели, Этот импульс, распространяясь по сети с полюса 25 через элемент И 8 и ИЛИ 16, устанавливает триггеры 6 в единичное состояние и повторяется формирователями 22 одиночного импульса н каждой модели, Определение числа внутреннего раз- щ деления вершины х. происходит бло1 ком 2 управления в результате снятия разрешения с полюсов 28 и выдачи разрешения на полюса 30 всех моделей из которых может быть достигнута выбранная вершина.

Модели вершин, для которых определено число внешне-внутреннего разделения, о чем свидетельствует единичное состояние триггеров 5 и 6, из дальнейшего рассмотрения исключаются. Это происходит в результате того, что разрешения с единичных выходов триггеров 5 и б поступают на входы элемента И 11 и с его выхода на вход элемента НЕ 18. Инверсия этого раерешения поступает через полюс 26 на один из входов элементов

И моделей 1„ — 1„,что обеспечивает и:: блокировку.

В дальнейшем устройство переходит к определению числа внешне-внутреннего разделения вершин, для которых оно не было определено. Процесс осуществляется аналогично описанному выше. Предварительно необходимо установить триггеры 5 и б в нулевое состояние и обнулить счетчики 20 импульсов моделей вершин,. у которых оба триггера 5 и б одновременно не находятся в единичном состоянии.

Множество моделей 1„ — 1д вершин моделируемого графа группируются по подмножествам, что позволяет выделить относительно каких первоначально выбранных вершин х для них определено число внешне-вйутреннего разделения. Для этого производится пометка вершин. Она производится .импульсом блока 2 управления через полюс 35 на полюс 27 всех моделей вершин. Этот импульс, пройдя элемент

И 12 в моделях вершин, у которых триггеры 5 и 6 одновременно находятся в единичном состоянии, поступает на вход счетчика 19 и запоминается н нем.

Процесс определения числа внешне.внутреннего разделения для всех вершин прекращается тогда, когда на полюсе 32 блока 2 управления с выхода сдвигового регистра 3 не появляется сигнал.

Номер подмножества, к которому относится вершина, и неличина числа внешне-внутреннего разделения индицируется блоком 23 индикации, входы которого подключены к выходам счетчиков 19 и 20.

Введение в известное устройстно дополнительно новых двух элементов

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

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

Устройство для исследования графов по авт.св. 9 643880, о т л и8

807313

Составитель И. Дубинина

Редактор Л.Кеви Техред С. Веца Корректор Г. Назарова

Заказ 294/75 Тираж .756 Подписное

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

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

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

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

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

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

Р 643880 KJI G 06 F 15/20, 1975 (прототип).. !