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

пц 643880 ОП ИСАНИЕИЗОБРЕТЕНИЯ й АВИИЧЗОМУ СВИ ВТИЛЬСТВУ Своз СоеетсимяСовналмстимесваРесяубямк(51) М 15/ Гещаервтвввввй квивтвт СССР вв девам взвбрвтвниР я вткритвР8.01.79 Д,ата опубликования описаии А. Г. Додонов, В. В. Федотов, Н, В, фед и В. М. Шишмарев 2) Авторыизобретения витель Институт ел) УСТРОйСт вершинызадачуИзобретение относится к области электронного моделирования н может быть использовано ддя решения задач на графах, в частности, для разложения грвз на максимальные сильно-связ ные подграфы.Известно устройство ддя нссдедова. ння экстремальных путей награфе, содержащее элементы И, триггеры,-счетчик, элементы НЕ Я. Устройство позволяет определят дерево экстремальных путей ддя арбой начальной Однако оно не может решатьопределения максимальных сных графов.Наиболее близким по технической сущ ности к предлагаемому является устройство содержашее 1 модели вершин, сое .днненные между собой согласнотололо гин исследуемого графа, . регистр, вход н первый выход которого подключены первому выходу н входу блока управце ння, второй, третий н четвертый выходы которого соединены соответственно с,динамики АН Украинской ИССЛЕДОВАНИЯ ГРАФОВ 2первым, вторым и третьим входами моделей вершин, информационные выходырегистра соединены с первыми входамнэлементов И группы, второй вход каждого нз которых подключен к первому 3 выходу соответствующей модели вершины, выходы элементов К группы подключены соответственно к четвертымвходам моделей вершйн, каждая нз ксеорых содержит первый триггер, первый тв элемент ИЛИ, первый элемент И 2,Однако, известное устройство непозволяет произвести разложение графана максимальные сильно-связные поаграфы.15 Целью изобретения является расппьрепке фуюааоюаьных возможностей засчет введения учета сильно-связныкйодграфов. Данная цель достигается тем,что в каждую модель вершины графа до 2 в нолннтельно введены второй триггер, первый н второй формирователЬ импульсов,второй, третий, четвертый, пятый н шес.той элементы И, второй элемяйт ИЛИ,643880 элемент НЕ, счетчик импульсов, блокиндикации, причем четвертый вход модели вершины грвфв соединен с первымивходами первого и второго элементов И,вторые входы которых подключены к пер- увому и второму входам модели вершины грвфв, выходы первого и второго элементов Исоединены соответственно с первыми входами первого и второго элементовИЛИ,выходы которых подключены к единичным гОвходам первого и второго триггеров,единичный выход первого триггера подгцпочен к первому входу четвертого элемента И и ко входу первого формирователя импульсов, выход которого соеди- г 1иен со вторым выходом модели вершиныграфа и с первым входом третьего элемента И, второй вход которого подключен к нулевому выходу первого триггера, третий вход третьего элемента И 20соединен со вторым входом втъоого элемента И и с первым входом модели вершины графа, выход третьего элементе Исоединен со вторым входом второго элементе ИЛИ. 23Единичный выход второго триггераподключен ко входу второго формироввтедя импудьсов, к первому входу,шестого элементе И и ко второму входу четвертого элементе И, выход которого сое- Мдинен с первым вищом пятого элементаИ и через элемент ЯЕ подключен к первому выходу модели веригины графа, третий вход которой соединен со вторымвходом пятогс элементе Я, выход кото- ЗЗрого подключен ко входу счетчика ичпульсов, выход которого соединен с блоком ийдиквпии, выход второго формирователя импульсов подключен к третьемувыходу модели вершины графа и ко вто Орому входу шестого элемента И, третийвход которого соединен со вторым входомпервого элемента И и со вторымвходом модели вершины графа, выходшестого элемента И подключен ко второму входу первого элементе ИЛИ,Прецлвгвемое устройство предстввлечо нв чертеже, Оно содержит моделивершин исследуемого граФа 1,Егг,блок управления 2, (сдвиговой) регистр 5 О3, группа элементов И 4 4 и .В соствв каждой модул вершины11- 1 входят; триггеры 5, 6, элементыИ 7-12 элементы ИЛИ 13, 14, элемент НЕ 15, счетчик импульсов 16, блокиндикации 17, формироввтели одиночныхимпульсов 18, 19, полгосв модели вершщ20-31,4Устройство работает следующим обрезом.Посредством полюсов 20 и 21, модели вершин коммутпруются между собойи соответствии со структурой исследуемого графа. Сдвиговой регистр 3 н счетчики 16 обнуляются. Триггеры 5 и 6всех моделей вершин уствнввливвются.внулевое состояние.Вначале в графе определяется множество вершин Г Х 1, достижимых изХ -ой вершины, то есть определяетсямножество вершин, для которых сушесьвует путь из Х-ой веошины. Для этогоблок управления 2 через полюс 22 выдвет разрешение нв полюса 23 всех моделей вершин 1;- 1 , Выбор Х: -ойвершины осуществляется, йоком управления 2 путем подачи импульса через полюс. 24 нв вход сдвигового регистре3, Пусть нв выходе первого разрядесдвигового" регистре 3появляется рвз.решение, которое поступит нв один извходов элемента И 44, Это разрешениепройдет элемент И 4.г, твк квк нв втором его входе есть разрешение с подгосв29 модели веригины 1, и поступит нвполюс 26 этой же модели. Сигнел сполюса 26, пройдя элементй И 9 иИЛИ 13, поступит нв,единичный входтриггере 5 и уствновит его в единичноесостояние. Этим будет осуществлен выбор модели вершины 1 .Таким обрезом выбирвется любая вершине графаи далее для определениямножества Г Х . необходимо определитьмножество.вершин, которые могут бытьдостигнуты из вершиныХ, Построениемножестве осугцествдяется рвспрост ранением по графу имцульсв, снимвемогочерез формирователь одиночного импуль-са 19 с единичного выхода триггере 5,выбранной модели вершины.Формироъвтель одиночного импудьсв19 выдает импульс нв погпос 21. Далееэтот импульс, рвспрострвняясь по графу,устанавливает триггера 5 моделей в единичное состояние. Это происходит поступлением импудьсв с полюса 20 черезэлементы И 7 и ИЛИ 13 нв единичныйвход этих трьгггеров. Твким образом,этот импульс, проходя с полюсе 20 ивполюс 21, будет рвспрострвняться поисследуемой сети н формироввть множество Г г Х. Единичное состояние траггеров5 моделей вершин будет свидетельствоВвть Об их принюдлежности этому мноффьщ вулф Х",повременно находятся в единичном состоянии, поступит на вход счетчика 16 и в нем запомнится.Как только будет сформирован и помечен максимальный связный подграф, блок управления 2 снимет разрешение с полюсов 28 всехмоделей вершин.и перейдет к формированию новых максимальных сильно-связных подграфов, Исключение вершин, нринадлежащих уже сформированным подграфам, из дальнейшего рассмотрения осуществляется путем инвертирования элементом НЕ 15 сигнала, поступающего с выхода элемента И 11. Этотинвертированный, сигнал поступает на полюс 29, снимак разрешение с входов соответствующих схем И 4-4. В дальнейшем блок управлении 2 устанавливает триггеры 5 и 6 в нулевое со. стояние у тех моделей вершин, которые не принадлежат сформированномуподграфу. После чего блок управления производит аналогичным образом выбор новой модели вершины и процесс формирования нового максимального сильно- связного подграфа повторяется. Процесс разложения графа на максимальные сильно-связные подграфы заканчивается толь. ко в том случае, если на выходе сдвигового регистра 3 появится сигнал, который поступает на полюс 30 блока управления 2. Это свидетельствует о том, что.в графе нет ни одйой вершины, которая не вХодила бы в какой-нибудь максимальный сильно-связный подграф.Число импульсов, занесенное в счетчики 16 моделей вершин, будет отражать номер подграфа, к которому относятся эти моделивершии. Данный номер индицируется блоком индикации 17, вход которого связан с выходом счетчика 16.Введение новых блоков и связей между ними позволяет достичь постайлеиной цели - расширения фуизттиояальных возможностей путем учета вершин исследуе мого графа. Устройство для исследования графов, содержащее модели вершин, соединеииывмежду собой согласно топологии иссле дуемого графа, регистр, вход и первый выход которого подключены к первому выходу и входу блока упраеления, второйр третий и четвертый выходы которого сов 5 643880 6После этого блок управления 2 начинает определять множество Г Х, множество вершин нз которых может бытьдостигнута Х -ая вершина, Для этогонеобходимо произвести переориентированне графа, которое осуществляется путем снятия разрешения с полюсов 23всех моделей вершин и подачей разрешения блоком управления 2 через полюс27 на все полюса 28, При этом входа- т 6ми у всех моделей вершин являются полюса 21, а выходами полюса 20.Разрешение с полюса 28, пройдя элементы И 10 и ИЛИ 14, поступит наединичный вход триггера 6 выбранной Ммодели вершины, так как только у неена втором входе элемента И 10 естьразрешение. Сигнал на единичном входетриггера 6 установит его в единичноесостояние., что снимет разрешение со 2 Овхода элемента И 7,Построение множества Г Х осуществляется импульсом цо сигналуу сяяфмаемому формирователем одиночного импульса 1 8 с единичного выхода тригге.ера 6 выбранной модели вершины, Формирователь одиночного импульса 18 вы.дает импульс на полюс 20. Далее этотимпульс, распространяясь по графу, устанавливает триггера 6 моделей в еди- ЗЕяичное состояние. Это обеспечиваетсяпоступлением импульсе 21 через элементы И 3 и ИДЯ 14 на единичщай входтриггеров бе ТазиМ ебразомз ВРОХОдяс йолюса 21 иа. полюс 20, импуаъс будет распросраняться по исследуемой сети и формировать множество Г" Х,Единичное состояние триггеров 6 меумей вершин будет свидетельствоватьо принадлежности вертпин множествуГПосле построения множеств Г ХиГ Х в моделях вернтин 1,- 1 тригИгеры 5 н 6, одновременно находящиесяв единичном состоянии, свидетельстиутото том, что соответствующие им мршиньтисследуемого графа. удовлетворятот условию СХ )Г Х ПГ ;и прниадлежачмаксимальному сильно-связному тждгрьфу, одной из.вершин которого яВляется Ф о р м у л а и з о б р е т е и и явьтбранттая вертяииа,Метка сформированного максимального сильно-связного подграфв осуществляется подачей импульса блоком уттравлеввя 2 через полюс 31 на полюс28.всех моделей вершин. Этот импульсйройдя через элемент И 12 в. моделяхвершин, в которых триггера 5 и 6 юе7 6438дииены соотвегственно с первым, вторыми третьим входамн моделей вершин, инФормапионньте выходы регистра соединеныс первыми модами элементов И группы,второй вход каждого из которых подключен.кпервому выходу соответствующей моделивершины, выходы элементов И группыподключены соответственно к четвертымвааам моделей вертив, каждая из которых содержит первый триггер, первый та:элемеиг ИЛИ, первый элемент Н,о тл и ч а в ш е е с я тем, что,с цельюрасширения Футвциональных возможностей за счет введения учета снльйо-сбяз-ньтх подграфоь, в камсдую модель верши тны граФа дополнительно введены второйтриггер, первый к второй формирователиимпульсов, второй, третий, четвертый,пятыйи щестой элементы И, второй " элеменг ИЛИ, элемент НЕ, счетчйк им- юпульсов блок индикации, причем четьвертый вход модели верщитты графасоединен с первыми входами первого ивторого элементов И, вторые входы которык подключены к первому и второму 2входам модели вершины графа, еьтходыпервого и второго элементов И соединены соответственно с первыми входаинпервого и второго элементов ИЛИ, вы"хоаа которых подктпотены к едйиичным Мвтащем первого и. второго триггеров,единичный выход первого триггера подключен к первому входу четвертого элемента И и ко входу первого Формирова велю мнульсов, выход которого соеди ииеи со вторым выходом модели верчтиньтграФа и с первым входом третьего эле 80 8мента И, второй вход которого подключен к нулевому выходу первого триггератретий вход третьего элемента И соединен со вторым входом второго элементаИ и с первым входом) модели вершиныграфа, выход третьего элемента И собдюпен со вторым входом второго элемента ИЛИ, единичный выход второго триггера подключен ко входу второго Формирователя импульсов, к червому входушестого элемента И и ко второму входучетвертого элемента И, выход которогосоединен с первым входом пятого элемента И и через элемент НЕ подключенкпервому выходу модели вершины граФа, третий вход которой соединен совторым входом пятого элемента И, выход ксторого подключен ко входу счевчика импульсов, выход которого соеди-.нен с блоком интпскапни, выход второгоФормирователя импульсов подключен ктретьему выходумодели вершины граФаи ко второму входу шестого элементаИ, третий вход которого соединен совторым входом первого элемента И исо вторым входом модели вершиныграфа, выход шестого элемента И подключен ко зтдрому 1 входу первого элемента ИЛИ,Источники информации, принятые вовнимание при экспертизе.1. Авторское свидетельство СССР% 308484, ил. О 06 8 7/12228.09 712. Авторское свидетельство СССР6 43880 Составите,ишвили Тех риценко Подписноеета СССР Тираж779 НИИПИ Государственно по делам юобрете 13035, Москва, Ж-Э., д. 4/ 4 род ул Пр П нтф, г Редактор Д, Яе,Заказ 8223/4Ц Колчин Ю. Ниамет Коррек ний и открытийб, Рауаскаа