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

Союз Советских Социалистнчеооа республик(5) М. КлСт 067/48 с присоединением заявки (23) ПриоритетГкуаарстееяии ненетет Сееета Менестрее СССР ее дезам езебретвкей н еткрпте(43) Опубликовано 05.12.78 Бюллетеиь %45(4) Дата опубликования описания 15,12.78(72) Авторы изобретени лектродинамики АН Украинс 71) аявител нст 54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ Изобретение относится к области вычислительной те кликнемНаиболее близким техническим решением к изобретению является устройство для моделирования сетевых графиков по основному авт, св. % 422002. 5Известное устройство не позволяет определять максимальное паросочетание двудольного графа,Целью изобретения является расшире ние функциональных воэможностей эа счет 10 дополнительной воэможности отыскания максимального паросочетания двудольного графа.Укаэанная цель достигается тем, что в блок формирования топологии дополни тельно введены элемент И и элемент ИЛИ, в каждую модель ветви дополнительно введены триггер и элементы И, первые входы первого и второго дополнительных элементов И каждой модели ветви подключены к выходу 1 а эадатчика адреса конечного узла, второй вход первого дополнительного элемента И каждой модели ветви подсоединен к выходу дополнительного элемента ИЛИ блокаформирования топологии, вход которогоподключен к выходу второго дополнительного элемента И каждой модели ветви,второй вход которого через дополнительный триггер подсоединен и выходу третьего дополнительного элемента И каждоймодели ветви, первый вход которого подключен к дополнительному выходу формирователя временных интервалов, второйвход третьего дополнительного элементаИ каждой модели ветви подсоединен к выходу дополнительного элемента И блокаформирования топологии, первый вход которого подключен к первому дополнительному выходу блока управления, второйдополнительный выход которого подсоединен к дополнительному входу второго элемента И блока формированич топологии,выход первого дополнительного элементаИ каждой модели ветви подключен к единичному входу второго триггера каждоймодели ветви, второй вход дополнительного элемента И блока формирования тонологии соединен с выходом третьего элемента ИЛИ этого блока.На фиг. 1 изображена Функциональнвзгсхема устройства; на фиг. 2 показан двудольный граф,Устройство содержит блок 1 моделейветвей, блок 2 фоомирования топологии,блок управления 3, генератор импульсов4. Блок 1 моделей ветви содержит задатчики адресов 5, 6 начального и конечного узлов соответственно, формирователь временных интервалов 7, триггеры8, 9, дополнительный триггер 10, элементы И 11, 12, дополнительные элементы И 13-15, инвертор 16, элементИЛИ 17, Блок формирования топологиисодержит элементы И 18-20, дополнительный элемент И 21, инвертор 22,элементы ИЛИ 23-25, дополнительныйэлемент ИЛИ 26,Для понимания работы устройства введем следующие названия: ветви графа,принадлежащие паросочетаиию - помеченные, помеченные и смежные с нимивьщелениые, остальные - невыделенные.Если вершине инцидентив одна выделенная ветвь, то последнюю будем называтьконцом цепи.Работу устройства рассмотрим иапримере отыскания максимального ивросочетания двудольного ,графа с пронумерованными узлами и ветвями.Работа устройства начинается в режиме основного счета. Так как невыделенных ветвей нет, все триггеры 9 находятся в нулевом состоянии, импульсысерии А поступают ив все формирователи временных интервалов 7, После первого импульса серии А нв выходе формирователя временных интервалов 7 первой модели ветви появляется единичный .сигнал, триггеры 8 и 9 первой моделиветви устанавливаются в едивичное состояние, Блок управления 3 посредствомгенератора импульсов 4 и элемента ИЛИ25 обесцечиввет подачу иа задвтчикиадресов 5, 6 2 И импульсов серии Б,чем организуются режимы проверки ивьщеления первой ветви,После первого импульса серии Бтриггер 8 первой модели устанавливается в нуль, в этот момент блок управления Э выдает сигнал на вход дополнительного элемента И 21. На выходеэлемента И 18 в этот момент присутсчвует нулевой сигнал (так как триггеры9 второй и третьей моделей ветвей находятся в нулевом состоянии, и на выходах элементов ИЛИ 17 второй и третьей моделей ветвей присутствуют нулевые сигналы). На втором входе элемента ИЛИ 24 также присутствует нуу левой сигнал, поэтому на втором входедополнительного элемента И 21 присутствует нулевой сигнал, Поэтому на входах дополнительного элементов И 1 4тоже присутствуют нулевые сигналы и1 ф установка в единицу дополнительноготриггера 10 первой модели ветви по номеру первого узла не производится,Синхронно с упомянутым: сигналомнв первом входе дополнительного эле 13 мента И 21 блок управления 3 выдаетразрешающий сигнал на дополнительныйвход элемента И 19, и на все формирователи временных интервалов поступаетодин импульс серии А, После этого им 36 пульса (второго импульса серии А с начала работы) появляется сигнал на выходеформирователя той же первой модели ветви, и триггеры 8, 9 этой модели ветвиустанавливаются в единичное состояние,М Далее продолжается режим проверки этойветви. По пятому импульсу серии Б навыходе задатчика адресов 6 этой модели ветви появляется единичный сигнал, покоторому устанавливается в нуль триггер3 Е 8 этой модели ветви. Блок управления 3выдает импульс на входдополнительного. элемента И 21, Так квк на выходе элемента И 18 присутствует нулевой сигнал(поскольку триггеры 9 четвертой и шесМ той моделей ветвей находятся в нулевомсостоянии), то установка в единицу допол.нительного триггера 10 первой моделиветви, по номеру пятого узда не производится. После каждого режима проверки4 ф блок управлении 3 устанавливает в нульвсе триггеры 9 (установочные входына фиг. 1 не показаны). Поскольку всетриггеры 10 находятся в нулевом состоянии, в режиме выделения первой ветви4 ф состояния элементов устройства не изменяются,После окончания режима выделения надополнительный вход элемента И 19 поступает разрешение на подачу импульсовф серии А - начинается режим основногосчета второго цикла, Твк как все триггеры 9 находятся в нулевом состоянии, всеэлементы И 11 выдают разрешение насчет импульсов серии А, и последниефф поступают нв все формирователи временных интервалов. По третьему импульсусерии А (считая с начала работы устройства) устанавливаются в единицу триг 636634геры 8, 9 второй модели ветви. Режимосновного счета прекращается, начинаетсярежим проверки второй ветви, Этв ветвьне является концом цепи ни для первого,ни для шестого узлов (так квк ветви пер-ввя, третья, пятая и седьмая не выделены). Поэтому режимы проверки и выделения второй ветви происходят аналогично этим режимам для первой ветви. После режима выделения второй ветви начинвется режим основного счета третьегоцикла, По пятому импульсу серии А устанавливаются в единицу триггеры 8, 9третьей модели ветви. По первому (в режиме проверки этой ветви) импульсу серии Б пометка третьей ветви не производится, твк квк онв не является концом цепи для первого узла, После четвертого (в этом режиме) импульса серииБ на выходе эадатчика адресов 6 третьей цмодели ветви появляется единичный сигнал. Поскольку триггер 9 третьей модели ветви находится в единичном состоянии, а на выходах инверторов 16 всехостальных ветвей присутствуют единич- Иные сигналы, последние присутствуют также на выходах элементов ИЛИ 17 всехмоделей ветвей. Поэтому нв выходе элемента И 18 появляется единичный сигнал,который через элемент ИЛИ 24 раэре- Мшает прохождение единичного сигнала сдополнительного выхода блока управления 3 иа выход дополнительного элемента И 21. Зтот сигнал через дополнительный элемент И 14 третьей модели ветви Мустанавливает ее дополнительный триггер10 в единичное состояние. (Единичныйсигнал на дополнительном выходе формирователя сохраняется . до следующего импульса серии А),40 Палее до конца режима проверки никаких изменений в состоянии элементов устройства не происходит. После режима проверки все триггеры 9 устанввливв- ф ются в нуль. В режиме вьщеления после первого в этом режиме импульса серии Б через дополнительный элемент И 15 третьей модели ветви, дополнительный элемент ИЛИ 26 блока формирования топологии, дополнительный элемент И 13 первой, второй, третьей моделей ветвей устанавливаются в единичное состояние триггеры 9 упомянутых моделей, посредством чего осуществляется выделение первой, второй, третьей ветвей. После режима выделения третьего цикла граф Фиг, 2 а приобретает вид фиг, 26 (на фиг. 26, 2 в помеченные ветви показанытолстой линией, в выделенные о".меченыкрестиком, ),В результате во всех последукнмхрежимах основного счета импульсы серииА на формирователи временных интервалов 7 первой, второй, третьей моделейне поступают.В следукицих циклах (с четвертого поседьмой включительно) в режимах основного счета появляются сигналы на выходах формирователей моделей с четвертойпо седьмую соответственно, Посколькуэти ветви концами цепей не являются, ихпометка в упомянутых циклах не производится. Режимы основного счета и проверки происходят аналогично этим режимам для первой ветви, а режимы вьщеления - аналогично режиму выделения длятретьей ветви.После режима вьщеления седьмой ветви импульсы серии А поступают на формирователи 7 моделей ветвей с четвертойпо седьмую включительно.Поскольку установленр, что среди невьщеленных ветвей нет концов цепи (т.е,блок формирования топологии не выдавалсигнал пометки конца цепи для упомянутых ветвей), блок управления выполняетпометку четвертой ветви. А именно, блокуправления вьщает сигнал нв вход элемента ИЛИ 24, который разрешает прохождение единичного сигнала с входа дополнительного элемента И 21 на его же выход. Пс этому сигналу через дополнительный элемент И 14 четвертой модели ветвиустанавливается в единицу дополнительный триггер 10 четвертой модели ветви.После режима проверки устанавливаютсяв нулевое состояние все триггеры 9, ав режиме вьщеления устанавливаются вединичное состояние триггеры 9 моделейветвей с первой по шестую включительно. После этого граф приобретает видфиг. 2 в, (Остается невьщеленной одна,седьмая ветвь), В следующем цикле работы устройства в режиме основного счета появляется сигнал на выходе формирователя 7 седьмой модели ветви. В режиме проверки этой ветви онв помечается, как конец цепи (поскольку смежная с ней в третьем узле шестая ветвь уже вьщелена, т.к. ее триггер 9 находится в единичном состоянии, и через элемент ИЛИ 17 шестой модели ветви на элемент И 18 блока формирования топологии выдается единичный сигнал).636634 7Госле режима выделения седьмой ее ви все триггеры 9 устанавливаются в единичное состояние. Ветви, дополнительные триггеры 10 моделей которых уста новлены в единицу, представляют собой искомое максимальное паросочетание исходного двудольного графа, А именно, это ветви третья, четвертая, седьмая. 36формула изобретения Устройство для моделирования сетевых графиков по авт.св. М 422002, отличающееся тем,что,с ц целью расширения функциональных возможностей за счет отыскания максималь-, ного паросочетания двудольного графау в блок формирования топологии дополнительно введены элемент И и элемент 20 ИЛИ, в каждую модель ветви дополнительно введены триггер и элементы И, первые входы первого и второго дополнительных элементов И каждой модели ветви подключены к выходу задатчика адреса конечно- д го узла, второй вход первого дополнительного элемента И кахщой модели ветви подсоединен к выходу дополнительного элемента ИЛИ блока формирования топологии, вход которого подключен к выходу второго дополнительного элемента Икаждой модели ветви, второй вход которого через дополнительный триггер подсоединен к выходу третьего дополнительного элемента И каждой модели ветви,первый вход которого подключен к дополнительному выходу формироввтеля времен;ных интервалов, второй вход третьего дополнительного элемента И каждой модели ветви подсоединен к выходу дополнительного элемента И блока формированиятопологии, первый вход которого подключен к первому дополнительному выходу блока управления, второй дополнительный выход которого подсоединен кдополнительному входу второго элемента И блока формирования топологии, выход первого дополнительного элемента И каждой модели ветви подключен кединичному входу второго триггера каждой модели ветви, второй вход дополни-.тельного элемента И блока формированиятопологии соединен с выходом третьегоэлемента ИЛИ этого блока,Источники информации, принятые во вннмание при экспертизе:1. Авторское свидетельство СССР