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

 

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

Социалистичес4ои

Республик

{61) Дополнительное к аат, сеид-вуИ 422002 с (22) Заявлеио03.12.76 {23 } 2425520/18-24

{5l} М. Кл

Ст 06 Cj 7/48 с присоединением заявки №вЂ” (23) ПриоритетГасудерстееяии9 еенетет

@вета Менеетрее NN ее дезен езебретеееа в еткритее

{43) Опубликовано 05.12.78Бюллетеиь ¹45 ! (45) Дата опубликования опигания 15 12.78

{5З) ygg 681.ззз (088.8) В. В. Васильев, О. Н. Голованова, A. Г.

B. В. Федотов (72) Авторы изобретения

Институт электродинамики AH Украинской

{71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ

ГРАФИКОВ

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

Наиболее близким техническим решением к изобретению является устройство для моделирования сетевых графиков по основному авт, св. % 422002. 5

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

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

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

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

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

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

На фиг. 1 изображена ФУнкционвльнв схема устройства; на фиг. 2 показан двудольный граф.

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

Блок 1 моделей ветви содержит задатчики адресов 5, 6 начального и конечного узлов соответственно, формировв тель временных интервалов 7, триггеры

8, 9, дополнительный триггер 10, элементы И 11, 12, дополнительные элементы И 13-15, инвертор 16, элемент

ИЛИ 17. Блок формирования топологии содержит элементы И 18-20, дополнительный элемент И 21, инвертор 22, элементы ИЛИ 23-25, дополнительный элемент ИЛИ 26.

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

Если вершине инцидентив одна выделенная ветвь, то последнюю будем называть концом цепи.

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

Работа устройства начинается в режиме основного счета. Так как невыделенных ветвей нет, все триггеры 9 находятся в нулевом состоянии, импульсы серии A поступают нв все формирователи временных интервалов 7. После пер» вого импульса серии А нв выходе формирователя временных интервалов 7 первой модели ветви появляется единичный . сигнал, триггеры 8 и 9 первой модели ветви устанавливаются в единичное состояние. Блок управления 3 посредством генератора импульсов 4 и элемента ИЛИ

25 обесцечиввет подачу иа задвтчики адресов 5 6 2И импульсов серии Б, чем организуются режимы проверки и вьщеления первой ветви.

После первого импульса серии Б триггер 8 первой модели устанавливается в нуль, в этот момент блок управления Э выдает сигнал на вход дополнительного элемента И 21. На выходе элемента И 18 в этот момент присутствует нулевой сигнал (так как триггеры

9 второй и третьей моделей ветвей находятся в нулевом состоянии, и на выходах элементов ИЛИ 17 второй и третьей моделей ветвей присутствуют нулевые сигналы). На втором входе элемента ИЛИ 24 также присутствует нуg левой сигнал, поэтому на втором входе дополнительного элемента И 21 присутствует нулевой сигнал, Поэтому на входах дополнительного элементов И 1 4 тоже присутствуют нулевые сигналы и установка в единицу дополнительного триггера 10 первой модели ветви по номеру первого узла не производится, Синхронно с упомянутым: сигналом нв первом входе дополнительного эле13 „мента И 21 блок управления 3 выдает рвзрешаюший сигнал на дополнительный вход элемента И 19, и на все формирователи временных интервалов поступает один импульс серии A. После этого им3© пульса (второго импульса серии А с начала работы) появляется сигнал на выходе формирователя той же первой модели ветви, и триггеры 8, 9 этой модели ветви устанавливаются в единичное состояние.

М Лалее продолжается режим проверки этой ветви. По пятому импульсу серии Б на выходе задатчика адресов 6 этой моде.ли ветви появляется единичный сигнал, по .которому устанавливается в нуль триггер

ЗЕ 8 этой модели ветви. Блок управления 3 выдает импульс на вход дополнительного . элемента И 21. Твк квк на выходе элемента И 18 присутствует нулевой сигнал ..: (поскольку триггеры 9 четвертой и шес> той моделей ветвей находятся в нулевом состоянии), то установка в единицу допол« .нительного триггера 10 первой модели ветви, по номеру пятого узла не произво« дится. После каждого режима проверки

4@ блок управлении 3 устанавливает в нуль все триггеры 9 (установочные входы на фиг. 1 не показаны). Поскольку все триггеры 10 находятся в нулевом состоянии, в режиме выделения первой ветви

4® состояния элементов устройства не изменяются, После окончания режима выделения на дополнительный вход элемента И 19 поступает разрешение на подачу импульсов серии А - начинается режим основного счета второго цикла. Твк как все триггеры 9 находятся в нулевом состоянии, все элементы И 11 выдают разрешение на счет импульсов серии А, и последние поступают íà все формирователи временных интервалов. По третьему импульсу серии А (считая с начала работы устройства) устанавливаются в единицу триг 636634 геры 8, 9 второй модели ветви. Режим ! основного счета прекращается, начинается режим проверки второй ветви. Эта ветвь не является концом цепи ни для первого, ни для шестого узлов (так как ветви пер- 3 вая, третья, пятая и седьмая не выделены). Поэтому режимы проверки и выделения второй ветви происходят аналогично этим режимам для первой ветви. После режима выделения второй ветви начи- 16 нается режим основного счета третьего цикла. По пятому импульсу серии А устанавливаются в единицу триггеры 8, 9 третьей модели ветви. По первому (в режиме проверки этой ветви) импульсу серии Б пометка третьей ветви не производится, так как она не является концом цепи для первого узла, После четвертого (в этом режиме) импульса серии

Б на выходе эадатчика адресов 6 третьей @ модели ветви появляется единичный сигнал. Поскольку триггер 9 третьей модели ветви находится в единичном состоянии, а на выходах инверторов 16 всех остальных ветвей присутствуют единичные сигналы, последние присутствуют также на выходах элементов ИЛИ 17 всех моделей ветвей. Поэтому на выходе элемента И 18 появляется единичный сигнал, который через элемент ИЛИ 24 раэре- М шает прохождение единичного сигнала с дополнительного выхода блока управления 3 иа выход дополнительного элемента И 21. Зтот сигнал через дополнительный элемент И 14 третьей модели ветви устанавливает ее дополнительный триггер

10 в единичное состояние. (Единичный сигнал на дополнительном выходе формирователя сохраняется . до следукацего импульса серии A).

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

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

Фиг, 2а приобретает вид фиг. 26 (на фиг. 26, 2в помеченные ветви показаны толстой линией, а выделенные о". мечены крестиком. ) .

B результате во всех последуюшхх режимах основного счета импульсы серии

А на формирователи временных интервалов 7 первой, второй, третьей моделей не поступают.

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

После режима вьщеления седьмой ветви импульсы серии А поступают на формирователи 7 моделей ветвей с четвертой по седьмую включительно.

Поскольку установлено, что среди невьщеленных ветвей нет концов цепи (т.е. блок формирования топологии не выдавал сигнал пометки конца цепи для упомянутых ветвей), блок управления выполняет пометку четвертой ветви. А именно, блок управления вьщает сигнал на вход элемента ИЛИ 24, который разрешает прохождение единя ш ого сигнала с входа дополнительного элемента И 21 на его же выход. Пс этому сигналу через дополнительный элемент И 14 четвертой модели ветви устанавливается в единицу дополнительный триггер 10 четвертой модели ветви.

После режима проверки устанавливаются в нулевое состояние все триггеры 9, а в режиме выделения устанавливаются в единичное состояние триггеры 9 моделей ветвей с первой по шестую включитель но. После этого граф приобретает вид фиг. 2 в. (Остается невьщеленной одна, седьмая ветвь). В следующем цикле работы устройства в режиме основного счета появляется сигнал на выходе формирователя 7 седьмой модели ветви.

B режиме проверки этой ветви она помечается, как конец цепи (поскольку смежная с ней в третьем узле шестая ветвь уже выделена, т.к. ее триггер 9 находится в единичном состоянии, и через элемент ИЛИ 17 шестой модели ветви на элемент И 18 блока формирования топологии выдается единичный сигнал).

636634

Г осле режима выделения седьмой ее ви все триггеры 9 устанавливаются в единичное состояние. Ветви, дополнительные триггеры 10 моделей которых уста« иовлены в единицу, представляют собой искомое максимальное паросочетание исходного двудольного графа, A именно, это ветви третья, четвертая, седьмая.

$0

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

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

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

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

hie 422002, кл. Cj 06 (j 7/48, 1972 °

ЦНИИПИ Заказ 6943/40

Тираж 784 Подписное

Филиал ППП Патент", г. Уж город, ул Лроектнея, 4