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

 

О П И С А Н И Е 21I908

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 27Л.1969 (№ 1307034/18-24) Кл. 42m4, 7/48 с присоединением заявки №

Комитет по делам изобретений и открытий при Совете Министров

СССР

МПК G 06g 7/48

УДК 681.33.001.57 (088.8) Приоритет

Опубликовано 26.Ч.1970. Бюллетень ¹ 18

Дата опубликования описания 9.1Х.1970

Автор изобретения

В. В. Васильев

Институт кибернетики АН Украинской ССР ", - ИЛОВ

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О МАКСИМАЛЬНОМ

ПОТОКЕ В СЕТИ

Изобретение относится к области вычислительной техники; оно может быть использовано для расширения возможностей комбинированных специализированных машин при решении задачи о максимальном потоке в сетях.

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

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

Выходной полюс этой модели ветви соединен с одним из входов триггера, другой вход которого соединен с выходом первой схемы

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

Входы схемы «ИЛИ» соединены с выходными полюсами индикаторов насыщенности индикационной схемы, а также со вторым выходом триггера, выход второй схемы «И» соединен со входом измерительного счетчика и с третьими полюсами моделей ветвей, четвертые полюса которых соединены с третьими полюсами соответствующих индикаторов насыщенности ветвей индикационной схемы, входной полюс индикационной схемы соединен с источником единичного напряжения, а промежуточные ее полюсы также соединены через резисторы с источниками напряжения. Кроме того, в предложенном устройстве модели ветвей состоят из элемента, моделирующего ветвь для решения задачи о кратчайшем пути, вход которого служит первым полюсом модели ветви, нуль-органа, вход которого соединен с выходом упомянутого элемента, схемы «И», счетчика, триггера и ключа, первый вход которого соединен с выходом нуль-органа, второй — с выходом триггера, а выход последнего — слу жит вторым полюсом модели ветви, причем первый вход схемы «И» соединен с выходом нуль-ограна, второй — с выходом триггера, а третий — служит третьим полюсом модели ветви, выход схемы «И» соединен со входом счетчика, выход которого соединен со входом триггера, выход триггера служит четвертым

271908 полюсом модели ветви. Ийдикаторы насыщенности ветвей состоят из схемы «И», одни входы которых соединены между собой и служат первым полюсом индикатора, и инвертора, вход которого через диод соединен с выходом первой схемы «И» и служит вторым пол(осом индикатора, а выход соединен со вторым Входом другой схемы «И». Выход последней служит выходным г(олюсом индикатора. причем второй вход первой схемы «И» служит третьим пол.осам индикатора.

3TII OT,lIl fIIH УСтРОйетВа сить его точность и разрешающу(о способность.

На фиг. I показана схема модели ветви (МВ); на фпг. 2 — схема индикатора пасьпценностп ветви (ИНБ); на фнг. 3 и 4 — два варианта схем предложенного устройства.

В основм работы предло>кенного усгронствя положен способ решения задач. вытекя(ощий из теоремы о максимальном потоке н минимальном сечении, сущность которого заключается в след (ощем.

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

Насыщают этот путь потоком, величина которого равна минимальной пропускной способности составляющих его ветвей.

Исключают из рассмотрения пасыщctlllhle ветви.

Повторяют операции пп. 1, 2, 3 до тех пор, пока окажется невозможным определить хотя бы один путь из начала в конец сети.

Определяют вершины (узлы) сети, которые можно достигнуть llo ненасыщенным путям.

Количество последних обозначим х, а количество узлов, в которые нельзя ttoIIHcTI> по lfeí;tсьпценны м путя м,— х.

Ветви, имеющие сг>он начала в х, я коп:(ы в х, образуют минимальное сечение (разрез) сети, которое определяет величину максима tl>ного потока. Последняя может быть найдена либо как сумма потоков, насьш(ак>щпх различные пути в соответствии с и. 2, либо как сумма величин пропускных способностей ветвей, образующих минимальное сечение.

Схемы модели ветви MB (см. фиг. 1) и индикатора насыщенности ветви ИНБ (см. фиг. 2) содержат элемент 1, моделирующий ветвь для решения задачи о кратчайшем пути с высокой разрешающей способностью, няприilep с эквивалентом отрицательного сопротивления, нуль-орган 2 (индикатор тока, протекающего по ветви), ключ 8, схему «И» 4, счетчик 5 (цифровая линия задержки с регулируемым коэффициентом пересчета), триггер б, схему «И» 7, диод 8, инвертор (схема

«НЕ») 9 и схему «И» 10.

В ycTpottcт;о (см. фш. 3 и 4 >, кроме элсмепТоВ МВ и 1 111., (х о. и индикационная схема

11, по топологии повторяющая моделируемую сеть 12, ветвями которой, обозначенными пунктиром, являются схемы ИНВ; источник напряжения 18, изображающий логическую единицу; дополнительная модель ветви 14 (индикатор насыщенности сети); источник тока 15; триггер 1б, схема «И» 17; измерительный счетчик 18; пъ(пульсняя схема «ИЛИ» 19; формирователь (липня задержки) 20; схема «И» 21, 10 схема «И» 22, источник питания E и резисторы R диодно-ло(ических схем «ИЛИ», образуемых в вершинах сети диодами 8 схем ИНВ прп их соединении между сооой.

Устройство работает следук>щим образом.

В исходном поло>кении во всех моделях ветвей МВ триггерь(b устанавливаются в нулевое положение путем подачи сбросового сигнала ня входы 23. Сигнал с нулевых выходов триггеров по шине 24 поступает на вход

65 схемы «И» 4 и удерживает клячи 8 в замкнутом состоянии.

В счетчики 5 заносятся количества пмпульсог, моделирующие в дополнительном коде величины пропускных способностей ветвей. Если одновременно с задачей о максимальном потоке задача о кратчайшем пути на той же сети не решается, то величина напряжения элемента 1 может быть установлена произвольной. В противном слу:яе она устанавливается пропорциональноц продолжительности ветви задачи о кратчайшем пути. При отсутствии то <я в ветви а — б выходной сигнал нуль-органа 2 подает по шине 25 запрещающий потенциал на вход схемы «И» 4.

Схемы моделей ветвей МВ (см. фиг. 1) перед решением задачи соединяются между собой полюсами а Il б в соответствии с топологией сети. Полюсы 2б (входы схемы «И») объединяются по всей модели. К образовавшейся не подключается еше одна модель ветви 14, длина которой в мясш(абе напряжений больше самого длинного пути в сети, и источник тока 15. Ток последнего потечет по крат (айшему пути сети. Так как в качестве элементов 1 использованы схемы с эквивалентами отрицательных сопротивлений, cxeма «И» 4 будет обладать высокой разрешающей способностью и выделит единственный путь без разветвлений.

В моделях ветвей этого пути потечет ток источника 15, сработают нуль-органы 2 и подадут разрешающие потеш(палы на схемы «И» 4 !

lO ш(II(ах(25

Сигнал пуска модели, поданньш Ila вход 27, у(тянов>гг триггер 1б в единичное состояние, выходной сигнал этого триггера откроет схему «И» (вентиль) 17 и импульсы тактового генератора, подкгпоченного к гочке 28, начнут поступать в измерительный счетчик 18 и на входы схем «И» 4 моделей ветвей. Зт>(импульсы, изображающие единицы потока, пропускаемого r!o CCT!(, начнут заполнять счетчик>(5 ветвей ьыбранного кратчайшего пути.

Числа этик импульсов будет соответствовать величине потока, пропускаемого по выбранному пути. В тот момент, когда величина потока

271908

55 б0

65 сравняется с. минимальной пропускной способностью одной из ветвей, образующих путь, счетчик 5 последней переполнится и сигнал переполнения по шине 29 установит трип ер 6 в единичное состояние. Сигнал выхода триггера, появившийся на выходе 80, будет в дальнейшем использован в качестве сигнала насыщенности данной ветви; одновременно оН же разорвет ключ и подаст запрещnþ.öèFI потенциал на схему «И» 1 по шине 24.

Таким образом, по крайней мере одна пз ветвей кратчайшего пути окажется разорванной, и модель кратчайшего пути выберет следующий кратчайший путь, состоящий пз ненасыщенных ветвей. До тех пор, пока не произойдет полное насыщение сети, модель будет работать аналогично. B момент насьпцения ток источника 15 переключится на самый длинный путь сети, состоящий из одной ветви 14.

Пропускная способность этой ветви становится равной нулю, поэтому на выходе 80 сразу появится сигнал, который установит триггер 16 в нулевое положение и остановит работу модели.

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

Индикацию ветвей сети, составляющих минимальное сечение (разрез), можно осуществить с помощью схемы, состоящей из индикаторов насыщенности ветвей, включенных в соответствии с топологией сети, причем выходы

80 схемы МВ должны быть соединены с соответствующими входами 81 схемы 11 (см. фиг. 3).

Диоды 8 при соединении ИНВ между собой вместе с сопротивлениями 1 и источником Е образуют схемы «ИЛИ», вклкгченпые в вершинах сети. На полюс Н индикационной модели схемы 11 подключается источник напряжения

18, изображающий сигнал логической единицы. На выходе 82 схемы «И» 10 появится сигнал принадлежности ветви минимальному сечению только в том случае, если вершина сети, к которой будет подключен полюс а, принадлежит множеству х, а вершина, к которой будет подключен полюс 6,— множеству. х.

Индикационные модели ветвей сети в целом могут быть выполнены как по позитивной схеме, так и по негативной логике. Поэтому рп описании работы схемы не копкретизнровались полярности источников напряжения Е, 18 и направления включения диодов 8.

Таким образом, схема 11, на пол1ос H которой подается сигнал логической единицы, может рассматриваться не только как индикатор ветвей минимального сечения, но и как индикатор насыщенности путей в сети. Сигналы логической единицы появятся в вершинах модели сети, которые можно достигнуть, идя пз начала сети 110 ненасыщенным путям. В вершинах модели сети, которые, идя по ненасыщенным

"5

40 путям, достппг ть нельзя, будут нулевые сигналы.

Характернои особенностью описанной модели является то, iTo точность и разрешающая способность ее полностью определяются цифровой частью системы, а аналоговая модель задачи о кратчайшем пути выполняет вспомогательную роль отыскания единственного пути, удовлетворяющего условию ненасыщенносп . Погрешности аналогoBcn модели, связа11пые с искажением длины ветвей в результате внутренних сопротивлений ветвей а — б, находящихся под током, не скажутся на pcIIIOIIII» задачи, если каждьш раз будет выделяться единствепныи путь.

Прп оппсашш работы устройства предполагалось, что переходные процессы в схеме, ооразующей ненасыщенный путь, оканчиваются за время, меньшее периода импульсов генератора тактовои IdoTOTbl. 3To накладыв IBT oiilIpделенные требования к быстродействию нульоргана 2 и ключей 8.

В том случае, когда в качестве этик элементов целесообразно применить низкочастотные элементы, в частности электромеханпческие, в схему управления модели необходимо ввести элементы задержки.

Реализация одного из возможных вариантов такого устройства показана на фиг. 4.

Формирователь (линия задержки) 20 осуществляет задержку разрешающего потенциала схемы «И» 22 всякий раз, когда срабатывает один из триггеров 6 моделей ветвей или пусковой триггер 16. Это обеспечивается с помощью импульсной схемы «ИЛИ» 19. на входы которой 88, 84, 85 подаются сигналы с выхода 30 моделей ветвей. На входы 86 и 87 подаются импульсы тактового генератора с некоторым сдвигом, чтобы осуществить синхронизацию пускового спп1ала на входе 2г и исключить явление «гонок» в схеме управления. B остальном работа схемы по этому варианту не отличается от работь1 описанных выше схем.

Предмет изобретения

1. Устройство для решения задачи о максимальном потоке в сети, содержащее модели ветвей, соединенные между собой первыми и вторыми полюсами согласно тополопш сети и образующие модель сети, ш1дпкаторы насыщенности ветвей, также соединенные между собой своими первым;1 и вторыми полюсамп согласно то 1олог1 п сеги и образу1ощпе индикациош1ую схему, источники тока и напряжения, триггер, с: смы «И» и «ИЛИ», формирователь и IIaiiepiire,"BFIBIiI счетчик, oTnu«IIIouieeca тем, что, с целью повышения точности и разрешающей способности устройства, в нем между начальным и конечным полосами модели сети включены параллельно источи:к тока и дополнительная модель ветви, служащая индикатором насыщенности сети, выходной полюс это" модели ветви соединен с одним из входа" триггера, другоп вход которого соединен с вы271008

8 ходом первой схемы «И», входы ее служат входами соответственно импульсов тактового генератора и сигнала пуска, первый выход триггера соединен с первым входом второй схемы. «И», второй вход которой соединен через,формирователь с выходом схемы «ИЛИ», а третий служит входом импульсов тактового генератора, входы схемы «ИЛИ» соединены с выходными полюсами индикаторов насыщенности индикационной схемы, а также со вторым выходом триггера, выход второй схемы

«И» соединен со входом измерительного счетчика и с третьими .полюсами моделей ветвей, четвертые полюса которых соединены с третьими полюсами соответствующих индикаторов насыщенности ветвей индикационной схемы, входной полюс индикационной схемы соединен с источником единичного напряжения, промежуточные ее полюсы также соединены через резисторы с источниками напряжения.

2. Устройство по п. 1, отличающееся тем, что в нем модели ветвей состоят из элемента, моделирующего ветвь для решения задачи о кратчайшем пути, вход которого служит первым полюсом модели ветви, нуль-органа, вход которого соединен с выходом упомянутого элемента, схемы «И», счетчика, триггера и ключа, один вход которого соединен с выходом нуль-ограна, другой — с выходом триггера, а выход — служит вторым полюсом модели ветви, причем первый вход схемы «И» соединен с выходом нуль-органа, второй — с выходом триггера, а третий — служит третьим полюсом модели ветви, выход схемы «И» со10 единен со входом счетчика, выход которого соединен со входом триггера, выход триггера служит четвертым полюсом модели ветви.

3. Устройство по пп. 1 и 2, отличающееся

15 тем, что в нем индикаторы насыщенности ветвей выполнены в виде схемы «И», одни входы которых соединены между собой и служат первым полюсом индикатора, и инвертора, вход которого через диод соединен с выходом

20 первой схемы «И» и служит вторым полюсом индикатора, а выход соединен со вторым входом другой схемы «И», выход которой служит выходным полюсом индикатора, причем второй вход первой схемы «И» служит третьим

25 полюсом индикатора.

271908

27

Составитель Л. Б. Дмитриева

Редактор М. И. Андреева Техред T. П. Курилко Корректор И. С. Хлыстова

Заказ 2423, 0 Тираж 480 Подписное

lIHliHfIH Комитета по делам изобретений и открытий прп Совете Министров СССР

Москва, 7К-35, Раушская наб., д. 4,5

Типографии, пр. Сапунова, 2