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

 

!

Sa y

ИЗОБРЕТЕНИЯ

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

Социалистическик республик (>i) 76391 1

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт, свид-ву(22) Заявлено 13. 09. 78 (21)2665194/18-24 с присоединением заявки Ио (23) Приоритет—

Опубликовано 150980 Бюллетень 34

Дата опубликования описания 180980 (51)М. Кл.з

G 06 С 7/122

Государственный комитет

СССР по делам изобретений и открытий (53) УДК681.333. (088.8) (72) Авторы изобретения

Э.А.Баканович, В.И.Новиков, С.Ф.Костюк, В.К.Мельников и С.П.Белов

Минский радиотехнический институт (71) Заявитель (54 ) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ

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

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

Недостатком этого устройства является то, что число дуг и узлов исследуемой сети или исследуемого графа не может превышать числа соответственно моделей узлон и дуг.

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

В этом устройстве число ветвей исследуемого сетевого графика не может превышать количество моделей ветви в устройстве.

Цель изобретения — расширение класса решаемых задач за счет разбиения графа на подграфы.

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

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

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

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

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

3 управления, генератор импульсов 4, счетчик (импульсон) 5, блок памяти 6, статистический анализатор 7, элемент

И 8.

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

Модель 10 связности содержит: регистр 11, элементы ИЛИ 12, элемент 45

И 13.

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

Блок 3 управления вырабатывает на выходе сигнал, по которому устанав- $p ливается в нуль счетчик 5, приводятся в исходное состояние генераторы

9.. Блок 1 моделей вершин и блок 2 формирования топологии настраиваются блоком 3 на заданные вероятностные харак- 55 теристики весов вершин и на требуемую топологию графа.

Для этого на выходах блока 3 вырабатываются сигналы, настраивающие генераторы 9 на воспроизведение случайных временных интервалов с задан- ® ными нероятщэстными характеристиками и вырабатынаются сигналы, по которым в регистрах 11 моделей 10 связности устанавливаются коды, которые разрешают появление сигнала на выходе эле ментов И 13 лишь при определенной комбинации сигналов на входах элементов ИЛИ 12. Так, например, если необходимо появление сигнала .на выходе модели 10 связности с номером

j при появлении сигналов на выходах генераторов 9 с номерами k,1,m (jk kk)4m), то в регистр 11 будет записан двоичный код с единицами во всех разрядах, кроме k-го I-ro u m-го, значение которых равно нулю. Тем самым задается требуемая топология графа. Моделирование одной реализации начинается по сигналам с блока 3, которые поступают одновременно на все модели 10 связности и тем саьым разрешают их срабатывание. Одновременно запускается генератор 4 импульсов, сигналы с выхода которого поступают на вход счетчика 5, являющегося таймером модели.

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

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

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

В-третьих, сигнал с выхода генератора 9 поступает на элемент И 8, где контролируется момент окончания выполнения всех вершин графа.

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

Блок 3 по сигналу с выхода элемента

И 8 останавливает работу моделей 10 и устанавливает н исходное состояние таймер и генераторы 9. Анализагор 7 обрабатывает в соответствии с требуемой программой исследования содержимое блока 6 памяти.

Таким образом, устройство работает в случае, когда число вершин графа меньше или равно числу генераторов 9..

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

763911

Сначало, аналогично предыдущему, моделируется первый граф, затем блок

3 производит перенастройку генераторов 9 и моделей 10 в соответствии с характеристиками второго графа. Для учета связности первого и второго графов блок 3 считывает из анализатора 7 коды времен окончания выполнения всех вершин первого графа, связанных согласно топологии с вершинами второго графа. Блок 3 для каждой

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

Блок 3 вырабатывает сигнал, по которому устанавливаются в исходное состояние таймер и генераторы 9. 3апускается генератор 4 и начинается работа таймера.

В процессе счета таймера блок 3 сравнивает код в счетчике 5 с полученными кодами начала работ вершин. второго графа. При равенстве кодов для некоторой j-й вершины второго графа блок 3 вырабатывает сигнал, по которому разрешается срабатывание j-й модели 10 связности и т.д.

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

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

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

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

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

35 входы которых соединены с соответствующими входами блока формирования топологии, выходы элементов ИЛИ соединены с информационными входами элемента И, управляющий вход которого подключен к соответстнукщему

40 управляющему входу блока формирования топологии, выход элемента И соединен с соответствующим ныходом блока формирования топологии.

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

1.Авторское свидетельство СССР

9 407345, кл. 0 06 G 7/48, 1971.

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

М 422002, кл. G 06 G 7/48, 1972

50 (прототип).

763911 аказ б285/43 тираж 751 подписиое

„ИИпд Государственного комитета СССР по делам иэобретений и открытий

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

Филиал ППП Патент, г.ужгород,ул.Проектная, Составитель А.Колчин

Редактор Т.Орловская Техред Т.Иаточка Корректор И.Демчик: