Устройство для решения задачи о максимальном

О П И С А Н И Е 27908ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических РеспубликЗависимое от авт. свидетельствааявлено 27.1,1969 ( 1307034/18 присоединением заявкиКомитет по делам изобретений и открыт при Совете Министре СССРМПК б 06 д 7/4 иоритет 81.33,001.5088,8) бликовано 26.Ч.1970, Бюллетень18 Дата опубликования описания 9.1 Х.1 Автор зобретения В. В. Васильевнститут кибернетики АН Украинской СС,т йй%Я аявител УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОТОКЕ В СЕТИНОМ И Изобретение относится к области вычислительной техники; оно может быть использовано для расширения возможностей комбинированных специализированных машин при решении задачи о максимальном потоке в сетях. 5Известны устройства для решения задачи о максимальном потоке в сети, содержащие модели ветвей, соединенные между собой первыми и вторыми полюсами согласно топологии сети и образующие модель сети, индикато ры насыщенности ветвей, также соединенные между собой своими первыми и вторыми полюсами согласно топологии сети и образующие индикационную схему, источники тока и напряжения, триггер, схемы И и ИЛИ, формирователь и измерительный счетчик.В предложенном устройстве между начальным и конечным полюсами модели сети включены параллельно источник тока и дополни. тельная модель ветви, служащая индикатором насыщенности сети.Выходной полюс этой модели ветви соединен с одним из входов триггера, другой вход которого соединен с выходом первой схемы И, выходы этой схемы служат входами соответственно импульсов тактового генератора и сигнал пуска, первый выход триггера соединен с первым входом второй схемы И, второй вход которой соединен через формирователь с выходом схемы ИЛИ, а третий - служит входом импульсов тактового генератора. Входы схемы ИЛИ соединены с выходными полюсами индикаторов насыщенности индикационной схемы, а также со вторым выходом триггера, выход второй схемы И соединен со входом измерительного счетчика и с третьими полюсами моделей ветвей, четвертые полюса которых соединены с третьими полюсами соответствующих индикаторов насыщенности ветвей индикационной схемы, входной полюс индикационной схемы соединен с источником единичного напряжения, а промежуточные ее полюсы также соединены через резисторы с источниками напряжения, Кроме того, в предложенном устройстве модели ветвей состоят из элемента, моделирующего ветвь для решения задачи о кратчайшем пути, вход которого служит первым полюсом модели ветви, нуль-органа, вход которого соединен с выходом упомянутого элемента, схемы И, счетчика, триггера и ключа, первый вход которого соединен с выходом нуль-органа, второй - с выходом триггера, а выход последнего - слу- жит вторым полюсом модели ветви, причем первый вход схемы И соединен с выходом нуль-ограна, второй - с выходом триггера, а третий - служит третьим полюсом модели ветви, выход схемы И соединен со входом счетчика, выход которого соединен со входом триггера, выход триггера служит четвертымполюсом модели ветви. Ийдикаторы насыщенности ветвей состоят из схемьс И, одни входы которых соединены между собой и служатпервым полюсом индикатора, ц инвертора,вход которого через диод соединен с выходомпервой схемы И и служит вторым полосоминдикатора, а выход соединен со вторым входом другой схемы И. Выход последней служит выходным полюсом индикатора. причемвторой вход первой схемы И служит третьим пол.осам индикатора.Этц отлььчья устройствасить его точность и разрецьаюц 1 ую способность.На фиг. 1 показана схема модели ветви(МВ); ца фцг. 2 - схема индикатора пасьпцецностп ветви (И 1-1 В); на фцг. 3 и 4 - два варианта схем предложенного устройства.В основм работы предложенного усгроцстваположен способ решения задач, вытекающийиз теоремы о максимальном потоке ц минимальном сечении, сущность которого заключается в след ощем.Определяют какой-либо путь (нацример,кратчайший) пз ььачяля в конец сети, проходящий по ненасыщенным ветвям, Прц этом следует отметить, что треоовацце минимальностидлины пути не является обязательным, но этотпуть должен быть единственным, без разветвлений.Насыщают этот путь потоком, величина которого равна минимальной пропускной способности составляющих его ветвей.Исключают из рассмотрения насыщенны светви,Повторяют операции пп. 1, 2, 3 до тех пор,пока окажется невозможным определить хотябы один путь из начала в конец сети.Определяют ве 1)ьцицы (узлы) сети, которыеможно достигнуть по ненасыщенным путям.1 холичество последних обозначим х, а количество узлов, в которые нельзя попасть цо цецясьцценны м путя м, - х.Ветви, имеющие своьд начала в х, я концыв х, образуют минимальное сечение (разрез)сети, которое определяет величину максимального потока. Последняя может быть найденалибо как сумма потоков, насьшьакнццх различные пути в соответствии с и. 2, либо каксумма величин пропускных способностей ветвей, образующих минимальное сечение.Схемы модели ветви МВ (см. фиг. 1) и индикатора насыщенности ветви ИНБ (см. фиг. 2) содержат элемент 1, моделирующий ветвь для решения задачи о кратчайшем пути с высокой разрешающей способностью, например с эквивалентом отрицательного сопротивления, нуль-орган 2 (индикатор тока, протекающего по ветви), ключ,3, схему И 4, счетчик б (цифровая линия задержки с регулируемым коэффициентом пересчета), триггерр б, схему И 7, диод 8, цнвертор 1 с:;ема НЕ) 9 и схему И 10.В устройст;о (см. фш. 3 и 4, кроме элементов МВ и 1111, с ояь индикационная схема11, по топологии повторяющая моделируемую сеть 12, ветвями которой, обозначенными пунктиром, являются схемы ИНВ; источник напряжения 18, изображающий логическую едини.5 цу; дополнительная модель ветви 14 (индикатор насыщенности сети); источник тока 15; триггер 1 б, схема И 17; измерительный счетчик 18; импульсная схема ИЛИ 19; формирователь (липця задержки) 20; схема И 21, 10 схема И 22, источник пцтания Е и резисторы 1 х диодно-лоьцческцх схем ИЛИ, образуемых в вершинах сети диодами 8 схем ИНВ прп их соединении между сооой.Устройство работает следующим образом.15 В исходном полокении во всех моделяхветвей МВ триггерь 1 б устанавливаются в нулевое положение путем подачи сбросового сигнала ня входы 23. Сигнал с нулевых выходов триггеров по шине 24 поступает на вход 20 253035 4050 55 60 65 схемь 1 И 4 и удерживает кльочи 8 в замкнутом состоянии.В счетчики 5 заносятся количества пмпульсог, моделирующие в дополнительном коде величины пропускных способностей ветвей. Если одновременно с задачей о максимальном потоке задача о кратчайшем пути на той же сети не решается, то величина напряжения элемента 1 может быть установлена произвольной. В противном слу:яе она хстянавливаетсяпропорццональноц продолжительности ветви задачи о кратчайьцем пути. При отсутствии тока в ветви а - б вььходной сигнал нуль-органа 2 подает по шине 25 запрещающий потенциал на вход схемы И 4.Схемы моделей ветвей МВ (см. фиг, 1) перед решением задачи соединяются между собой полнсами а ц б в соответствии с топологией сети. Полосы 2 б (входы схемы И) объединяются по всей модели. К образовавшейся цецц подклочается еше одна модель ветви 14, длцця которой в масштабе напряжений больше самого длинного пути в сети, и источник тока 15. Ток последнего потечет цо крат ьайшему пути сети. Так как в качестве элементов 1использованы схемы с эквивалентами отрицательных сопротивлений, схема И 4 будет обладать высокой разрешающей способностью и выделит единственный путь без разветвлений. В моделях ветвей этого цутц потечет ток источника 1 б, сработают нуль-органы 2 ц подадут разрешающие потенциалы на схемы И 4 чо шшьам 25Сигнал пуска модели, цодацньш па вход 27, установит триггер 1 б в единичное состояние, выходной сигнал этого триггера откроет схему И (вентиль) 17 ц импульсы тактового генератора, подклоченного к гочке 28, начнут поступать в измерительный счетчик 18 и на входы схем И 4 моделей ветвей. Зтц импульсы, изображающие единицы потока, пропускаемого по сстц, начнут заполнять счетчики 5 ветвей ьыбранцого кратчайшего пути. Число этик импульсов будет соответствовать величине потока, пропускаемого по выбранному пути. В тот момент, когда величина потокаходом первой схемы И, входы ее служат входами соответственно импульсов тактового генератора и сигнала пуска, первый выход триггера соединен с первым входом второй схемы. И, второй вход которой соединен через,формирователь с выходом схемы ИЛИ, а третий служит водом импульсовго генератора, входы схемы ИЛИ соединены с выходными полюсами индикаторов насыщенности индикационной схемы, а также со вторым выходом триггера, выход второй схемы И соединен со входом измерительного счетчика и с третьими полюсами моделей ветвей, четвертые полюса которых соединены с третьими полюсами соответствующих индикаторов насыщенности ветвей индикационной схемы, входной полюс индикационной схемы соединен с источником единичного напряжения, промежуточные ее полюсы также соединены через резисторы с источниками напряжения.2. Устройство по п, 1, отличающееся тем, что в нем модели ветвей состоят из элемента, моделирующего ветвь для решения задачи о кратчайшем пути, вход которого служит первым полюсом модели ветви, нуль-органа, вход которого соединен с выходом упомянутого элемента, схемы И, счетчика, триггера и ключа, один вход которого соединен с выходом нуль-ограна, другой - с выходом триггера, а выход - служит вторым полюсом модели ветви, причем первый вход схемы И соединен с выходом нуль-органа, второй - с выходом триггера, а третий - служит третьим полюсом модели ветви, выход схемы И со единен со входом счетчика, выход которогосоединен со входом триггера, выход триггера служит четвертым полюсом модели ветви. 3. Устройство по пп. 1 и 2, отличаюшееся 15 тем, что в нем индикаторы насыщенности ветвей выполнены в виде схемы И, одни входы которых соединены между собой и служат первым полюсом индикатора, и инвертора, вход которого через диод соединен с выходом 20 первой схемы И и служит вторым полюсоминдикатора, а выход соединен со вторым входом другой схемы И, выход которой служит выходным полюсом индикатора, причем второй вход первой схемы И служит третьим 25 полюсом индикатора.271908 Составитель Л. Б. ДмитриеваИ. Андреева Техред Т. П. Курилко Корректор И. С. Хлысто Редакто Типографии, пр. Сапунова,аказ 2423, О1.1 НИИ 1 Р 1 Коми Тираж 480 Подписное а по делам изобретений и открытий прп Совете Министров СССР Москва, Ж, Раушская наб., д. 4,5