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

 

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

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

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

РЕСПУБЛИН а91В <в (SD 4 G 06 F I 20

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

ПО ДЕЛАМ ИЗОбРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 ) 4251458/24-24 (22) 26.05 .87 (46) 15.12.88. Бюл. № 46 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О .Н,Костюк (53) 681,333(088.8) (56) Авторское свидетельство СССР № 1124318, кл. G 06 F 15/20, 1984.

Авторское свидетельство СССР № 1!74937, кл. G 06 F 15/20, 1985 ° (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СВЯЗНОСТИ ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано для исследования графов при решении задач, допускающих теоретико-графовое представление . Цель изобретения — расширение функциональных возможностей за счет определения носителей компонент сильной связности - достигается тем, что в устройство, содержащее генератор тактовых импульсов, элемент НЕ, элемент задержки, элемент И, счетчик, дешифратор, первую и вторую группы элементов И, матрицу моделей дуг, дополнительно введены третья и четвертая группы элементов И, с первой по третью группы элементов ИЛИ, регистр, второй счетчик, второй элемент И, второй элемент НЕ, втброй элемент задержки и элемент ИЛИ. 2 ил.

144480 7

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

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

Информация о. топологии исследуемого графа заносится в триггеры моделей дуг в виде матрицы смежности. В ходе работы устройства на основании этой информации определяется состав !5 носителей для каждой компоненты сильной связности исследуемого графа, т.е. осуществляется разбиение множества вершин графа на подмножества, каждое из которых образуется сильно- 20 связными вершинами, определяется также число таких подмножеств, На фиг. 1 приведена структурная схема устройства; на фиг. 2 — структурная схема модели дуги.

Устройство содержит генератор тактовых импульсов, первый элемент И

2, вход 3 пуска устройства„ первый элемент НЕ 4, дешифратор 5, выход б признака окончания работы устройства, ЗО первый счетчик 7, первую Я и вторую

9 группы элементов ИЛИ, матрицу моделей 10 дуг, первую группу элементов И 11, вторую группу элементов И

12, первый выход 13 моделей !0 дуг, второй выход 14 моделей 10 дуг, первый вход 15 моделей 10 дуг, второй вход 16 моделей 10 дуг, третью 17 и четвертую 18 группы элементов И, третью группу элементов ИЛИ 19, регистр 20, первые информационные выходы 21 устройства, элемент 22 ИЛИ, второй элемент НЕ 23, второй элемент

И 24, элемент 25 задержки, второч счетчик 26, выход синхронизации 27 устройства, вторые информационные выходы 28 устройства, вход. 29 начальной установки.

Каждая модель 10 дуги содержит триггер 30, первый элемент И 31, второй элемент 32 задержки.

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

В исходном состоянии работа устройства заблокирована нулевым сигналом на входе 3 пуска устройства, в счетчиках 7, 26 и регистре 20.хранятся "0" во всех разрядах, что обеспечивается сигналом на входе 29 начальной установки. При этом сигналы опроса матрицы моделей дуг с выхода дешифратора 5 отсутствуют и на всех выходах 13, 14 моделей дуг 10,имеются логические "0", которые через элементы И 17 поступают на информационный выход устройства, на выходе элемента

HE 4-"1"

Исходная информация о топологии исследуемого графа заносится в триггеры 30 моделей дуг, после чего устройство готово к работе.

При подаче на вход 3 сигнала

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

Опрос матрицы моделей 10 дуг состоит в следующем. На такте К счетчика 7 сигнал опроса в виде "1" с К-го выхода дешифратора 5 поступает через элемент ИЛИ 8 и открытый тактовым импульсом элемент И 11 на входы 15 моделей 10 дуг К-й строки матрицы, а через элементы ИЛИ 9 и И 12 на входы

1б моделей 10 дуг К-ro столбца матрицы. При этом на выходах 13 моделей

10 дуг К-й строки матрицы в триггерах

30 которых содержится "1", также появляется "1 которая вызывает появление "1" на выходе элемента KIN 8, что приводит к появлению сигнала опроса в И-й строке матрицы моделей дуг и т,д. Наличие "! на выходе соответствующего элемента ИЛИ 8 при опросе строки К означает существование в исследуемом графе пути из вершины с индексом К в вершину с индексом P. Аналогично на выходах 14 моделей 10 дуг К-ro столбца матрицы, в триггерах 30 которых содержится "1", также появляется "!", вызывающая появление "1" на выходах соответствующих элементов ИЛИ 9, а значит, и onрос соответствующих столбцов матрицы.

Наличие "1" на выходе P-ro элемента

ИЛИ 9 второй группы при опросе столб-.. ца К означает существование пути из вершины с индексом P в вершину с индексом К. Таким образом, при опросе строки К и столбца К наличие "1" на

144480 выходах элементов ИЛИ 8 первой группы определяет множество вершин, связанных с вершиной К,путями, в которых К является начальной, а наличие

11 I!

1 на выходах элементов ИЛИ 9 второй группы — множество вершин, связанных путями с К, в которых К является конечной ° Индексный состав этих множеств определяется соответствен- 10 но номерами элементов ИЛИ первой 8 и второй 9 группы. Пересечение данных множеств определяет состав множества вершин, являющихся носителями компоненты сильной связности, содер- 15 жащей вершину К. Пересечение отыскивается на элементах И 18 четвертой группы и поступает в виде кода с единицами в разрядах, номера которых соответствуют индексам вершин — носи- 20 телям полученной компоненты сильной связности, на выходы 21 устройства через элементы ИЛИ 19 на входы регистра 20. Код пересечения также поступает к четвертой группе элементов

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

22 появляется "1", поступающая на вход второго элемента НЕ 23 и запрещающая прохождение тактового импульса на выход 27 синхронизации вывода 40 и к второму счетчику 26. Тем самым блокируется появление синхросигнала, являющегося признаком вывода информа ции с выходов 21, и изменение содержимого второго счетчика 26, учитываю- 45 щего число компонент сильной связности в исследуемом графе. В случае получения информации о компоненте сильной связности, не зафиксированной на предыдущих тактах, ни в одном из 50 разрядов сравниваемых кодов совпадения не будет и на выходах всех элементов четвертой группы И 18 будут логические "0". На выходе элемента

ИЛИ 22 также будет "0", который через 55 элементы НЕ 23 и 24 И разрешит прохождение тактового импульса с генератора 1 на выход синхронизации 27 и

4 к второму счетчику 26. Тем самым будет подтвержден вывод информации о носителях очередной компоненты сильной связности с выходов 21 . Задержка тактового импульса с генератора

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

19 третьей группы соединены с его же входами, то на каждом такте происходит поразрядное объединение текущего кода пересечения множеств с зафиксированными ранее ° Тем самым исключается потеря информации, полученной на предыдущих тактах.

Группы элементов И 11, 12 служат для предотвращения искажения результирующей информации из-за наличия обратных связей в целях опроса матрицы модели 10 дуг. При переходе тактового импульса в уровень "0" элементы И 11, 12 закрываются по второму входу, тем самым разрывая цепи опроса строк и столбцов матрицы моделей .10 дуг и исключая прохождение сигналов уровня "1" по этим цепям с выходов элементов ИЛИ первой 8 и второй

9 групп на их же входы.

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

При достижении первым счетчиком 7 соответствующего состояния йа последнем выходе дешифратора 5 появляется сигнал, служащий признаком окончания работы, который поступает на выход 6 устройства и на элемент НЕ 4, Нулевой сигнал с выхода элемента НЕ 4 блокирует прохождение тактовых импульсов с генератора 1 через элемент И

2. В счетчике 26 фиксируется общее число компонент сильной связности исследуемого графа. При этом работа устройства заканчивается.

После обнуления регистра 20, первого 7 и второго 26 счетчиков сигналом на входе 29 начальной установки и занесения исходной информации о

1444807. топологии исследуемого графа устройство готово к следующему цнклу работы.

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

Устройство для исследования связности графов, содержащее генератор тактовых импульсов, первый элемент

И, первую и вторую группы элементов

И, первый элемент HF., дешифратор, матрицу моделей дуг„ первый счетчик, информационные выходы которого соединены с информационными входами дешифратора, а счетный вход соединен с выходом первого элемента И, первый вход которого является входом пуска устройства, второй вход соединен с . выходом генератора тактовых импульсов, а третий вход с выходом nepsoro элемента НЕ, вход которого соединен с (К+1)-м выходом дешифратора (где К вЂ” количества вершин в графе), отличающееся тем, что, с целью расширения функциональных возможностей за счет определения носителей компонент сильной связности„ в устройство введены первая, вторая и третья группы элементов ИЛИ, третья и четвертая группы элементов И, регистр, второй элемент задержки, элемент ИЛИ, второй элемент НЕ, второй элемент И, второй счетчик, счетцьтй вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом элемента ИЛИ, входы которого соединены с выходами соответствующих элементов И четвертой груттпы, первые входы которых соединены с первыми входами соответствующих элементов ИЛИ третьей группы, выходами соответствующих элементов И и являются первой группой информационных выходов устройства, информационные выходы второго счетчика являются вторыми информационными выходами устрой5

45 ства, счетный вход второго счетчика является тактовым выходом устройства, а вход сброса второго счетчика соединен с входами сброса первого счетчика и регистра и является входом сброса устройства, вход первого элемента HE соединен с выходом признака окончания циклà работы устройства, информационные выходы регистра соединены с вторыми входами соответствующих элементов И четвертой группы и элементов ИЛИ третьей группы, выходы элементов ИЛИ третьей группы соединены с соответствующими информационными входами регистра, вход записи которого соединен с вторым входом второго элемента И и выходом второго элемента задержки, вход которого сое.динен с выходом первого элемента И, первые входы элементов И первой и второй групп объединены и соединены с выходом первого элемента И, M-й выход дешифратора (где М=1...,,К) соединен с первыми входами M-х .элементов ИЛИ первой и второй групп, входы с второго по К-й М-го элемента

ИЛИ первой группы соединены с первыми выходами соответствующих им моделей дуг M-го столбца матрицы, выход

N-го элемента ИЛИ первой группы соединен с вторыми входами соответствующих М-х элементов И"первой и третьей групп, выход M-го элемента И первой группы соединен с первыми входами моделей дуг М-й строки матрицы, выход

M-ro элемента ИЛИ второй группы соединен с первым входом соответствующего М-го элемента И третьей группы и вторым входом соответствующего М-го элемента И третьей группы, входы с второго по К-й М-го элемента ИЛИ второй группы соединены с вторыми выходами соответствующих моделей дуг N-й строки матрицы, выход М-го элемента

И второй группы соединен с вторыми входами моделей дуг М-го столбца матрицы.

1444807

1444807

М

Составитель О. Гречухина

Редактор М.Циткина Техред А.Кравчук Корректор Г.Решетник

Заказ 6508/50 Тираж 704 Подписное

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

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

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