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

 

0 ll H C A H H K п>643880

ИЗОБРЕТЕНИЯ

Соез Советска

Сэииалистииесиия

Республик и АВТОРСКОМУ СВИ ВТИЛЬСТВУ (В!) Дополнительное к авт. свиа-ву(22) Заявлено 20.11.75 (21) 2194669/18-24 с присоединением заявки. № (23) ПриоритетОпубликовано25 01.79 бюллетень 34 3

Дата опубликования описания 28.01.79 (5l} М, Кл. (3 06 Г 15/20

Гввудврвтвввввй вивтвт

СССР вв деми взФрввнив я вткритвв (53} УДК 681 ЭЭЗ (088.8) .(одоиов, K В. Федотов, Н. В. федотов B В 3 )(-ино и В. М Шишмарев

Г. ектродинамики AH Украинской p „:-;;

""" ° с; „ (72} Авторы изобретения (71) Заявитель (54) VCTPOACTBO QJ3$f HCCREGOBAHHH?PA@09

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

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

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

Наиболее близким по технической сущ- И

ВОсти K предлагаемому является rpoé ство,, содержашее1 модели вершин, сое» .дииенные меЖду собой согласно тололо гии исследуемого графа, . регистр, вход и первый выход которого подключены первому выходу и входу блока управце. иии, второй, третий и четвертый выходы которого соединены соответственно с.

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

Однако, известное устройство не позволяет произвести разложение графа на максимальные сильно-связные ноа» графы.

Целью изобретения является рас пм рение функциональных возможностей за счет введения учета сильно-связнык йодграфов. @аннан цель достигается тем, что в каждую модель вершщы графа донолннтельно введены второй триггер, пер вый н второй формирователЬ импульсов, второй, третий, четвертый, пятый и mecтой элементы Я, второй элемейт ИЛИ, 643880 элемент НЕ, счетчик импульсов, блок индикации, причем четвертый вход модели вершины графа соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к первому и второму входам модели вершины гра фа, выходы первого и второго элементов И соединены соответственно с первыми входа« ми первого и второго элементов ИЛИ,выходы которых подключены к единичным входам первого и второго триггеров, -единичный вьцсод первого триггера подгопочен к первому входу четвертого элемента И и ко входу первого формирователя импульсов, выход которого соединен со вторым выходом модели вершины графа и с первым входом третьего элемента И, второй вход которого подключен к нулевому выходу первого триггера, третий вход третьего элемента И соединен со вторым входом вт"ооого элемента И и с первым входом модели вершины графа, выход третьего элемента И соединен со вторым входом вт орого элемента ИЛИ.

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

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

-Прецлагаемое устройство представлечо на чертеже, Оно содержит модели вершин исследуемого графа 1г, - ° ° 1 ггпу блок управления 2, (сдвиговой) регистр

3, группа элементов И 4 ...4п.

В состав каждой модели вершины

11- 1ггвходят: триггеры 5, 6, элементы

К 7-12„элементы ИЛИ 13, 14, элемент HE 15, счетчик импульсов 16, блок индикации 17, формирователи одиночных импульсов 18, 19, папоса модели вершщ

20-31.

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

Посредством полюсов 20 и 21, модели вершин коммутпруются между собой и совтветствни со структурой исследуемого графа. Сдвиговой регистр 3 н счетчики 16 обнуляются. Триггеры 5 и 6 всех моделей вершин устанавливаются . в нулевое состояние. г0 Вначале в графе определяется множество вершин Г Х ., достижимых из

X -ой вершины, то .есть определяется множество вершин, для которых сушест вует путь из Х -ой вершины. для этого г1 блок управления 2 через полюс 22 выдает разрешение на полюса 23 всех мо. делей вершин 1 - 1 . Выбор X: -ой вершины осуществляется. олоком управления 2 путем подачи импульса через по

20 люс. 24 на вход сдвигового регистра

3, Пусть на выходе первого разряда сдвигового регистра 3 поавляетса раз-. решение, которое поступит на один из входов элемента И 44. Это разрешение

2 пройдет элемент И 4.г, так как на втором его входе есть разрешение с полюса

29 модели варягины 1<, и поступит на полюс 26 этой же модели. Сигны с полюса 26, пройдя элементй Я 9 и

ИЛИ 13, поступит на,единичный вход триггера 5 и установит его в единичное состояние. Этим будет осуществлен вы бор модели вершины 1 .

Таким образом выбираетса любаа вершине графа и далее для определения множества Г Х;. необходимо определить

Ф множество вершин, которые могут быть достигнуты из вершины )(. Построение г множества осуществляется распрост ре4О нением по г рафу импульса, снимаемого через формирователь одиночного merges са 19 с единичного выхода триггере 5 выбранной модели вершины. формироъатель одиночного импульса

4> 19 выдает импульс на полюс 21. Далее этот импульс, распространяясь по графу, устанавливает триггера 5 моделей в еди ничное состояние. Это происходит поступлением импульса с полюса 20 через

5О элементы И 7 и ИЛИ 13 на единичныйвход этих трьгггеров. Таким образом, этот импульс, проходя с полюса 20 иа полюс 21, будет распространяться по исследуемой сети н формировать множество Г г XÄ.. Единичное состояние трщтеров

5 моделей вершин будет свидетельство58Th об Нх принадлежности эт0му мно

h yr X „ " .

5 6438

После этого блок управления 2 начинает определять множество Г X „, множество вершин нэ которых может быть достигнута Х„ -ая вершина. Для этого необходимо произвести переориентиро- 3 ванне графа, которое осуществляется путем снятия разрешения с полюсов 23 всех моделей вершин и подачей разрешения блоком управления 2 через полюс

27 на все полюса 28. При этом входа- т6 ми у всех моделей вершин являются иолюса 21, а выходами полюса 20.

Разрешение с полюса 28,. пройдя элементы И 10 и ИХ И 14, поступит на единичный вход триггера 6 выбранной М модели вершины, так как только у нее на втором входе элемента H 10 есть разрешение. Сигнал на единичном входе триггера 6 установит его в единичное состояние., что снимет разрешение со входа элемента И 7.

Построение множества Г Х ссушествляется импульсом цо сигналу сян мае мому формирователем одиночного импульса 18 с единичного выхода тригге .ра 6 выбранной модели вершины. формирователь одиночного импульса 18 вы .дает импульс на полюс 20. Далее этот импульс, распространяясь по графу, ус таиавливает триггера 6 моделей в единичное состояние. Это обеспечивается поступлением импульсе 21 через iaeменты И 8 и ИДЯ 14 на едииичйьтй вход тРиггеров 6. Таким образом, проходи с йолюса 21 иа полюс 20, импульс будет распрос раняться по исследуемой се ти и формировать множество Г Х .

Единичное состояние триггеров 6 ме» джей вершин будет освидетельствовать о принадлежности вернтин множеству

r.x.

Досле ностроения множеств Г Х„и

Г Х в моделях вертнин 1,- 1 тригИ геры 5 н 6, одновременно находяшиеся. в единичном состоянии, свидетельствуют о том, что соответствующие им мршиньт исследуемого графа. удовлетворятот условию С(Х;) Г Х;ДГ ф;и прннадлежж максимальному сильно-связному тждграфу, одной из .вершин которого является выбранная картинна.

Метка сформированного максималь» ного сильно-связного подграфв осушествляется подачей импульса блоком утт равнения 2 через полюс 31 на полюс

28.scex моделей вершин. Этот импульс пройдя через элемент И 12 в. моделях вершин, s которых триггера 5 и 6 юж80 6 повременно находятся в единичном состоянии, поступит на вход счетчика 16 и в нем запомнится.

Как только будет сформирован и помечен максимальный связный подграф, блок управления 2 снимет разрешение с полюсов 28 всех моделей вершин и перейдет к формированию новых максимальных сильно-связных подграфов. Исключение вершин, нринадлежащих уже сформированным подграфам, иэ дальнейшего рассмотрения осуществляется путем инвертирования элементом HE 15 сигнала, поступающего с выхода элемента И 11. Этот инвертированный, сигнал поступает на полюс 29, снимак разрешение с входов соответствуюших схем И 4-4 . В дальнейшем блок управлении 2 устанавливает триггеры 5 и 6 в нулевое со стояние у тех моделей вершин, которые не принадлежат сформированному подграфу. После чего блок управления производит аналогичным образом выбор новой модели вершины и пропесс формирования нового максимального сильносвяэного подграфа повторяется. Процесс разложения графа на максимальные сильно-связные подграфы заканчивается только в том случае, если на выходе сдвигового регистра 3 появится сигнал, который поступает на полюс 30 блока управления 2. Это свидетельствует о том, что.в графе нет ни одйой вершины, которая не входила бы в какой-нибудь максимальный сильно-связный подграф.

Число импульсов, занесенное s счетчики 16 моделей вершин, будет отражать номер подграфа, к которому относятся этн модели вершии. Данный номер индииируется блоком индикации 17, sma которого связан с выходом счетчика 16.

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

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

7 6438 динены соответственно с первым, вторым и третьим входамн моделей вершин, информационные выходы регистра соединены с первыми входами элементов И „группы, второй вход кщкдого из которых подключен.к первому всюду соответствующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вэргнин, каждая из которых содержит первый триггер, первый 1ф :элемеиг ИдИ, первый элемент Ц„,о ти и ч а в ш е е с я тем, что, с целью расширения функциональных возможностей за счет введения учета сильйо-ciwa- ных подграфоь в каждую модель Верши f $ ны графа дополнительно введены второй триггер, первый к второй формирователи импульсов, второй, третий, четвертый, пятый и шестой элементы И, второй элемемг ИЛИ, элемент НЕ, счетчйк" нм- ю пульсов блок индикации, причем чу вертый вход модели вершины графа соединен с первыми входамн первого а второго элементов И, вторые входы ко торык подключены к первому и второму 23 входам модели вершины графа, выходы первого и второго элементов И соедпнеиы соответственно с первыми входамн первого и второго элементов ИДИ, вы ходМ которых пошиакиены к едйничным 30 входам первого и второго тр«ггеров, единичный выход первого триггера подключен к первому входу четвертого элемюнта И и ко входу первого форм«рова вела «мнульсов, выход которого соеди и иеи со вторым выходом модели вершины графа и с первым входом третьего эле80 8 мента И, второй вход которого подключен к нулевому выходу первого триггера третий вход третьего элемента И соединен со вторым входом второго элемента

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

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

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

1 . Авторское свидетельство СССР и 308484, 3Li. О 06 а 7/1229

28.09 71 °

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

14 408312, кл. ® 06 5 18/20, 29-03.74.

6 43880

Составитель Колчин

Редактор Д. Мепурншвили Техред 10, Йиймет Корректор, A. Грнд нко . Заказ 8223/45 .. Тираж 779 Подписное

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

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

Филнал ППП Патент, г. Ужгород, ул. Проектная, 4