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

 

Изобретение относится к вычислительной технике и предназначено для решения задачи определения - медиан неориентированных графов, являющихся математическими моделями широкого класса прикладных оптимизационных задач размещения различного рода баз снабжения, пунктов обслуживания и коммутационных узлов. Цель изобретения - расширение функциональных возможностей за счет определения рмедиан графа (где р Н, Н - число вершин графа). Поставленная цель достигается тем. что устройство содержит блок синхронизации 1, блок определения кратчайшего пути 2, блок задания матрицы смежности 3, блок регистрации времени исполнения вершиим 4, блок сравнения 6. блок памяти 7 и сумматор 5.1 ил.

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

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

РЕСПУБЛИК (я)з G 06 F 15/20

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

1 (21) 4817886/24 (22) 24.04,90 (46) 23.05.93. Бюл. М 19 (72) А, М. Борисов, В,А. Буслаев, А.Б.Шербань и Н.И.Ячкула (56) Авторское свидетельство СССР

М 1348850, кл. G 06 F 15/20, 1986.

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

М 1559394, кл. 6 06 F 15/20, 1991. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ГРАФОВ (57) Изобретение относится к вычислительной технике и предназначено для решения задачи определения — медиан неориентированных графов, являющихся математиче„„Я „„1817104A1 скими моделями широкого класса прикладных оптимизационных задач размещения различного рода баэ снабжения, пунктов об- . служиванию и коммутационных узлов, Цель изобретению — расширение функциомальных воэможностей за счет определения рмедиан графа (где р < Н, Н вЂ” число вершин графа). Ооставленнаю цель достигается тем, что устройство содержит блок симхронизации 1, блок определения кратчайшего пути

2, блок задания матрицы смежности 3, блок регистрации времени исполнения вершиин

4, блок сравмения 6, блок памяти 7 N сумматор 5.1 ил.

1817104

10

30

40

50

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

Цель изобретения — расширение функциональных воэможностей устройства за счет определения р-медиан графа (где р > Н).

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

Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок

4 регистрации времени исполнения .вершин, сумматор 5, блок 6 сравнения, блок 7 памяти и разделительные диоды 8;, i = 1, и (и — число вершин графа), Блок 1 синхронизации обеспечивает формирование сигналов уровня логической единицы на элементы и блоки устройства в соответствии с алгоритмом определения рмедиан графа. Основу блока может составлять генератор сочетаний из и по р на базе известных устройств для перебора сочетаний, Цифровые обозначения на схеме имеют: вход пуска устройства 9, вход задания числа р10, тактовый вход 11, управляющие выходы 12ь i 1, и, 13, 14.

Блок 2 определения кратчайшего пути регистрирует моменты исполнения вершин графа и формирует сигнал признака исполнения всех вершин графа. На схеме обозначены: 15 — вход начальной установки, 16;,! =

=1, и — информационные входы; 17 — выход признака исполнения всех вершин графа, Блок 3 задания матрицы смежности предназначен для задания топологии и весов дуг исследуемого графа, устанавливаемых по входам 18, lj = 1, п, а также для моделирования исполнения вершин графа и сигнализации об этом через выходы 19i, i =

=1, и.

Блок 4 регистрации времени исполнения вершин графа предназначен для записи сигналов, пропорциональных минимальному времени достижения i-той вершины графа (i =

=1, и) из всех р вершин, соответствующих данному шагу решения, и подачи этих сигналов на входы сумматора, Блок содержит интегратор 20п элементов памяти 21, выходы признака записи 22ь вход 23 подготовки и вход 24 пуска блока, информационные выходы блока 25 (i =- 1, n).

Блок 5 сумматор предназначен для определения результирующего сигнала, пропорционального сумме времени достижения всех вершин графа из заданных на шаге решения вершин. Информационные входы блока 26ь1= 1, и информационный выход 27, Блок 6 предназначен для сравнения, по сигналу поступающему на управляющий вход 28, сигнала на информационном входе

29 с сигналом, хранящемся в памяти блока, Если сигнал, поступающий на информационный вход меньше, то появляется импульсный сигнал на выходе 30 блока, а значение информационного сигнала записывается в память блока вместо сигнала, хранящегося там ранее, Вход 31 начальной установки, поступление импульса на него обеспечивает запись в память блока предельно большоro сигнала, Блок 7 предназначен для фиксирования по сигналу на управляющем входе 32 комбинации сигналов, поступающих на информационные входы 33l, i = 1, и.

Устройство работает следующим образом. Перед началом работы подачей соответствующих сигналов по входам 18, Ц = 1, и блока 3 задается топология и веса дуг исследуемого графа, по входу 10 блока 1 Задается число р (и и подачей сигнала на вход

31 устанавливается в исходное состояние блок 6.

Работа устройства начинается подачей сигнала на вход пуска 9. При этом появляется сигнал уровня логической единицы на выходе 14, откуда он поступает на вход 15 блока 2 и осуществляет его начальную установку, а через вход 23 блока 4 на входьi возврата в исходное нулевое состояние преобразователя 20 и элементов памяти 21;, i = 1, и.

По завершению этих операций сигнал с выхода 14 снимается и появляется сигнал на управляющем выходе 13 и р выходах группы выходов 12l, i = 1, и в соответствии с первым сочетанием иэ и по р, сформированным в блоке 1. Сигнал с выхода 13 поступает через вход 24 на вход запуска времяинтегрирующего преобразователя 20, который при этом начинает генерировать линейно-возрастающий сигнал (напряжение или код), поступающий на информационные входы элементов памяти 21ь I — 1,n. Сигналы уровня логической единицы с р выходов 12l, i =

=1, п поступают на информационные входы

33l, i 1, и блока 7, а, через соответствующие разделительные диоды 8ь i = 1, и на объединенные полюса 16l, 19, 22.,! = 1, и блоков 2, 3, 4 соответственно. При этом в блоке 2 моделируется достижение тех р вершин, которым соответствуют единичные сигналы на выходах 12, i = 1, и. В блоке 3 начинается моделирование достижения остальных и - р вершин графа. В блоке 4 по сигналам с соответствующих р входов 22I осуществится за1817104

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

19 этого блока, откуда они поступают на входы 16 блока 2, где фиксируется достижения соответствующей вершины, и на входы

22; блока 4, С входов 22 сигналы поступают на входы элементов памяти 21 и в них фиксируется сигнал пропорциональный минимальному расстоянию от заданных на шаге решения р вершин до данной i-той.

Через время достаточное для моделирования достижения всех вершин графа, блок

2 формирует импульсный сигнал, поступающий на управляющий вход 28 блока 6 и тактовый вход 11 блока 1. В блоке 6 осуществляется сравнение сигнала, поступающего с выхода сумматора и пропорционального сумме кратчайших расстояний от заданных на шаге решения р вершин до остальных n - р вершин графа, со значением, хранящимся в памяти блока 6. Так как в исходном состоянии там хранится предельно большое число, что на выходе 30 блока 6 появляется импульсный сигнал, поступающий на вход 32 блока

7, в котором при этом фиксируется заданное на первом шаге решения сочетание из и по р. Через время достаточное для срабатывания блоков 6 и 7 снимаются сигналы уровня логической единицы с р выходов 12; и с выхода 13. Вновь формируется сигнал уровня логической единицы на выходе 14 и далее работа устройства повторяется аналогично выше рассмотренному первому шагу до полного перебора всех сочетаний из и по р.

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

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

Устройство для анализа графов, содержащее блок синхронизации, блок задания матрицы смежности, блок определения кратчайшего расстояния и блок памяти, причем а-й выход группы (где а = 1, ..., Н, Н вЂ” число вершин исследуемого графа) блока синхронизации соединен с а-м выходом блока задания матрицы смежности с помощью элемента МОНТАЖНОЕ ИЛИ и подключен к а-му, информационным входам блока определения кратчайшего пути и бло5

50 ка памяти, первый выход блока синхронизации подключен к входу установки в исходное состояние блока определения кратчайшего пути, выход которого подключен к первому входу режима блока синхронизации, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения р медиан графа (гред р < Н), оно содержит сумматор, блок сравнения и блок регистрации времени исполнения вершин, причем а-й выход группы блока синхронизации соединен с ам выходом блока задания матрицы смежности с помощью элемента МОНТАЖНОЕ

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

Н элементов памяти, при этом в блоке регистрации времени исполнения вершин управляющий вход подключен к входу запуска интегратора, выход которого подключен к информационным входам всех элементов памяти, выходы которых подключены соответственно к выходам блока регистрации времени исполнения вершин, вход установки в исходное состояние которого подключен к входу установки в "0" всех элементов памяти и к входу установки в исходное состояние интегратора, входы с первого по

Н-й признака записи блока регистрации времени исполнения вершин подключены соответственно к входам записи-считывания элементов памяти с первого по Н-й.