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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

{ii>995094, (61}Дополнительное к авт. свид-ву— (22) Заявлено 04. 08. 81 (21)3331336/18 24

f$g)+ g 3

G 06 F 15/20 с присоединением заявки ¹â€”

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

СССР по делам изобретений и открытий (?3) Приоритет—

Опубликовано 0702.83. Бюллетень ¹5

153) УДК 681 333 (088. 8) Дата опубликования описания.07.02.83 (72) Автор изобретения

В.A.Òèòîâ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ

ПУТЕЙ В ГРАФАХ

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

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

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

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

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

20 иэ которых связаны с занесени исходной информации о топологии и весах дуг моделируемого граФа и подсчета импульсов в счетчиках весов дуг, а третий этап — со

25 сравнением результатов двух подсчетов в схемах сравнения.

Наиболее близким по технической сущности к предлагаемому является устройство для определения максимальЗО йых путей в графах, в состав которо995094 го входят цепочки из последовательно соединенных первого триггера и первого элемента И по числу и строк и и столбцов матричной модели графа, и элементов ИЛИ-HE n элементов ИЛИ, и вторых элементов И, счетчиков весов вершин, п третьих элементов И, регистрирующих счетчиков, четвертых элементов И, вторых триггеров, и пятых элементов И, блок выбора максимального кода, дешифратор, дополнительный счетчик, первый элемент И, второй элемент И, элемент ,ИЛИ, генератор тактовых импульсов, выход которого подсоединен к первому .входу шестого элемента И и первому входу седьмого элемента И, выход которого подсоединен к первым входам вторых элементов И и первым входам третьих элементов И, выходы первых элементов И одноименной 1-й (1 = Z и ) строки матричной модели N графа подсоединены к входам i --го элемента ИЛИ-HE выход которого подсоединен к второму входу i-го второ"

ro элемента И, выход которого подсоединен к входу1-ro счетчика ве- Я са вершины, выход которого подсоединен к вторым входам первых элементов И одноименного столбца матричной модели графа, к первому входу i-го третьего элемента И и к 1-му входу у) элемента ИЛИ, выход которого подсоединен к второму входу второго элемента И, второй вход i-ro третьего элемента И подсоединен к выходу i-го элемента ИЛИ, а выход подсоединен через регистрирующий счетчик к первому входу группы i-x четвертых элементов И, выход которой подсоединен к 1-му входу блока выбора максимального кода, -й выход которого подсоединен к входу -ro второго триггера, выход которого подсоединен к первому. входу i-ão пятого элемента

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

И Г21, Цель изобретения — повышение быстродействия устройства.

59

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

И, причем выход триггера соединен с первым входом первого элемента И, а также группу из и элементов ИЛИ-HE первую, вторую, третью и четвертую Щ ,группы,из и элементов И, группу из .п счетчиков веса вершин, группу из и регистрирующих счетчиков„ блок выбора кода максимального числа, группу из 11 регистрирующих триггеров,

ИЛИ, дешифратор, первый и второй элементы И, счетчик и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, вйход i --ro элемента ИЛИ-НЕ (i= I,ï, n — размерность матричной модели графа) соединен с вторым входом i -го элемента И первой группы,.выход которого подключен к входу 1 -ro счетчика веса вершины, выход которого соединен с вторым входом i -ro элемента И второй групПы, вы<од последнего через -й регистрирующий счетчик подключен к первому входу элемента И третьей группы, выход которого соединен с 1-м входом блока выбора кода максимального числа, 1-й выход которого подключен к входу .1-го регистрирующего триггера, выход которого соединен с первым входом

i-го элемента И четвертой группы, выход которого подключен к вторым входам первых элементов И узлов 1-й строки матричной модели графа, выход первого элемента И i-го узла матричной модели графа соединен с i-м вхо- дом 1 -ro элемента ИЛИ группы, выход которого подключен к второму входу

i-го элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И, выход второго элемента И через счетчик подключен к входу дешифратора, 1-й выход которого соединен с вторым входом i --ro элемента И четвертой группы, введены элемент НЕ, а в каждый узел матричной модели графа — второй элемент И выход второго элемента И узла i-u строки подключен к i-му входу i--го элемента ИЛИ-HE группы, выход i-ro счетчика веса вершин группы соединен с первыми входами вторых элементов И узлов 1-го столбца матричной модели графа и с 1-м входом элемента ИЛИ,выход которого через элемент

HE подключен к втброму входу второго элемента И, выход триггера i --ro узла матричной модели графа соединен с вторым входом второго элемента И узла матричной модели графа.

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

Устройство содержит матричную модель 1 графа, триггеры 2 по числу строк и столбцов матричной модели графа (n x и ), первый и второй элементы И 3 и 4, по числу и столбцов матричной модели графа группу элементов ИЛИ-НЕ 5, группу из и элементов

ИЛИ 6, первую группу из и элементов

И 7, группу из. и счетчиков 8 весов вершины, вторую группу из и элементов И 9, группу из и ре истри.

995094

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

На первом этапе с появлением пускового сигнала на входе 22 элемента

И 16 импульсы с выхода генератора 17 поступают на входы элементов И 7 и 9.

При этом импульсы проходят на все счетчики 10, так как в исходном состоянии вторые входи элементов И 9 подключены к выходам одноименных счетчиков 8, на которых появляетсясигнал переполнения. Кроме того, счетные импульсы поступают через элементы И 7 на входы тех счетчиков S, для которых триггеры 2 одноименной строки матрицы находятся s нулевом :

- рующих счетчиков 10, третью группу . из и элементов И 11, группу из и ре гистрирующих триггеров 12 четвертую группу из и элементов И 13, блок 14 выбора -максимального кода числа, элемент ИЛИ 15, первый элемент Й 16, генератор 17 тактовых импульсов, элемент НЕ 18, второй элемент И 19; счетчик 20, дешифратор 21, вход 22, выход 23 °

Матричная модель 1 графа представляет собой матрицу однородных узлов, каждый из которых представляет собой триггер 2 и подсоединенные к его выходу элементы И 3 и 4.- Размер мат-, ричной модели — n и, где и — мак:симальное число вершин моделируемого графа.

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

Первоначально в модель 1 заносится информация о топологии модулируемого графа (сети) ° При этом триггеры

2; (), = 1, и ), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из r --й вершины в j --ю вершину. Соответствующий триг- гер 2;. определяется пересечением -й строки и 1 -го столбца.. Другие триггеры. 2(, а также счетчики 10 и

20 находятся в нулевом состоянии. В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине модулируемого графа. В счетчики 8 Соответствующих вершин графа заносятся числа. импульсов, дополняющие веса вершин до полной емкости счетчиков. После занесения исходной информации на выходах элементов 5 ИЛИ-НЕ, объединяющих выходы триггеров 2,в строках, соответствующих конечный вершинам моделируемого графа, будут высокие потенциалы.

Это объясняется тем, что в однонап- . равленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом состоянии. со -"тоники Это происходит благодаря тому, что на выходе соответствующих элементов ИЛИ-НЕ 5 и на УпРавляемом входе одноименного элемента И 7 бу-дут высокие потенциалы.

Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 8 переполняется, и низкий потенциал с триггера переполнения (не показан) счетчика 8-подает

10 ся на вторые входы элементов И 4 одноименного столбца матричной модели

1 н одноименный вход элемента ИЛИ 15.

Появление низкого потенциала на вхо» де соответствующего элемента И 9 (5 обеспечивает прекращение подачи счетных импульсов через элемент И 9 на вход регистрирующего счетчика 10, на котором фиксируется код максиМального пути из цанной вершины до ко70 нечной вершины графа сети. Вычисли,тельный процесс прбдолжается .до тех пор, пока на выходах всех счетчиков

8 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 15

25 имеется низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 16 на информационные входы Ълементов И 7 и 9. На этом первый этап работы устройства заканчивается.

Второй этап работы УстРойства начинается после появления высокого потенциала на выходе элемента НЕ 18, 35 после чего счетные импульсы с выхода генератора 17 через элемент И 19 пос- тупают на вход счетчика 20, с первого выхода которого код поступает.на входы дешифратора 21. На выходе дешифра4р тора 21 возбуждаются поочередно выходные шины, которые подсоединены к первым входам соответствующих элементов И 13. Если при этом триггер

12 „. (i= 1,п) находится в единичном

45 состоянии, то высокий потенциал поступает на второй.,вход элемента И 13;. а с его выхода высокий потенциал поступает на информационные входы элементов И 3(((,j= l,n) одноименной строки матричной модели сети 1 и поступает далее через элементы

ИЛИ 6 только на те управляемые входы элементов И 11, которьм в данной строке матричной модели сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых выходах элементов KJIH 6 обеспечивает поступление кодов с выходов счетчиков 10 на входы блока 14, который, 6@ в свою очередь, обеспечивает выбор максимального из.поступивших кодов, при этом соответствующие триггеры

12 перебрасываются в единичное состояние и т.д. Процесс поиска макси65 мального критического пути заканчи995094 вается при появлении единичного сигнала на выходе 23 (сигнал переполнения счетчика 20).

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

Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин.

О 1 1 1 О О О О О О

О О О. О 1 О 1 О О О

О О О 0 1 1 1 0 1 О

О О 0 О О О 1 О 0 0

О О О О О О 0 1 1 О

О О О 0 О О О О 1 О

О О 0 О О О 0 0 О 1

О О О 0 О О О О О 1

О О 0 О О О О 0 О 0

Т=(1; 3; 2; 5; 4; 3; 4; 3, 2; 2) где элементы

О, если нет дуги из -й

С z вершины в -ю!

1, если есть дуга из i-ой вершины в j --ю;

11 - У вес В 1 -A вершины моделиру.емого графа. 35

После занесения исходной информации на входах элемента ИЛИ-НЕ 5 имеется низкий потенциал, а на выходе — высокий. На выходах элементов

ИЛИ-HE 51 — 5 9 присутствует низкий 40 потенциал, поэтому после подачи пускового сигнала на вход 22 устройства счетчика импульсы с выхода генератора

17 через элемент И 16 поступают через элементы Ц 91 — 91р на входы регистрирующих счетчиков 10 1 — 101, а также через элементы И 71в на вход .счетчика 8 „р. Через +1 - 2, с приходом второго импульса, которых заполняет до полной емкости счетчик

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

Таким образом, на выходах элементов ИЛИ НЕ 561 59 и 510 и после при хода второго импульса с выхода генератора 17 через элементы И 7 и . 9 появляются высокие потенциалы, после чего счетные импульсы поступают также на входы счетчиков 88 и 89 и т.д.

Вычислительный процесс перного этапа заканчивается с приходом четырнадцатого импульса, после чего прекращается подача счетных импульсон на вход счетчика 10 (на все другие счетчики 10 подача импульсов прекращается ранее); на выходе элемента ИЛИ 15 имеется низкий потенциал, вследствие чего прекращается подача счетных импульсов на входы счетчиков 8 и 10. Показания счетчиков 10 соответствуют максимальным величинам в графе для каждой вершины, при этом каждому номеру вершины сопоставлен счетчик. В данном случае эти показания (начиная с первого) следующие : 14; 12; 11; 13; 9; 8;

8; 5; 4; 2.

На втором этапе работы устройства после появления высокого потенциала на входе элемента НЕ 18 начинается подача счетных импульсов на вход счетчика 20. Поянление первого импульса с генератора 17 через элемент на входе дешифратора 21 вызывает возбуждение первой его выходной шины, в результате чего с выхода элемента

И 13 высокий потенциал поступает на управляемые входы вторых элементов И 3 первой строки матричной модели графа, поэтому на входы блока 14 поступают коды со счетчиков 10,, 103 и 10, через элементы И 11, 113 и

111 соответственно. Максимальный из

) этих кодов — код со счетчика 104 (13), поэтому в единичное состояние перебрасывается триггер 12 4 .

Далее к содержимому счетчика 20 прибавляется единица и процесс продолжается до тех пор, пока не переполнится счетчик 20, после чего на выходе 23 устройства будет выдан единичный сигнал (сигнал переполнения счетчика 20). В данном примере критический максимальный путь составляет

1, 4, 7, 9 и 10 вершины, о чем свидетельствуют единичные состояния триггеров 121, 12,, 12>, 129 и 1216.

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

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

Устройство для определения максимальных путей в графах, содержащее матричную модель графа размерностью и х n, каждый узел которой содержит триггер и первый элемент И, причем выход триггера соединен с первым входом первого элемента И, а также группу из и элементов ИЛИ-ЙЕ>первую, вторую, третью и четвертую группы из

995094 и элементов И, группу из и счетчиков веса вершин, группу из и регистрирующих счетчиков, блок выбора кода максимального числа, группу из и регистрирующих триггеров, группу из элементов ИЛИ, элемент ИЛИ, дешифратор, первый и второй элементы И, счетчик к генератор тактовых нмйульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И подключен к первым входам элементов И первой и второй групп, выход -ro элемента ИЛИ-НЕ (= J,и, n — раэмерность матричной модели графа) соединен с вторым входом i --го элемента

И первой группы, выход которого под.ключен к входу i-ro счетчика веса .вершины, выход которого соединен с вторым входом i -го элемента И второй группы, выход последнего через q --й регистрирующий счегчик подключен к первому входу элемента И третьей группы, выход которого соединен с 1 -м входом блока выбора кода максимального числа, i-й выход которого подключен к входу i.-ro регистрирующего триггера, выход которого соединен с первым входом l-ro элемента И четвертой--группы выход которого подключен к вторым входам первЫх элементов И узлов -й строки матричной моделй графа, выход первого элемента И i-ro узла матричной модели графа соединен с -м входом т -го элемента ИЛИ груПпы, выход которого подключен к второму входу i -ro элемента И третьей группы, выход элемента ИЛИ соединен с вторым входом первого элемента И, выход второго элемента И через счетчик подключен к выходу дешифратора, > --й выход которого соединен со вторым входом

i-го элемента И четвертой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены элемент

НЕ, а в карый узел матричной модели. графа — второй элемент И выход второго элемента И узла i.-й строки подключен к -му входу i --го элемента ИЛИ-НЕ группы, выход -го счетчика веса вершин группы соединен с первыми входами вторых элементов И узлов -го столбца матричной модели

20 графа и с -м входом элемента ИЛИ, выход которого через элемент НЕ подключен к второму входу второго элемента И, выход. триггера 3-ro узла матричной модели графа соединен с

25 вторым входом второго элемента И уз ла матричной модели графа.

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

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

30 9 798854, кл. G 06 F 15/20, 1978.

2. Авторское свидетельство СССР по заявке Р 3007322/28-24, кл. 6 06 F 15/20, 1980 (прототип).

995094

Составитель И.Дубинина

Редактор A.Âîðîâè÷ Техред Ж.Кастелевич, Корректора.Дэнтко

Заказ 646/34 Тираж 704 Подписное

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

113035, Москва, Ж-35, раущскан наб., д.4/5

Филиал ППП Патент, r.Óæãîðîä, ул..Проектная,4