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

например задачи об оптимальном дереве. связи, оптимальной связывающей сети, Кроме того, это устройство работает в режиме последовательного просмотра и формирования конфигурации путей, не может реализовать алгоритмы осиовременного, параллельного определения путей и деревьев, что увеличивает время решения задачи. Цель изобретения - повышение быстро- |Q , действия и расширение класса решаемых задач. Эта цель достигается тем, что в предложенное устройство введены формирователь импульсов и элемент ИЛИ-НЕ, входы s Ю

которого соединены с первыми выходами блоков моделей ветвей. Выход элемента ИЛИ-НЕ подключен к первому входу блока управления, первый выход которого соединен с первым входом третьего элемента И каждого блока модели ветви. Выход третьего элемента И соединен с нулевым входом первого триггера, второй вход со вторым входоь( второго элемента И и единичным выходом второго триггера,счетц25

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

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

Блок управления содержит два счетчика, элемент задержки, инвертор и два элемента И, первые и вторые входы которых 50

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

аходом одного из элементов И, выход которого подключен к первому выходу блока. Выход другого элемента И соешшен

со вторым выходом блока. Третий и четвертый вхо/гы блока подключены к счетным входам первого и второго счетчиков соответственно.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - функциональная схема блока управления.

Устройство содеряшт блок 1 моделей ветвей, блок 2 формирования топологии.

13-16, входных и выходных полюсов 17-24 (полюса 17 и 18 являются первым и вторым входом, а полюса 19 и 20 первым и вторым выходами блока соответ ственно).

Блок 2 имеет первый 26, второй 27 и третий 28 выходь, первую 29 и вторую ЗО группы входов.

Блок 3 управления имеет два выхода

стоит из элемента задержки 37, двух элементов И 38 и 39, инвертора 40 и двух счетчиков 41 к 42.

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

В исходном состоянии триггеры 10, 11 находятся в нулевом состоянии. В счетчике 7 записано количество импульсов, пропорцисжальное длительностям сографа. В счетчиках 8 и 9 заданы в обратном коде адреса вершин графа, инцидентных, согласно топологии исследуемого графа, данной ветви.i

В блоках 1, не принимающих участие

в моделировании графа, счетчики 8 и 9 находятся в нулевом состоянии.

Фаза 1 - поиск очередной сформированной модели ветви, которая может входить

в решение задачи. После подачи сигналов пуска, формирователь 6 импульсов подает импульсы на входы счетчиков 7 временного интервала. Первым появляется сигнал переключения в том счетчике 7, в кототельность. По этому сигналу в этом блоке 1 устанавливаются в единичное состояние триггеры 10 и 11, и сигнал с единичного выхода триггера 11 поступает

ке 2. По этому сигналу блок 2 выдает на управляющий вход формирователя 6 сир нал, запрещающий подачу импульсов на блок 3 .управления, генератор 4, элемент. 5 ИЛИ-НЕ и формирователь 6 импульсов, Блок 1 модели ветви состоит из счет чика 7 временного интервала счетчиков 8, 9 арреса, первого и второго триггеров , 11, элемента 12 ИЛИ, элементов И 31 и 32 и четыре входа 33-36, и соответствующих им ветвей исследуемого рый была записана самая большая, длиодин из входов первой группы в блосчетчики 7. Признаком удаления ветви из 1рафа служит ешониноо состояние выхода 20 в соответствующем блоке модели вет ви. Фаза 2 - определение связанности всех вершин графа. Если оставшиеся вершины графа связаны между собой, то данная ветвь окончательно удаляется из графа, в противном случае она воз ащается в граф, Одновременно с прекращением формирования длительностей ветвей блок 2 формирования топологии с выхода 26 начинает выдачу импульсов на входы 17 всех блоков. Эти сигналы поступают на входы счетчиков 8 и 9 адреса для автоматического формирования топологии. Первым появляется сигнал на выходе задатчиков 8 или 9 адресов, в которых записан первоначальный адрес В1, потом на выходах задатчиков арресов, в которых записан следующий 1 адрес В2, и т.д. Для провер ки связности ветвей, оставшихся в графе, т.е. в тех моделях 1 ветви, в которых триггер 10 находится в нулевом состояНИИ, по первоначальному адресу В1 блок 2 формирования топологии выдает единичный логический уровень на ЕКОДЫ 18 бло ков 1. В тех блоках 1, в которыхзапи- сан адрес В1 и триггер 10 находится в нулевом состоянии единичный логический уровень с выхода элемента 13 И устанавливает в единичное состояние триггер 11 Теперь на входах элемента 14 И имеются сигналы логической единицы, и единичный сигнал с выхода этого элемента подается на второй вход элемента 16 И. При поступлении сигнала второго адреса с Шз1ходов счетчиков адреса 8 и 9 через элемент 12 ИЛИ на первый вход элемента 16 И единица с его выхода поступает на один из входов второй группы блока 2. Число входов в первой и второй Группах В1ходов соответствует числу блоков 1. При наличии хотя бы одного единичного сигнала на входах ЗО блок 2 формирования ТСЯ1ОЛОГИИ выдает на выход 27 СИ1 нал, который поступает на входы 18 блоков 1. В моделях ветвей, присутствующих в графе, и в которых есть сигналы второго адреса, присутствуют единичные логические уровни на всех входах элемента 13 И. Сигеалы единицы с выходов эл&ментов 13 И поступают на счетные входы триггеров 11. Те триггеры 11, которые в этот Момент времени находились в единичном состоянии, перебрасываются в нулевое состояние, а триггеры 11, находившиеся D нулевом состоянии, переходят з единичное состояние, и таким образом сигналы связности передаются следующим ,моделям ветвей по следующим адресам вершин графа. Чередуя реясимы работы дашюго уст ройства по фазам 1 и 2 находят, например, минимальное связывающее дерево следующим образом. В режиме по фазе 1 импульсы с выхода формирователя поступают одновременно на входы счетчиков- 7 всех блоков 1. Модели ветвей формируют свои длительности по порядку уменьшения их величин, начиная с самой большей.Как только какой-нибудь блок 1 сформировал свою длительность, два триггера 10 и ll устанавливаются в единичное состояние. Единица с единичного выхода триггера 11 сформированной модели ветви поступает на один из Ессодов 29 блока 2. При наличии хотя бы одной единицы на входах 29 блок 2с выхода 28 выдает запрет формирователю 6 на выдачу импульсов формирования временных интервалов, и одновременно начинает выдавать импульсы с выхода 26 на выходы счетчиков 8 и 9 адресов всех моделей ветвей, т.е. производится переключение работы устройства в режиме по фазе 2 для определения связности графа без сформированной и отклю- ченной по фазе 1 ветви. Работа устройства в режиме по фазе 2 описана вьпле. В режиме по фазе 2 подсчитываются сигналы связаности, поступившие на входы ЗО блока 2. Сигналы связаности, собирающиеся по схеме ИЛИ в блоке 2 с выхода 27 поступают на вход 36 блока 3 управления, который подсчитывает их. Конец определения связности оставшегося подграфа определяется элементом S ИЛИ-НЕ. Если хотя бы в одной модели ветви оставшегося подграфа есть сигнал связности, т.е. триггер 1О в соответствующем блоке 1 находится в нулевом состоянии, а триггер 11 - в единичном состоянии, нулевой сигнал с выхода элемента 5 дает запрет в режиме работы устройства по фазе 2 в блок 3 управления. Как только окончится процесс определения связности оставшегося поаграфа в режиме по фазе 2, триггеры 11 всех моделей вервей находятся в нулевом состоянии, и на всех входах элемента 5 присутствуют нулевые сигналы. При этом с выхода элемента 5 выдается на вход 33 блока 3 разрешающий ед1шичный сигнал.

По этому сигналу, определяющему конец определения связности вершин оставшего подграфа, если не будут достигнуты все вершины исходного графа, блок 3 с выхода 31 выдаетсигнал единицы на входы 21 всех блоков 1. В. блоке 1 модели ветви, исключенной из графа в предыдущем режиме по фазе 1, триггер 11 дает разрешающий потенциал на Екод элемента 15 И, и триггер 10 устанавливается в нулевое состоя-10 ние, так как эта ветвь входит в решение задачи. Если исключение ветви в предыду щем режиме по фазе 1 не влияет на связанность вершин исходного графа, блок 3 не выдает сигнала на входы 21 блоков 1 ,и исключенная ветвь не воз1 ащается в граф. В любом случае после прихода сигнала единицы U выхода элемента 5 на вход 33 блока 3 через некоторое время задержки, необходимое для анализа связности вершин, блок 3 с выхода 32 выдае сигнал на входы 24 всех блоков 1, по которому производится сброс триггеров 11 и убираются все сигналы единицы на входах 29 блока 2, т.е. устройство для. моделирования графов снова переключается в режим по фазе 1 и т.д. Устройство останавливается после того, как произойдет формирование временных интервалов и пробное исключение все ветвей графа. Это происходит автоматически за один просчет регенерационнрго счетчика в формирователе, работающем параллельно со всеми счетчиками 7. На этом решение задачи заканчивается,Триг., геры 10 в блоках моделей ветвей принадлежащих минимальному связывающему дереву, находятся в.единичном состоянии Единичные сигналы с выходов 20 моделей 1 ветвей могут подаваться на устройство или табло индикации. При этом исходная информация о длительностях вет вей, записанная в счетчиках 7, восстанав ливается. Величина связывающего дерева может быть определена поочередным суммированием длительностей ветвей ему принадлежащих. Максимальное связывающее дерево на:ходят аналогично, с той лишь разницей, что исходная информация в длительности ветвей графа записывается в обратном коде. Рассмотрим блок 3 управления. Счетчик 41 предназначен для регенерации инфсфмации об адресах в моделях ветвей. Емкость счетчика 41 равна емкости счет чиков 8 и 9 адреса в блоках 1. Перед началом решения задачи счетчик 41 устанавливается в нулевое состояние. Счетчик 42 предназначен, для подсчета количества связных вершин в графе. Перед началом работы устройства для моделирс вания графов в режиме по фазе 2 счет чик 42 сбрасывается по входу 34 в исходное состояние N -V (где N - емкость, счетчика, V - число вершин в графе решаемой задачи). Через V импульсов, поступаюших-на нход 36 блока 3, на выходе счетчика 42 появляется импульс переполнения, а на выходе инвертора 40 - нулевой сигнал. Сигнал сброса триггеров Ю с выхода 31 блока 3 вырабатывается при одновременном присутствии единиц на всех входах элемента И 39, т.е. после Ькончания определения связности оставш гося подграфа, регенерации информации о топологии в блоках 1 и признака, что не все вершины исходного графа связаны. Если все вершины исходного графа связаны, на выходе инвертора 4О имеется нулевой сигаал, который запрещает срабатывание элемента 39 И. После конца определения связности, остаииегося подграфа импульс переполнения с выхода счетчика 41 поступает на элемент 38 И. Сигнал вьссойаэлемента 38 И через элемент 37 задержки поступает на выход 32 блока 3 как сигнал с броса триггеров 11 в блоках 1. Введение новых элементов и связей позволило расширить класс решаемых задач и дало возможность параллельной обработки информации одновременно во всех моделях ветвей, т.е. увеличило быстродействие устройства. Формула изобре 1. Устройство для моделирования графов, содержащее блок управления генератора, два выхода которого подключены соответственно к первому и второму шсодам блока формирования топологии, первый и второй выходы которого соединены соот ветственно с первыми и вторыми входами блоков моделей ветвей, каждый из которых содержит два счетчика адреса, входы которых подключены к первому входу блока модели ветви, счетчик временного интервала, выход которого соединен с единичными входами первого и второго триггеров, элемент ИЛИ и элементы И, первый вход первого элемента И подключен ко второму входу блока модели ветви, второй вход первого элемента И соединен с нулевым ш 1ходом первого триггера и с

первьгм входом второго элемента И, которого подключен к первому выходу блока модели ветви, единичный выход первого триггера соединен со вторым выходом блока модели ветви, единичный вьг- 5 ход второго триггера каждого блока модели ветви соединен с соответствующим выходом из первой группы входов блока и формирования топологии, отличающееся тем, что, с целью повышения ю быстродействия и расширения класса решаемых задач, в него введены формирователь импульсов и элемент ИЛИ-НЕ, входы которого соединены с первыми выходами блоков моделей ветвей, выход элемента 15 ИЛИ-НЕ подключен к первому входу блока управления, первый ныход которого соецинен с первым входом третьего элеменЬ та И каждого блока модели ветви, выход третьего элемента И соединен с нулевым 20 входом первого триггера, второй вход третьего элемента И подключен ко второму входу второго элемента И и к единичному выходу второго триггера, счеПный вход которого соединен с выходом 25 первого элемента И, третий йход которого подключен к выходу элемента ИЛИ и к первому входу четвертого элемента И, второй вход которого соединен с выходом второго элемента, Ызгход 4eTBepTt3ro эле- 30 мента И каждого блоки модели ветви соединен с соответствующим входсы из второй группы входов блока формирования топологии, третий выход которого подключен ко второму входу блока управления и k управляющему входу форм1фования ш.пульсов, выход которого соединен с входами счетчиков временных интервалов, выходы счетчиков адреса подключены к входам соответствующих элементов ИЛИ, первый и второй выход блока формирования топологии соединен соответственно с третьим и четвертым входами блока управления, второй выход которого подключен к нулевым входам вторых триггеров.

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что- блок управления содержит два счетчика, элемент задержки, инвертор и два элемента И, первые и вторые входы которых соединены с первым входом блока и выходом первого счетчика соответственно, второЁ. вход бп(жа подключен к управляющему входу счетчика, выход которого через Нйвертор соединен с третьим входом одного нэ элементов И, выход которого подключен к первому выходу блока, выход другого элемента И соединен со. вторым выходстм блока, третий и четвертый ЕКОДЬГ блока подключены к счетным входам первого и второго счетчиков соответственно.

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

1.Авторское свидетельство СССР N9 305484, кл. G 06 G 7/48, 1970.

2.Авторское свидетельство СССР №422002, кл. G 06 G 7/48, 1972 (прототип).

35