Устройство для моделирования сетевых графиков Советский патент 1978 года по МПК G06G7/48 

I

Изобретение относится к обп&стя вычислительной техники.

Наиболее блнзкнм техническим решением к изобретению является устройство для моделирования сетевых графиков по основному авт, ев, № 4220О2,

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

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

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

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

И каждой модели ветва подклкгчен к единичному входу второго триггера каждой модели ветви, второй вход дополнительного элемента И блока фор етрования топо6логии соединен с выходом третьего элемента ИЛИ этого блока. На фиг. 1 изображена функциональна схема устройства; на фиг. 2 показан двудольный граф. Устройство содержит блок 1 модел ветвей, блок 2 формирования топологии, блок управления 3, генератор импульсов 4. БЛОК 1 моделей ветви содержит задатчики адресов 5, 6 начального и коне иого узлов соответственно, формирователь временных интервалов 7, триггеры 8, 9, дополнительный триггер 10, элементы И 11, 12, дополнительные элементы И , инвертор 16, элемент ИЛИ 17. Блок формирования топологии содержит элементы И 18-2О, дополнительный элемент И 21, инвертор 22, элементы ИЛИ 23-25, дополнительный элемент ИЛИ 26. . Для понимания работы устройства вве дем следующие названия: ветвей графа, принадлежащие паросочетанию - помечен ные, помеченные и смежные с ними выделенные, остальные - невьщеленные. Если вершине инцидентна одна выделенная ветвь , то последнкяо будем называт концом цепи. Работу устройства рассмотрим на примере отыскания максимального варосочетания двудольного графа с пронуме рованными узлами и ветвями. Работа устройства начинается в режиме основного счета. Так как невыделенных ветвей нет, все триггеры 9 находятся в нулевом состоянии, импульсы серки А поступают на все формирователи временных интервалов 7. После первого импульса серии А на выходе формирователя временных интервалов 7 пер вой модели ветви пояштяетса единичный сигнал, триггеры 8 и 9 первой Модели ветви устанавливаются в едишачное состояШе. Блок управления 3 посредством генератора импульсов 4 и элемента ИЛ 25 обеспечивает подачу на задатчики адресов 5, 6 2 К импульсов серии Б, чем организуются режимы проверки и выделения первой ветви. После первого импульса серии Б триггер 8 первой модели устанавливает ся в нуль, в этот Момент блок упрбшленйя 3 вьщает сигнал на вход дополнительного элемента И 21. На выходе элемента И 18 в этот момент присутст вует нулевой сигиал (так как триггеры 9 второй н третьей моделей ветвей нах дятся в нулевом состоянии, и на вы44ходах элементов ИЛИ 17 второй и третьей моделей ветвей присутствуют нулевые сигаалы). На втором входе элемента ИЛИ 24 также присутствует нулевой сигнал, поэтому на втором входе дополнительного элемента И 21 прис тствует нулевой сигнал. Поэтому на входах дополнительного элементов И 14 тоже присутствуют нулевые сигналы и установка в единицу дополнительного триггера 1О первой модели ветви по номеру первого узла не производится. Синхронно с упомянутым; сигналом на первом входе дополнительного эле мента И 21 блок управления 3 выдает разрешающий сигнал на дополнительный вход элемента И 19, и на все формирователи временных интервалов поступает один импульс серии А. После этого импульса (второго импульса серии А с начала работы) появляется сигнал на выходе формирователя той же первой модели ветви, и триггеры 8, 9 этой модели ветви устанавливаются в единичное состояние. Далее продолжается режим проверки этой ветви. По пятому импульсу серии Б на выходе аадатчика адресов 6 этой модели ветфи появляется единичный сигнал, по которому устанавливается в нуль триггер 8 этой модели ветви. Блок управления 3 выдает импульс на зход дополнительного элемента И 21. Так как на выходе элемента И 18 присутствует нулевой сигнал (поскольку триггеры 9 четвертой и шестой моделей ветвей находятся в нулевом состоянии), то установка в единицу дополнительного триггера 10 первой модели ветви по номеру пятого узла не производится. После каждого режима проверки блок управления 3 устанавливает в нуль все триггеры 9 (установочные входы на фиг. 1 не показаны). Поскольку все триггеры 1О находятся в нулевом состоянии, в режиме выйеления первой ветви состояния элементов устройства не изменяются. После окончания режима вьщеления на дополнительный вход элемента И 19 поступает разрешение на подачу импульсов серии А - начинается режим основного счета второго цикла. Так как все триггеры 9 находятся в нулевом состоянии, все элементы И 11 выдают разрешение на счет импульсов серии А, и последние поступают на все формирователи временных интервалов. По третьему импульсу серии А (считая с начала работы устройства) устанавливаются в единицу триг герм 8, 9 второй модели ветви. Режим основного счета прекращается, начинаетс режим проверки второй ветви. Эта ветвь не является концом цепи ни для первого ни для шестого узлов (тлк как ветви пер вая, третья, пятая и седьмая не выделены). Поэтому режимы проверки и выделения второй ветви происходят аналогично этим режимам для первой ветви. После режима выделения второй ветви начинается режим основного счета третьего цикла. По пятому импульсу серии А уста навливаются в единицу триггеры 8, 9 третьей модели ветви. По первому (в ре жиме проверки этой ветви) импульсу серии Б пометка третьей ветви не производится, так как она не является кон- цом цепи для первого узла. После четвертого (в этом режиме) импульса серии Б на выходе задатчика адресов 6 третье модели ветви появляется единичный сит нал. Поскольку триггер 9 третьей модели ветви находится в единичном состоянии, а на выходах инверторов 16 всех остальных ветвей присутствуют единичные сигналы, последние присутствуют так же на выходах элементов ИЛИ 17 всех моделей ветвей. Поэтому на выходе элемента И 18 появляется единичный сигнал который через элемент ИЛИ 24 разре- шает прохождение единичного сигнала с дополнительного выхода блока управления 3 на выход дополнительного элемента И 21. Этот сигнал через дополнительный элемент И 14 третьей модели ветви устанавл1шает ее дополнительный триггер Ю в единичное состояние. (Единичный сигнал на дополнительном выходе формирователя сохраняется . до следукнцего импульса серии А). Далее до конца режима проверки никаких изменений в состоянии элементов устройства не происходит. После режима проверки все триггеры 9 устанавливаются в нуль, В режиме выделения после первого в этом режиме импульса серии Б через дополнительный элемент И 15 третьей модели ветви, дополнительный элемент ИЛИ 26 блока формирования топологии, дополнительный элемент И13 первой, втopoйj третьей моделей ветвей устанавливаются в единичное состояние триггеры 9 упомянутых моделей, посредством чего осуществляется вьщеление первой, второй, третьей ветвей. После режима выделения третьего цикла граф фиг, 2а приобретает вид фиг. 26 (на фиг. 26, 2в помеченшге ветви показаны толстой линией, а выделенные отмечены крестиком.). В результате во всех последукяамх режимах основного счета импульсы серив А на формирователи,временных интервалов 7 первой, второй, третьей моделей не поступают. В следующих циклах (с четвертого по седьмой включительно) в режимах основного счета появляются сигналы на выходах формирователей моделей с четвертой по седьму ю соответственно. Поскольку эти ветви концами цепей не являются, их пометка в упомянутых циклах не производится. Режймы основного счета и проверки происходят аналогачно этим рехшмам для первой ветви, а режимы выделения - аналогично режиму ш шелення для третьей ветви. После режима выделения седьмой импульсы серии А поступают на формирователи 7 моделей ветвей с четвертой по седьмую включительно. Поскольку установлено, что среди невьщеленных ветвей нет концов цепи (т.е. блок формирования топологии ие выдавал сигнал пометки конца цепи для упомянугых ветвей), блок управления выполняет 1юметку четвертой ветви. А именно, блок управления выдает сигнал на вход элемента Или 24, который разрешает прохождение единичного сигнала с входа дополнительного Элемента И 21 на его же выход. По этому сигналу через дополнительный элемент И 14 четвертой модели ветви устанавливается в единицу дополнительный триггер Ю четвертой модели ветви. После режима проверки устанавливаются в нулевое состояние все триггеры 9, а в режиме выделения устаиавливаются в единичное состояние триггеры 9 моделей ветвей с первой по шестую включител1гно. После этого граф приобретает вид фиг. 2 в. (Остается невыделенной одна, седьмая ветвь). В следующем цикле работы устройства в режиме основного счета появляется сигнал на выходе форкшрователя 7 седьмой модели ветви. В режиме проверки этой ветви она помечается, как конец цепи (поскольжу смежная с ней в третьем узле шестая ветвь уже вьщелена, т.к. ее триггер 9 находится в единичном состоянии, и через элемент ИЛИ 17 шестой модели ветви на элемент И 18 блока формирования топологии выдается единичный сигнал).