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

(56) Авторское свидетельство СССР У 962968, кл. 6 06 Р 15/20, 1981.Авторское свидетельство СССР В 013965, кл. 6 06 Р 15/20, 1981, (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФЕ(57) Изобретение относится к вычислительной технике, может быть испольэо" вано для исследования сетевых графов без контуров и петель и позволяет находить минимальную и максимальную массу дуг, соединенных с вершинами . графа, определять критические пути в .графе и свободные резервы времени исол ун с Затемровляют фа вер ОСУДАРСТВЕННЫЙ КОМИТ О ДЕЛАМ ИЗОБРЕТЕНИЙ И нения вершин графа, что расширяеткциональные возможности устройста, С этой целью устройство для иследования путей в графе содержит надиагональную матрицу моделей дуг, соержащую в своих узлах регистры, на оторых записана масса дуг графа, и локи элементов И, Критический путь пределяется путем анализа на схемах равнения группы экстремальных кодов ассы дуг. Результаты анализа запомиаются на регистрах одной из двух рупп, входящих в состав устройства.при помощи двух групп сумматаи двух групп вычитателей опредеся максимальные и минимальные массы дуг всех вершин графа, а также фезерв свободного времени исполненияИзобретение относится к вычислительной технике и может быть испопьзовано при исследовании сетевых графов, без контуров и петель.Цель изобретения - расширение Функциональных возможностей устройстваза счет определения минимального имаксимального веса ребер, соединенныхс вершинами графа, 10На чертеже представлена функциональная схема устройства.Устройство содержит наддиагональную матрицу 1 моделей 2 дуг, состоящих из регистра 3 и бпока 4 элементов И, генератор 5 тактовых импульсов,распределитель 6 импульсов, две группы блоков 7 и 8 элементов ИЛИ, блок9 выбора максимального кода, блок 10элементов НЕ две группы регистров 2011 и 12, две группы сумматоров 13 и14, две группы вычитателей 15 и 16,наддиагональную матрицу 17 опроса,каждый узел которой содержит блок 18элементов И, два счетчика 19 и 20, 25группу схем 21 сравнения и переключатель 22.Устройство работает следующим образом.Б матрицу 1 заносят информацию о З 0топологии графа, загружая в соответ.ствующие регистры 3 веса дуг, Обнуляют распределитель 6, счетчики 19 и20 и регистры 11 и 12.После подачи сигнала пуска импульсы с выхода генератора 5 поступают навход распределителя 6, который поочередно выдает импульсы на свои выходы,Импульс с первого выхода распределителя 6 открывает блок 4 элементов И 40модели 2 (М,М) - го узла матрицы 1между (М)-й и М-й вершинами графа,через соответствующий блок 7 элементов ИЛИ поступает на соответствующийвход блока 9, который выдает его навыход в инверсном коде, а блок 10 -в прямом коде. Через переключатель 22подвес дуги поступает на информационные входы регистров 11, Задним фронтом импульса с первого выхода распре-делителя 6 вес этой дуги, равный величине максимального пути из (М)-йв М-ю вершину графа, записывается всоответствующий регистр 11,При поступлении импульса с второго выхода распределителя 6 открываются блоки 4 моцелей 2 (М)-й строкиматрицы 1 и вес дуги (М,М) с выходасоответствующего регистра 3 через соответствующий блок 4 элементов И и блок 7 элементов ИЛИ поступает на соответствующий вход блока 9, а вес дуги (М; М) через соответствующий блок 7 элементов ИЛИ - на вход первого слагаемого сумматора 13, на вход второго слагаемого которого поступает вес дуги (М,М) с выхода соответствующего регистра 11. Суммарный вес дуги (М,М) и дуги (М,М) с выхода соответствующего сумматора 13 поступает на вход блока 9, который выбирает наибольший из двух поступивших кодов и выдает его на выход в инверсном, а блок 10 - в прямом коде через переключатель 22 на информационные входы регистров 11, из которых лишь (М)-й регистр 11 записывает его, при поступлении на его вход признака записи заднего фронта импульса с второго выхода распределителя 6.Далее устройство работает аналогично, и после прохождения импульса с последнего выхода распределителя 6 в регистрах 11 оказываются записанными величины Т максимальных путей иэ вершин графа в его конечную М-ю вершину. Импульс (М)-го выхода распределителя 6 поступает на вход счетчика 20, содержимое которого становится равным "1", Единичный сигнал с выхода младшего разряда счетчика 20 поступает на выход устройства как сигнал на съем величин Т и на входы признака записи регистров 12, которые запоминают поступающие с выходов соответствующих вычитателей 16 наиболее поздние времена Т, выполнения вершин графа, получаемые путем вычитания из величины Т, поступающей на входы вычитателей 16 с. выхода первого регист. ра 11, величин максимальных путей, поступающих на входы вычитателей 16 с выходов соответствующих регистров 11, начиная с второго задним фронтом импульса с (М)-го выхода распределителя 6, поступающим на вход останова генератора 5, Завершается работа устройства на первом этапеПеред вторым этапом устройство приводят в исходное состояние, однако в матрицу 1 весов дуг графа транспонируют относительно неглавной диагонали. Счетчик 20 и регистры 12 не обнуляют.После подачи пускового сигнала импульсы генератора 5 вновь поступают на вход распрецелителя 6, и далее уст з 1 Згройство работает так же, как на первом этапе. В регистрах 11 оказываются записанными величины максимальныхпутей инвертированного графа, которыев прямом графе соответствуют наиболееранним временам Т выполнения вершин.При этом номера регистров 11 такжедолжны инвертироваться, т.е. в первом регистре 11 записывается наиболеераннее время выполнения М - й вершины,а в (М) "м регистре 11 - наиболеераннее время выполнения первой вершины,При поступлении импульса с последнего выхода распределителя 6 содержимое счетчика 20 становится равным "2". Единичный сигнал с выходаего второго разряда поступает на выход устройства как сигнал на съем свыходов регистров 11 величин Т нанеболее ранних времен выполнения вершин. и на входы опроса схем 21 сравнения.Схемы 21 сравнения сравнивают поступающие на их входы величины Тр (с выходов регистров 11) и Т (с выходоврегистров 12) и выдают на выходы устройства единичные сигналы только приравенстве Т и Т , что имеет местолишь для вершин, лежащих на критическом пути. Таким образом, единичныесигналы на выходах тех или иных схем21 сравнения указывают вершины, черезкоторые проходит максимальный критический путь графа между его начальнойи конечной вершинами. На случай наличия в исследуемом графе двух или более таких одинаковых по величине путей по схеме графа уточняют, одномуили нескольким таким путям принадлежат найденные вершины.На третьем этапе для каждой дугиграфа определяется свободный резерввремени Р, =Тр -(Т+Т), где Т - весданной дуги. Для этого устройствовновь приводят в исходное состояние,не обнуляя, счетчик 20, регистры 11и 12 и сохраняя записанную в матрице1 информацию о топологии инвертированного графа. Переключатель 22 переводят в другое положение, подключаясчетчик 18, в который заносят "1".Затем вновь подают сигнал пуска иимпульсы генератора 5 вновь поступают на вход распределителя 6, импульсс первого выхода которого открывает(М,М)-й блок 4 элементов И, и весдуги (1,2) между первой и второй вершинами графа через соответствующий5500 55 5 10 15 20 25 30 35 ао 45 50 блок 7 посту:ает на вход соответствующего сумматора 15, на другой входкоторого через (М,М)-й блок 18, открытый импульсом с первого выходараспределителя 6, и соответствующийблок 8 элементов ИЛИ поступает значение Т(2) времени выполнения второйвершийы. На выход устройства с выхода вычитателя 15 выдается величинаР (1,2) свободного резерва временидуги (1,2) между первой и второй вершинами графа, при этом номер вычитателя 15 (в данном случае этот номер 1)указывает номер начальной вершины дуги, а код на выходе счетчика 19 (вданном случае после поступления одного импульса с первого выхода распределителя 6, это код "2") - номер конечной вершины дуги.Импульсы с второго, третьего ит.д. выходов распределителя 6 открывают блоки 18 элементов И соответствующих строк матрицы 17 для прохождения на входы соответствующих вычитателей Тг с выходов соответствующихрегистров 11, на другие входы вычитателей 15 с выходов соответствующихсумматоров 14 (для первого вычитателя 15 с выхода М-го блока 7 элементов ИЛИ) - суммы значений Тп и весовдуг Т. Например, импульс с второго выхода распределителя 6, открыв блоки 4элементов И моделей 2 (М)-й строкиматрицы 1, обусловливает поступлениевеса дуги, записанного в (М,М)-мрегистре 3, через блок 7 элементовИЛИ на вход второго сумматора 14, надругой вход которого поступает значение Т (2) с выхода второго регистра12 так, что на вход второго вычитате".ля 15 поступает величина Тп(2)+Т(2,3).В результате с выходов соответствующих вычитателей 15 в темпе работыраспределителя 6 снимаются величинысвободных резервов времени дуг графа,причем выдаваемые счетчиком 19 кодыуказывают номера конечных вершин дуг,Причем, величина Р тогда указываетосвободный резерв времени, когда онабольше О. Импульс с (М)-го выходараспределителя 6, поступая на входостанова генератора 5, прекращаетработу устройства,Формула изобретения Устройство для исследования путейв графе, содержащее две группы ре5 13 гистров, блок выбора максимального кода и наддиагональную матрицу моделей дуг из (М) строк и (М) столбцов, где М - число вершин в графе, каждый узел которой содержит блок элементов И и регистр, выход которого подключен к первому входу блока элементов И, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального и максимального веса ребер, соединенных с вершинами графа, в него введен распределитель импульсов, переключатель блок элементов НЕ, две группы блоков элементов ИЛИ, две группы сумматоров, группа схем сравнения, два счетчика, две группы вычитателей, генератор так товых импульсов и наддиагональная мат рица опроса из (М) строк и (М) столбцов, каждый узел которой содержит блок элементов И, причем вход пуска генератора тактовых импульсов является входом пуска устройства, выход генератора тактовых импульсов подключен к первому информационному входу переключателя и входу распределителя импульсов, (М-К)-й выход которого (К, ,М) подключен к вторым входам всех блоков элементов и К-й стро. ки наддиагональной матрицы моделей дуг, к входу признака. записи К-го регистра первой группы и к первым входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, (М)-й выход распределителя импульсов подключен к входу останова генератора тактовых импульсов и к счетному входу первого счетчика, выхоц младшего разряда которого подключен к входам признаков записи всех регистров второй группы и является .выходом признака окончания первого этапа работы устройства, выходы всех блоков элементов И К-го столбца (К 11) наддиагональной матрицы моделей дуг подключены к соответствукнцим входам К-го блока (КФ 1) элементов ИЛИ первой группы, выход К-го блока элементов ИЛИ первой группы (КФ 1, М) подключен к входу первого слагаемого К-го сумматора первой группы и к входу первого слагаемого (М-К)-го сумматора второй группы, выход блока элементов И первого столбца наддиагональной мат рицы моделей дуг подключен к входу первого слагаемого первого сумматора первой группы и к входу первого слагаемого (М)-го сумматора второй 25500 6 группы, выход К-го сумматора первой группы (КМ) подключен к К-му информационному входу блока выбора максимального кода, выход (М)-го блока элементов ИЛИ первой группы подключен к (М)-му информационному входу блока выбора максимального кода, выход которого подключен к входу блока элементов НЕ, выход которого подключен к 10 второму информационному входу переключателя, второй выход которого подключен к информационным входам всех регистров первой группы, выход К-го регистра первой группы (КФ 1) подключен к вторым входам всех блоков элементов И К-й строки наддиагональной матрицы опроса, к входам вычитаемого (К)-го вычитателя первой группы, к входу второго слагаемого К-го суммато ра первой группы, первому информационному входу (М-К)-6 схемы сравнения группы и является К-м информационным выходом первой группы устройства, выхоц первого регистра первой группыпоцключен к вторым входам всех блоков элементов И первой строки наддиагональной матрицы опроса, к входам уменьшаемого всех вычитателей первой группы и является первым информационным выходом первой группы устройства, выход К-го вычитателя первой группы (КФМ)подключен к информационному входу К-го регистра второй группы, выход которого подключен к входу второ го слагаемого (М-К)-го сумматора второй группы и к второму информационному входу К-й схемы сравнения группы, выход признак равенства которой является К-м информационным выходом второй группы, выходы блоков элементов И К-го столбца (К 41) наддиагональной матрицы опроса подключены к соответствующим входам К-го блока элементов ИЛИ второй группы, выход которого под ключен к входу уменьшаемого (М-К)-говычитателя второй группы, выход блока элементов И первого столбца подключен к:входу уменьшаемого (М)-го вычитателя второй группы, выход К-го сумма тора второй труппы (К 1) подключен квходу вычитаемого К-го вычитателя второй группы, выход которого является К-м информационным выходом третьейгруппы устройства, выход (М)-го блока элементов ИЛИ первой группы подключен к входу вычитаемого первого вычитателя второй группы, информационный выход которого является пер1325500 8ройства, первь.й выход переключателя подключен к счетному входу второго счетчика, информационный выход которого является информационным выходом устройства. Составитель А.11 ишиТехред И,Попович Редактор Б.ПеКороль ррек Заказ 311 ИИПИ коми отк 113035,ушск зводственно-поли ческ вым информационным выходом третьейгруппы устройства, выход второго разряда первого счетчика подключен квходам опроса всех схем сравнениягруппы и является выходом признакаокончания второго этапа работы устТираж 672осударственнолам изобретенМосква, Ж,Подписита СССРтийнаб., д.4 едприятие,г.ужгород,ул.Проектная,4