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

 

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

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

Республик

О П И С А Н И Е ()635490

ИЗОБРЕТЕ И И Я

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

Ф= ч (61) Дополнительное ж авт; твид-ву— (22) Заявлено 21.10.76 (21) 2413836, 18-24 (51) 11.Кл. 6 06 F 15/20 с присоединением заявки ¹â€” (23) Приоритет—

1осудаоствеииый комитет (43) Опубликовано 30.11.78. Б оллетечь ¹ 44 (53) УД1 681.333 (088.8) по делам изобретеиий и открытий (45) Дата опубликования описания 30.11.78 (72) Авторы (э4) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

НЕОРИЕНТИРОВАННЫХ ГРАФОВ

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

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

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

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

Цель изобретения — расширение функциональных возможностей устройства II)Te r определения суммарного веса входящих в дерево ребер.

Указанная цель достигается тем, что устройство содержит индикаторы, элементы задержки, суммирующий счетчик, генератор импульсов и выходной индикатор, входом через суммирующий счетчик подключенный к выходам счетчиков, вход каждого из которых через соответствующий элемент задержки соединен с первым выходом генератора импульсов, второй выход которого подключен к вторым входам запоминающих триггеров. Выход каждого управляемого ключа второй группы подключен к входу соответствующего индикатора, выход элемента И соединен с входом генератора импульсов и с вторыми входами управляемых ключей второй группы.

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

Она содержит блок 1 перебора сочетаний, командную шину 2, запоминающие

15 триггеры 8, шину 4 установки устройства в исходное состояние, первую группу управляемых ключей 5, индикаторы б, вторую группу управляемых ключей 7, шину 8 проверки проводимости, элемент И 9, гснера20 .тор 10 импульсов, элементы 11 задержки, счетчики 12, суммирующий счетчик 13, выходной индикатор 14 и шину 15 считывания.

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

50 пропорционально весу соответствующего ребра. Устройство работает по тактам fi, 1, tç k! 1 .

В такте t! по шине 4 постугает с1;гнал установки устройства в искодное положение, l станаВЛИВЯ10щпй В н ль запомина!0щие триггеры 8 и генератор 10 импульсов.

При подаче сигнала на командную шину 2 блок перебора сочетаний образует последовательность всевозможнык сочетачий по (М вЂ” 1)-му ребру из 111 имеющихся. В к".kiiдом такте t2 на выходе блока перебора сочетаний появляется одно из сочетаний

С„", которое поступает на зкоды запоминающих триггеров 8, соответстзу1ощих ребрам, ко",орые присутствуют в образованном блоком перебора сочетании ребер. Запоминающие триггеры 3 перебрась;заются в единичное состояние и в соответствии с запомненной комбинациеи реоер открывают соответствующие управляемые ключи 7 и

5. Между входами открыты.; управляемых ключей 7 образуется электрический контакт. Если при случайном выборе ребер блоком перебора сочетаний сочетание их. обеспечивает образование связного графа иа исследуемом множестве верши-i, элсктричсский контакт устанавливается между всеми управляемыми ключами 5. В том случае, если выбранное сочетание ребер ооразует несколько компонент связности, электрический контакт между управляемыми ключами нарушается и они образуют две группы или оолее.

В такте t.- по шине 8 поступает сигнал проверки проводимости на вкод произвольно выбранного управляемого ключа 5, подключенного к шине 8 проверки проводимости. В том случае, если выбранная блоком 1 перебора сочетаний комбинация ребер образует связные граф, сигнал проверки проводимости проходит через все открытые управляемые ключи 5 и с выхода каждого из ник проходит на входы элемента И 9. Так как сигнал проверки проводимости присутствует на зсек входах элемента И 9, он появляется на его зыкоде и проходит на открытые запом1!нающими триггерами 8 управляемые ключи 7, а также запускает генератор 1О импульсоз

lH c IeT IIIKH 12. И мну 7ьcbi c PPHPI! B . A" Я 10 через элементы 11 задержки поступают на вкоды счетчиков 12 до тек пор, пока не сработает элемент задержки, который через время, пропорциональное весу соответствующего ребра, разорвет цепь прохождения импульсов с генератора 10. Таким образом, показания счетчика 12 пропорциональны весу соответствующего ребра.

Одновременно с этим сигнал проверки проводимости, проходя через открытые управляемые ключи 7, засвечивает индикаторы б, присутствующие при данном розыгрыше. В том случае, если при выборе ребер блоком перебора сочетаний получился двук- или более компонентный граф, си. нал проверки нроводимости поступает только на ту часть управляемых ключей 5, которая оказывается связанной с подключенной к шине 8 проверки прозоднк;ости управляемым ключом 5. В результате э-.о. го сигнал проверки проводимости появляетоя только на части входов элемента И 9 и oki срабатывает, т. е. выходной сигнал на нем отсутствует.

В такте t по шине 15 считывания подается сигнал считывания на счетчики 12, в результате чего информационные с1!гналы, соответствующп чис.там подсчнтан нык импульсов, поступа!от на суммирующий счетчик 18 и соединенный с ним ин20 дикатор 1-- суммарной длины исследуемого дереза высвечивает число импульсов, соответствую цее суммарному весу всех входящих з данное дерево ребер.

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

Устройство для моделирозаги!я неориентированнык графов, содержащее блок перебора сочетаний, выкоды которого подИ ключены к первым входам запоминающих триггеров, одни выкоды которых через первую группу управляемык ключей соединены с соответству1ощими вкодами элемента И, другие выкоды запоминающик тригЗЗ геров подключены к первым входам управляемык ключей второй группы, и счетчики, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем определения суммарного веса вкодящик в дерево ребер, оно содержит индикаторы, элементы задержки, суммиру!Оц!Нй счетчик, генератор импульсов и выходной индикатор, вкод которого через суммирующий счетчик подключен к выходам счетчиков, вход каждого из которых через соответствующий элемент задержки соединен с первым выходом генератора импульсов, второй выход котоpoi o подкл1очен к вторым входа м 3 а по ikI50 нающпк триггеров, выход ка кдого управляемого ключа Второй группы подключен к входу соответствующего индикатора, выход элемента И соединен с входом генератора импульсов и с вторыми входами упБ» равляемык ключей второй группы.

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

Ilk!!!ìàIlèå при экспертизе:

1, ?Вторское свидетельство СССР

27 .906, Ci 06 С! 7, 18, 1970.

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

3 "9538. кл. С- 06 С! 7/48. 1972.

fgvпед Q $ = :, c кз

1-,с:1г::т, (. И. Снмкина

Редактор И. Грузова

Тпп. Харьк. фпл. пред хГ .зтепт»

Заказ 843/1268 11зд, . з 748 Подписное

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

Москва, )K,-35, Рзушская::а5., д. 4,5