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

- I .. -:,

Изобретение относится к области

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

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

Наиболее близким по технической cyi ности к предлагаемому является устройство,, содержащее у модели вершин, сое« дивенные меясду собой согласно топологии исследуемого , : регистр, вход и выход которогч) подключены

пер&ому выходу н входу блсжа управпе watt агорой, трётвА и четвертый выходы котиршЧ) соединены соответствешю с.

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

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

Целью изобретения вшшется paiconiрение фушаю( возможностей за счет введёиш учета сильяо-сввзных подграфов. Данная ведь достигается тем, что в кажпую модель верШ1;кы графа дополнителшо введены второй триггер первый и второй формирсАателЬ импульсов, Ьторой, Третий, четвертый, пятый и шестой элементы И, второй алеЫвкг ИЛИ,

Элемент НЕ, счетчик импульсов, блок индикации, причем четвертый вход модели вершины графа соединен с первыми входами первого и второго элементов и, вторые входы которых подключены к пер- Бому и второму входам модели вершины графа, вьцсоды первого и второго элементов И соединенъ соответственно с первыми входа« ми первого и второго элементов ИЛИ, выходы которых подключены к единичным входам первого и второго триггеров, единичный выход первого триггера подключен к первому входу четвертого элемента И и ко входу первого формирователя импульсов, выход которого соединен со вторым выходом модели вершины графа в с первым входом третьего элемента И, второй вход которого подключен К нулевому выходу первого т риггбра, третий вход треть€(ГО элемента И соединен со вторым входом элемента И и с первым входом модели вершины графа, выход третьего элемента И соединен со вторым входом второго элемейта ИЛИ,

ЕднничйЬ1Й выход второго триггера подйлиочен ко Входу второго формироватеия импульсов, к niepBOMy вхЬду .шестог го эпемеита И и ко вторёму входу четвертого элемента И выход которого соэдннеи с первым входом пятого элемента И и через элемент НЕ подключен к первому Выходу модел)я вершины графа, третий вход которой соединен со вторым Входом элемента и, выход которого подключен ко входу счетчика импульсов, соединен с блоком йндккашш, выход второго форшроватёля импульсов подключен к третьему выходу модели вершины графа и ко второму входу шестого элемента И, третий вход которого соединен со вторым входом первого элемента И и со вторым входом модели вершины графа, аыход шесгогр элемента И подключен ко вторО1и у входу первого Элемента ИЛИ.

Предлагаемое устройство представлено на чертеже. Оно содержит модели вершин исследуемого гра 1, . . . Ij, блок управления 2, (сдвиговой) регистр 3, группа элементов И 4...4j, .

В состав каждой модели вершины Ijjвходят: триггеры 5, 6, элементы И 7-12, апемеаты ИЛИ 13, 14, элемент НЕ 15, счет-чик импульсов 16, бло 8НДИКШЯН 17, формвровш-епи одиночных импульсов IS, 19, полрюса модели вершщ 20-31.

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

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

Вначале в графе определяется множество вершин Г X , достижимых из X 4 О вершины, то есть определяется множество вершин, для которых существует путь из X :|-ой вершины. Для этого блок управления 2 через полюс 22 выдает разрешение на полюса 23 всех моделей вершин i . Bbi6op Х,; -ой вершины осуществляется, ёпоком управления 2 путем подач импульса черед полюс 24 на вход сдвигового регистра 3, Пусть на выходе первого разряда сдвигового регистра 3появляется разрешение, которое постзгаит на один из входов элемента И 4. Это разрешение пройдет элемент К 4 , так как на втором его входе есть разрешение с полюса 29 модели верщшы 1 , и постутшт па полюс 26 этой Же модели. Сигнал с полюсй 26, иройда элементы И 9 и ИЛИ 13, постзгашт на,единичный вход триггера 5 и установит его в единичное состоявЕие. Этим будет осушествлен выбор модели вершины 1, .

Таким образом выбирается любая вершина графа и далее для определения мяожёства необходимо огфеделвгть множество вершин, которые могут быть дсзстигнуты из вершины Xij Построение Множества осуществляется pacnpocipaненйем по графу импульса, синмаемогр через формирователь одийочного импупы са 19 с единичного выхода триггера S, выбранной модели вершины.

Формиротзатель одиночного имоуяьса 19 выдает импульс на шмшс 21. Далее этот импульс, распростракяясь по графу, устанавливает триггера 5 моделей в единичное состояние. Это происходит поступлением импульса с полюса 20 элементы И 7 и ИЛИ 13 на едишпный вход этих триггеров. Таким образом, этот импульс, проходя с полюса 2О на полюс 21, будет распространяться по исследуемой сети к формировать во Г Х|. Единичное состояние триггеров 5 моделей вершин будет свидетельствовать об их принвдлежностн этому множеству Г X1 . После этого блок управления 2 начинает определять множество Г X , мно жество вершин из которых может быть достигнута Х -ая вершина. Для этог необходимо произвести переориентирование графа, которое осуществляется пу тем снятия разрешения с полюсов 23 всех моделей вершин и подачей разреше ния блоком управления 2 через попюе 27 на все полюса 28. При этом входами у всех моделей вершин являются яолюса 21 а выходами - полюса 2О. Разрешение с полюса 28, пройдя эле менты И 1О и ИЛИ 14, поступит на единичный вход триггера 6 выбранной модели вершийы, так как у нее на втором входе элемента И 10 есть разрешение. Сигнал на едийкчном входе триггера 6 установит его в еааййчное состояние, что снимет разрешение со входа элемента И 7. Построение множества Г Х осуществляется импульсом по Сигналу, ciaaмаемому формирователем одиночного им пульса 18 с единичного выхода тригге. ра 6 выбранной модели вершины. Формирователь одиночного импульса 18 вы.дает импульс на полюс 20. Далее этот импульс, pacnpocrpaHirecb ао rpf, ус- танавйявает триггера i6 моделей в едиаичное состояние. Это об есвёчйвается аостуяяеннем вмяульс© 21 врвз эяеМШ5РЫ И S и ИЛИ 14 на едиийчйьй вхо триггеров 6. Таким , лроходя с ttojBdca 21 на полюс 20, будет спрост а Шться по йссяейуе юй се ти и формирсфать множество Г . Единичное сострянне триггеров 6 йо«деяей вершин будет свидетельствовать о пршгадлежврсти мвр сеству После построешя множеств Г X-f и Г Xf в моделях 1 триггеры 5 я б одновремемво назсодзшнеся в eaawPtnoM состоянии, свидетвльствукп о том, что coOTBetcTByroioH© нм верашш исследуемого графа удовлетворяют условию С(Х)аГ X|flr Xfи макснмвпыюму сЕлшо-свззному 1юд1фд 4, одной из вершин которого выбранная . Метка сфс мированного максимального скпьао-свазного подграфа осушест- вяаетсз подачей нмйуяьса блшсом управления 2 через пошос 31 на полюс 25.всех моделей . Этот нмнуяьс 11ройдя через элемент И 12 в моделях ве{Я1ШН, в которых, триггера 5 в 6 9°повременно находятся в единичном состоянии, поступит на вход счетчика 16 и в нем запомнится. Как тольжо будет сформирован н помечен максимальный связный подграф, блок управления 2 снимет разрешение с полюсов 28 всех моделей вершин и перейдет к формированию новых максимальных сильно-связных подграфов. Исключение вершин, принадлежаших уже сформировантам подграфам, из дальнейшего рассмотрения осуществляется путем {швертировання элементом НЕ 15 сигнала, поступающего с йыхода элемента И 11. Этот инвертированный, снгнал поступает на полюс 29, снимаяразрешение с йход ов соответствующих схем И 4j . В дальнейшем блок управления 2 устанавливает 5 н 6 в нулевое состояние у тех моделей вершин, которые не принадлежат сформированному подграфу. После чего блок управления пронэводят аналОгичнь1М 1 бразом выбор новой модели вершины и процесс формирования нового максимального сШ1ьносвязного подграфа повторяется. Процесс разложения графа на максимальные сильно-свазнь1е подграфы зшсанчивается только в том случае, если на выходе сдвигового регистра 3 появится сигнал, который поступает на пояюс 30 блока управлення 2. Это свидетельствует о том, что в графе нет ия одной вершины, которая не входила бы в какой 4габудь KffUfCсимальный сильно-связный подграф. Число импульсов, занесенное в C4eiv чики 16 моделей вервиин, будет отражать номер подграфа, к которому относятся Эти модели вершш. Данный номер индиШ1руется блоком индвкшши 17, вход которого связан с вй1зк дом счетчика 16. Введение новьцс блоков н связей мезкду ними HosBon JT доставь аостазвпенной цели - расширения фушашональных возможностей путем учета вершин исслёоуе мого графа. формулавзобретення Устройство они исспедсжания графов, содержащее модели вершян, соединёнаыв между собой согласно тояопогин нссле дуемого графа, регистр, вход и первый выход которого подключены к кыжопу и входу блока управления, второй ретий н четвертый выходы которого сое

диневы соответственно с первым, вторым tf третьим входами моделей вершин, ин- формшхиоявые выходы решстра соединены с первыми входами алементов И группы, второй вхоа каждого из которых подключена первому вьикоду соответствующей модели вершины, выходы алемевтов И группы подкяюч шы соответственао к четвертым яжэдвм моделей вершни, каждая из ко торых содержит первый триггер, первый Мемеиг ИЛИ, первый элемент tItyjD т л и ч а ю ш е е с я тем, что,с целью расщирекяя фующисшальных возможноетей за счет юзедения учета супзАо-СЁяз ных подграфсю, каждую модель вершииы Грефа допоаиятельно введены второй Tpitrrep, первый к второй формырователв импульсов, второй, третий, четвертый, вять и «юстой ёНекШггьс И, влемещ- ИЛИ элемент НЕ, счетчик им пульсов;, блок индикации, пртпем чет ВДУТЫЙ вход модвяв вершины соединен с первыми входами первого и iwopOrt влементов И, вторые входы ко«. торых подюйочеиы к первому и второму вдсодам модели вершша 1 графа, выходы оврвргр и вторс го элементов И соедвtttttaa состветствеимо с входами вержях) и второго элемевтов ИЛИ, выходь кото{ядх подключены к ejitiiBSPiHHM входам nef Ekoro и второго TpffrrepoB, ОАИИЯчвый выход верюсяч) Триггера под клхУчеи к первому входу четвертскго элемента И и ко входу первого форм{{рова тблд itiMRynbcaB, выход которого соеди8ви со вторым выходом Модели вершииь графа и с первым входом третьего эле8

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

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

ИсточтЁр информации, пршшть е во iN MasHe при «кспертязв

1.Авторское свидетельство СССР N9 305484, кя. Q 06 Q 7/122, 28.09.71.

2.Авторское свидетельство СССР № 408312Гкл. F15/2O, 29.03.74.