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

О П И С А Н И Е732898ИЗОБРЕТЕН ИЯ Союз Советски кСоциалистическикРеспублик Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ(23) Приоритет аа делам изобретений н открытий(53) УДК 681.3. ,001.57 (088,8) Опубликовано 05,05,80, Бюллетень 17 Дата опубликования описания 08,05,80(72) Авторы изобретения А. Г. Додонов, О. Н. Голованова, Я, Я, Фенюк и В, В, Хаджинов Институт электродинамики АН Украинской ССР(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ1Изобретение относится к вычнслительной технике и может быть использованодля решения ряда задач на графах и сетях.Известно устройство для моделирования графов Ц, содержащее модели ветвей графа, соединенные согласно топологии графа, Каждая модель ветви содержитсчетчик временного интервала, два триггера, элементы И и элементы ИЛИ. Устройство позволяет решать ряд задач нанаправленных графах,Недостатком устройств является малое быстродействие за счет ручной ком-.мутации графа.Наиболее близким по технической сущ 15ности к изобретению является устройстводля моделированйя сетевого графа 2,содержащее блок управления, генератор,два выхода которого подключены соответственно к первому и второму входам блока ормирования топологии, первый и второй выходы которого соединены соотвевственно с первыми и вторыми входамиблоков моделей ветвей, каждый из кото 2рых содержит два счетчика адреса, входыкоторых подключены к первому входу блока модели ветви, счетчик временного интервала, выход которого соединен с единичными входами первого и второго триггеров, элементы ИЛИ и элемент И. Первый вход первого элемента И подключенко второму входу блока модели ветви,второй вход - к нулевому входу первого триггера и к первому входу второго элемента И, выход которого подключен к первому выходу блока модели ветви, Единичный выход первого триггера соединен совторым выходом блока модели ветви, единичный выход второго триггера каждогоблока модели ветви - с соответствующимвходом из первой группы входов блокаформирования топологии,Зто устройство позволяет автоматически формировать топологию и предназначено для нахождения критических путей вориентированном графе, Однако имеютсязадачи, математической моделью в которых является неориентированные графы,3 7328например задачи об оптимальном деревесвязи, оптимальной связывающей сети,Кроме того, это устройство работает врежиме последовательного просмотра иформирования конфигурации путей, не мо 5жет реализовать алгоритмы одновременного, параллельного определения путей идеревьев, что увеличивает время решениязадачи,Цель изобретения - повышение быстро-, действия и расширение класса решаемых1задач.Эта цель достигается тем, что в предложенное устройство введены формирователь импульсов и элемент ИЛИ-НЕ, входы т 5которого соединены с первыми выходамиблоков моделей ветвей. Выход элементаИЛИ-НЕ подклточен к первому входу блокауправления, первый выход которого соединен с первым входсм третьего элемента щФИ каждого блока модели ветви, Выходтретьего элемента И соединен с нулевымвходом первого триггера, второй вход -со вторым входом второго элемента И иединичным выходом второго триггера, счет ный вход которого соединен с выходомпервого элемента И, третий вход которого подкпючен к выходу элемента ИЛИ ик первому входу четвертого элемента И,второй вход которого соединен с выходом 50второго элемента И, Выход четвертогоэлемента И каждого блока модели ветвисоединен с соответствующим входом извторой группы входов блока формированиятопологии, третий выход которого подклю- учен ко второму входу блока управленияи к управляющему входу формирователяимпульсов, выход которого соединен свходами счетчиков временных интерваловВыходы счетчиков адреса подклточены ко 40входам соответствующих элементов ИЛИ.Первый и второй выходы блока формирования топологиисоединены соответственно с третьим и четвертым входами блокауправления, второй выход которого подключен к нулевым входам вторых триггеров+Блок управления содержит два счетчика, элемент задержки, инвертор и два элемента И, первые и вторые входы которых 0соединены с первым входом блока. и выходом первого счетчика соответственно.Второй вход блока подключен к управляющему входу второго счетчика, выход которого через инвертор соединен с третьим 55входом одного из элементов И, выход которого подключен к первому выходу блока. Выход другого элемента И соединен 98 4со вторым игходом блока, Третий и четвертый входы блока подключены к счетнымвходам первого и второго счетчиков соответственно.На фиг, 1 представлена структурнаясхема устройства; на фиг. 2 - функциональная схема блока управления,Устройство содержит блок 1 моделейветвей, блок 2 формирования топологии,блок З,управления, генератор 4, элемент,5 ИЛИ-НЕ и формирователь 6 импульсов.Блок 1 модели ветви состоит иэ счет-чика 7 временного интервала счетчиков 8,9 адреса, первого и второго триггеров10, 11, элемента 12 ИЛИ, элементов И13-16, входных и выходных полюсов17-24 (полюса 17 и 18 являются первыми вторым входом, а полюса 19 и 20 -первым и вторым выходами блока соответственно) .Блок 2 имеет первый 26, второй 27и третий 28 выходы, первую 29 и вторую30 группы входов.Блок 3 управления имеет два выхода31 и 32 и четыре входа 33-36, и состоит из элемента задержки 37, двух элементов И 38 и 39, инвертора 40 и двухсчетчиков 41 и 42,Устройство работает следующим образом.В исходном состоянии триггеры 10,11 находятся в нулевом состоянии, Всчетчике 7 записано количество импульсов, пропорциональное длительностям соответствующих им ветвей исследуемогографа, В счетчиках 8 и 9 заданы в обратном коде адреса вершин графа, инцидентных, согласно топологии исследуемого графа, данной ветви.ГВ блоках 1, не приниматощих участиев моделировании графа, счетчики 8 и 9находятся в нулевом состоянии.фаза 1 - поиск очередной сформированной модели ветви, которая может входитьв рещение задачи. После подачи сигналовпуска, формирователь 6 импульсов подаетимпульсы на входы счетчиков 7 временного интервала, Первым появляется сигналпереключения в том счетчике 7, в который была записана самая большая длительность. По этому сигналу в этом блоке 1 устанавливаются в единичное состояние триггеры 10 и 11, и сигнал с единичного выхода триггера 11 поступаетна один из входов первой группы в блоке 2. По этому сигналу блок 2 выдаетна управляющий вход формирователя 6 сигнал, запрещающий подачу импульсов наРабота устройства в режиме по фазе 2 описана выше.В режиме по фазе 2 подсчитываются сигналы свяэаности, поступившие на входы 30 блока 2. Сигналы свяэаности, собирающиеся по схеме ИЛИ в блоке 2 с выхода 27 поступают на вход 36 блока 3 управления, который подсчитывает их. Конец определения связности оставшегося подграфа определяется элементом 5 ИЛИ-НЕ, Если хотя бы в одной модели ветви оставшегося подграфа есть сигнал связности, т.е. триггер 10 в соответствующем блоке 1 находится в нулевом состоянии, а триггер 11 - в единичном состоянии, нулевой сигнал с выхода элемента 5 дает запрет в режиме работы устройства по фазе 2 в блок 3 управления, Как только окончится процесс определения связности оставшегося попграфа в режиме по фазе 2, триггеры 12 всех моделей ветвей находятся в нулевом состоянии, и на всех жопах элемента 5 присутствуют нулевые сигналы. При этом с выхопа элемента 5 выдается на вход 33 блока 3 разрешающий единичный сигнал. 5 (328счетчики 7, Признаком удаления ветви иэграфа служит единичное состояние выхода20 в соответствующем блоке модели ветви,фаза 2 - определение связанности всехвершин графа. Если оставшиеся вершиныграфа связаны между собой, то даннаяветвь окончательно удаляется иэ графа,в противном случае она возвращается вграф. оОдновременно с прекращением формирования длительностей ветвей блок 2 формирования топологии с выхода 26 начинает выдачу импульсов на входы 17 всехблоков. Эти сигналы поступают на входы 15счетчиков 8 и 9 адреса для автоматического формирования топологии, Первым по.является сигнал на выходе эадатчиков 8или 9 адресов, в которых записан первначальный адрес В 1, потом на выходах 20задатчиков адресов, в которых записанследующий 1 адрес В 2, и т.д. Для проверки связности ветвей, оставшихся в графе,т.е. в тех моделях 1 ветви, в которыхтриггер 10 находится в нулевом состоянии, по первоначальному адресу В 1 блок2 формирования топологии выдает единичный логический уровень на входы 18 блоков 1. В тех блоках 1, в которыхзапи-.сан адрес В 1 и триггер 10 находится внулевом состоянии единичный логическийуровень с выхода элемента 13 И устанавливает в единичное состояние триггер 11,Теперь на входах элемента 14 И имеютсясигналы логической единицы, и единичный З 5сигнал с выхода этого элемента подаетсяна второй вход элемента 16 И. При поступлении сигнала второго адреса с выходов счетчиков адреса 8 и 9 через элемент 12 ИЛИ на первый вход элемента16 И единица с его выхода поступает наодин из аходов второй группы блока 2,Число входов в первой и второй группахжодов соответствует числу блоков 1,При наличии хотя бы одного единичного сигнала на входах 30 блок 2 формирования топологии выдает на выход 27 сигнал, который поступает на входы 18 блоков 1. В моделях ветвей, присутствующихв графе, и в которых есть сигналы второ Ого адреса, присутствуют единичные логические уровни на всех входах элемента13 И, Сигналы епиницы с выходов элементов 13 И поступают на счетные входы триггеров 11,Те триггеры 11, которые в этот Момент времени нахопипись в единичном сэстоянии, перебрасываются в нулевое состо 98 6янне, в триггеры 11, находившиеся в нулевом состоянии, переходят в единичное состояние, и таким образом сигналы связности передаются следующим моделям ветвей по следующим адресам вершин графа.Чередуя режимы работы данного уст- ройства по фазам 1 и 2 находят, например, минимальное связывающее дерево следующим образом, В режиме по фазе 1 импульсы с выхода формирователя поступают одновременно на входы счетчиков 7 всех блоков 1. Модели ветвей формируют свои длительности по порядку уменьшения их величин, начиная с самой большей.Как только какой-нибудь блок 1 сформировал свою длительность, два триггера 10 и 11 устанавливаются в единичное состояние.Единица с единичного выхода триггера 11 сформированной модели ветви поступает на один из входов 29 блока 2, При наличии хотя бы одной единицы на входах 29 блок 2 с выхода 28 выдает запрет формирователю 6 на выдачу импульсов формирования временных интервалов, и одновременно начинает выдавать импульсы с выхода 26 на выходы счетчиков 8 и 9 адресов всех моделей ветвей, т.е. производится переключение работы устройства в режиме по фазе 2 для определения связности графа без сформированной и отключенной по фазе 1 ветви,98 8навливается в нулевое состояние, Счетчик 42 предназначен для подсчета количества связных вершин в графе, Перед началом работы устройства для моделирс- вания графов в режиме по фазе 2 счетчик 42 сбрасывается по входу 34 в исходное состояние й -Ч (где- емкость, счетчика, 7 - число вершин в графе решаемой задачи), Через Ч импульсов, поступающих на вход 36 блока 3, на выходе счетчика .42 появляется импульс переполнения, а на выходе инвертора 40 - нулевой сигнал, Сигнал сброса триггеров 10 с выхода 31 блока 3 вырабатывается при одновременном присутствии единиц на всех входах элемента И 39, т,е, после Ькончания определения связности оставшегося подграфа, регенерации информации о топологии в блоках 1 и признака, что не все вершины исходного графа связаны, Если все вершины исходного графа связаны, на выходе инвертора 40 имеется ну левой сигнал, который запрещает срабатывание алемента 39 И. После конца определения связности. оставшегося подграфа импульс переполнения с выхода счетчика 41 поступает на алемент 38 И. Сигнал выходавлемента 38 И через элемент 37 задержки поступает на выход 32 блока 3каксигналсброса триггеров 11 в блоках 1.Введение новых алементов и связей позволило расширить класс решаемых задач и дало возможность параллельной обработки информации одновременно во всех моделях ветвей, т.е. увеличило быстродействие устройства. 7 7328По этому сигналу, определяющему конец определении связности вершин оставшегоподграфа, если не будут достигнуты все вершины исходного графа, блок 3 с выхода 3 1 выдаетсигнал единицы на входы 21 всех блоков 1, В блоке 1 модели ветви, исключенной иэ графа в предыдущем режиме по фазе 1, триггер 11 дает разрешающий потенциал на вход элемента 15 И, и триггер 10 устанавливается в нулевое состоя ние, так как эта ветвь входит в решениезадачи, Если исключение ветви в предыдущем режиме по фазе 1 не влияет на связанность вершин исходного графа, блок 3не выдает сигнала на входы 21 блоков 1,и исключенная ветвь не возвращается вграф, В любом случае после прихода сигнала единицы с выхода элемента 5 навход 33 блока 3 через некоторое времязадержки, необходимое для анализа связности вершин, блок 3 с выхода 32 выдаетсигнал на входы 24 всех блоков 1, покоторому производится сброс триггеров11 и убираются все сигналы единицы навходах 29 блока 2, т.е. устройство для.моделирования графов снова переключается в режим по фазе 1 и т.д,Устройство останавливается пссле того, как произойдет формирование временных интервалов и пробное исключение всехветвей графа, Зто происходит автоматически за один просчет рвгенврационногосчетчика в формирователе, работающемпараллельно со всеми счетчиками 7. Наэтом решение задачи заканчивается,Триг- З 5, геры 10.в блоках моделей ветвей принадлежащих минимальному связывающемудереву, находятся в единичном состоянии.Единичные сигналы с выходов 20 моде 40лей 1 ветвей могут подаваться на устройство или табло индикации. При атомисходная информация о длительностях веъвей, записанная в счетчиках 7, восстанавливается. Величина связывающего дереваможет быть определена поочередным суьмированием длительностей ветвей емупринадлежащих,Максимальное связывающее дерево находят аналогично, с той лишь разницей,50что исходная информация в длительностиветвей графа записывается в обратномкоде.Рассмотрим блок 3 управления. Счетчик 41 предназначен для регенерации ин 55формации об адресах в моделях ветвей,Емкостьсчетчика 4.1 равна емкости счетчиков 8 и 9 адреса в блоках 1. Передначалом решения задачи счетчик 41 устаформула изобретения 1, Устройство для моделирования графов, содержащее блок управлении генератора два выхода которого подключены соответственно к первому и второму входам блока формирования топологии, первый ивторой выходы которого соединены соответственно с первыми и вторыми входами блоков моделей ветвей, каждый из которых содержит два счетчика адреса входы которых подключены к первому входу блока модели ветви, счетчик временного интервала, выход которого соединен с единичными входами первого и второго триггеров, элемент ИЛИ и элементы И, первый вход первого элемента И подключен ко второму входу блока модели ветви, второй вход первого элемента И соединен с нулевым выходом первого триггера и с9 732 первым входом второго элемента И, вь- , ход которого подключен к первому выходу блока модели ветви, единичный выход первого триггера соединен со вторым выходом блока модели ветви, единичный выход второго триггера каждого блока моде ли ветви соединен с соотвежтвующим выходом из первой группы входов блока и формирования топологии, о т л и ч а ющ е е с я тем, что, с целью повышения 1 о быстродействия и расширения класса решаемых задач, в него введены формирователь импульсов и элемент ИЛИ-НЕ, входы которого соединены с первыми выходами блоков моделей ветвей, выход элемента 15 ИЛИ-НЕ подключен к первому входу блока управления, первый выход которог 6 соединен с первым входом третьего элемы 4- та И каждого блока модели ветви, выход третьего элемента И соединен с нулевым 20 входом первого триггера, второй вход третьего элемента И подключен ко второму входу второго элемента И и к единичному выходу второго триггера, счетный вход которого соединен с выходом 25 первого элемента И, третий вход которого подключен к выходу элемента ИЛИ и к первому входу четвертого элемента И, второй вход которого соединен с выходом. второго элемента, выход четвертого эле О мента И каждого блока модели ветви соединен с соответствующим входом из второй группы входов блока формирования топологии, третий выход которого подклю 35 898 10чен ко второму входу блока управления ис управляющему входу формирования импульсов, выход которого соединен с входами счетчиков временных интервалов, выходы счетчиков адреса подключены к входам соответствующихэлементов ИЛИ, первый и второй выход блока формированиятопологии соединен соответственно с третьим и четвертым входами блока управления, второй выход которого подкщочен кнулевым входам вторых триггеров.2, Устройствопоп, 1, отлич а -ю щ е е с я тем, что-, блок управлениясодержит два счетчика, элемент задержки,инвертор и два элемента И, первые и вторые входы которых соединены. с первымвходом блока и выходом первого счетчика соответственно, второй вход блока подключен к управляющему входу вжрогосчетчика, выход которого через инверторсоединен с третьим входом одного из элементов И, выход которого подключен кпервому выходу блока, выход другого элемента И соединен со. вторым выходомблока, третий и четвертый входы блокаподключены к счетным входам первогои второго счетчиков соответственно.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР% 305484, кл. 606 б 7/48, 1970.2. Авторское свидетельство СССРЪ 422002, кл. 606 С 7/48, 1972 (прототип).732898 Фиг г. Я Л, Утех каз 1739/39 Тираж 751 ЦНИИПИ Государственного комитета по делам изобретений и открыти 113035, Москва, Ж, Раушская наПодписноеСР ППП фПате РедактоЗа Составитель А. ЯицковТехред О. Андрейко Корректор И. Мус Ужгород, ул.Проектна