Устройство для решения задач на графах

сооз согстскихСО ИАЛИСТ ИЧЕСКИХРЕСПУБЛИК ЬО(1 и 5 О 06 Г 15/41 ЕНИЯ ТЕЛЬСТВУ истровой,(54) УСТР НА ГРАФ (57) Изобр ВОД ЕШЕНИЯ ЗАДАЧ Хтение отьной теоваия осится нике и кибернетике и редназначено нии задач комграфах. Цель роиства и расых возможно.едения блока ьчислитег для испольбинаторноиизобретени при реше зации на щенис уст оцтими УпРОш менова Известно ния кратчайш щее блок фо управления, ф тервала, логи адресов верш ляет определ ленного ран пути и циклы ствие,тва за цикло ГОСУДАРС ГРЕГСЫЙ КОМИТЕТПО ИЗОЕРЕГЕИИЯМ и ОТКРЫТИЯМПРИ ГК) СССР ОПИСАНИЕ К АВТОРСКОМ/ СВИД(56) Авторское свидетельство СССМ 485451, кл, 6 06 Е 15/20, 1971.Авторское свидетельство СССМ 1462352, кл, 5 06 Е 15/20, 1987 ие его Функциональн достигаеся путем в Изобретение относится к кибернетике и вычисли тел ьнои технике и пред азначео для использования при решении задач комбинаторной оптимизации на графах. устроиство для моделироваих путей на графе, содержармирования топологии. блок ормирователь временного инеские элементы и задатчики ин, Это устройство не позвоять кратчайшие пути опредега, а также гамильтоновыи имеет низкое быстродейНаиболее близким к предлагаемо ледует считать устройство, содержащее г ератор импульсов, блок управления, бл формирования корневой вершины и синхронизирующих сигналов, блока задния матрицы весов ребер, блоков формирования путей, блоков выделения направлений, блоков фиксации путей, блоков Формирования гамильтонова цикла, блоков суммирования и бгоков выбора минимума, Сущность изобретения состоит в том, что при выделении направлений передачи путей и их промежуточной Фиксации формирование путей различных рангоь к Одчои вершиР происходит в Одном блоке, что уменьшае 1 число блоков формирован,я путей, ,рокв того, введение блоков выбора мини;лума псзвгляет определять минимальные веса путей и циклов, что расширяет Функц 1 оная нье возможности ус;рой;тва зыкч Очаюциес;, в способности Огределя ь крат айли-. -ути различного р:",га, а г 1 кж гамиль 1 ооспутициклы, 1 ил. шин и блок мариОй лодели дерева путей графа.Недостатками известного являются его сложность и ограниченные Функциональные возможности, заключающиеся в неспособности определять кратчайшие гути определенного ранга, а также гамильт)новы пути и циклы,Необходимость определения кратайших путей различного ранга, а также гамильтоновых путей и циклов возникает при решении таких задач как оптимальное упорядочение обьектов, маршрутизация сообщений, нахождение оптимального порядка обработки деталей и дрЦелью изобретения являе;ся расширение функциональных возгложностей устройс счет определения кратчайцих и пей и в определенного ранга.Поставленная цель достигается тем, чтов устройство, содержащее генератор импульсов и блок переименования вершин,введены блок формирования корневой вершины и синхронизирующих сигналов, блок 5задания матос 1 цы весов ребер. (В - 1) блокформирования путей, сде В - количессовершин е графе, (В - 1) блок выделениянаправлений, (В - 1) блок. фиксации путей,,В 1) блок фоомированцся гамильтоноеа 1 Оцикла, (В - 1) блок суммирования и В блоковвыбора минимума, Выход тактовых импульсов генератора импульсов подклочен к входу блока формирования корневой вершинь.и синхронизирующих сигналов, выход корневой вершины котсрого подключен к входублока задания матрицы вес,ов ребер,входуэка и еяг ИР вериь 1ХГ. у коревсв, шинь цзждсгсз блока формирсвання путей а выходы синхронизирующих 20.гналов и;:оес; и. и путей и по"ученкя вепч-ей блока формирования копневоЕОП ЯНЬ И С П ХРС;НИ;ПУЮЩИХ СИСНаЛОВчоД ",ючены к сРавлян;.1 м вхоцам с Оот-т венно каждого блок фиксации путей и 25"алого блока суммировэнс я.Выход свЯзей вепш 1 н блока заданиЯэиц, а-ссв ОеГ р ссединен с входамизадания г,1 дй Крала каждого блокаферми,ования пут й," яц дами задания на-,1 пправлений передачи пу 1 ей К-го ранга каждого блока выделения направлений, свходами задания цикла каждого блока формирования гамильтонова цикла и с входамизацания весов путей К-го ранга каждого блока уммирования, где К = 1. (В - 1),По каждому входу задания путей , гооанга, каждому входу задания направлен 1"передьчи пуей К-го ранга, каждому вхсзадания цикла и каждому входу задания с 1 Осое путей К-го ранга гередается информц яосвязях-ол-косвоей вершины, Выходьномеров верши блока псоеименованиятер,дин г дключены к входам своеи вера:НЫ ССОЕЕтСтвуЮщИ бСКОВ фарМИрс.еа с1путей, Выход сформированных пут.й К-соранга;саждого блока формирлваниг путейподключен к информационному вход соответствующего блока выделения напраппсний. Выход выбранных напр лений 59передачи путей К-го ранга 1 ь 1-со блэка выцеления направлений де Л =- 1,(В . подключен к Уе му входу спссцусп ос ги пу-,иК ГО оанга каждого блок фс 1 ксапи пут 1где е (Р 11-Вьход За тикс;и,.в.,ранга ка:, до, э блока фг,кс:; пи пув подключенвходу перечня "ч,шич ужин те 1К-го ранга соо 1 ветс, эссег блска форлРовдНИЯ ПУТЕИ И ВХОД пв 1 ЕЧПЯ СС-ОСПц; ВО их путей К-го ранга соответствующего блока суммирования, Выход зафиксированных гамильтоновых пу 1 ей каждого блока фиксации путей подключен к информационному входу соответствующего блока формирования гамильтонпва цикла, выход перечня вершин цикла которого подключен к входу перечня веригин цикла соответствующего блока суммирования.Выход результата определения сумм каждого блока суммирования подключен к входу соответствующего блока выбора минимума, а выход веса цикла каждого блока суммирования подключен к соответстсующему вхоцу последнего блока выбора минимума. Выход результата опрецеления минимума весов путей каждого, кроме поглес 1 него, блока выбора минисума сот динен с входом иденификации вершин пути соот нетсгвующего блока фиксации путей и входом идентификации вес пути соответствуящего блока суль 1 И;.:ванс 1 я Яход результата опредее;,ч ми имальпсго веса цикла последнего блока выбора ми иьума подключен к входу идентификации вершин цикла каждого блока формирова ия гамильтонова цикла и входу ,д.=нтифн ации веса цикла каждого бтсока сул 1 л 1 ирования, Выходы кернВОЙ вершины и номеров вершин имею разрядность максимально;о номера вершины в гра, каж дьй из входов задания путей К-:о ранга, задания направлений г;ередачи путей К-со ранга, задания цикла и задания весов путей К-го ранга имеет разрядность последовательности весов ребер, связываюьцих сдну лерсничу графа с остальными Кж,час из акодсв пере ня вершин чужих и ссоих путей К-со ранга информационных вхсдон блсков оыдспения направлений и блпков фрмирования гамнльтонова цикла каждый иэ входов совокуг;ности путей К-го раиса ил 1 еет р; зрядносгь соследовательности вершин, обое.,у ссух пити (В - 1)-го ранга, Выходычределэюя сумм имеют разрпдн, С Ь СООтВЕтетвуСЭщуЮ раэрядНОСтИ вс".ое пуссЙ (В - 1)-го ранга, каждый выход пс:речня черс;Йч цила имеет разрядность псследовательности номеоов вершин, образуют,их гуть Р-гс ранга а каждый выход геса цикла имеет разрядность, соответствующую ра ряднос-и веса пути В-го ранга.1".иеденньс 1 блок формирования корневой вершин. и 1 нхронизиррощих сигналов г редназнз :, ,;л записи номера ссрнс.вой вер;сичо, в, цачи управляющих импуп сов на блокс фиксации путей и суммирова и: . Етвден ый . 1 ок задания,1 атрицы весов ребер служи- для записи весов ;Обс еинясцс дую вершину гра 1705841фа с остальными вершинами, Введенные блоки формирования путей предназначены для формирования путей различнык рангов к соответствующей вершине в виде перечня вершин, начиная с корневой, Введенные блоки выделения направлений обеспечивают передачу информации о путях (перечни номеров вершин) на те блоки фиксации путей, номера которых соответствуют номерам вершин, имеющим связь с последней вершиной сформированного пути и не встречавшимся ранее в перечне номеров вершин этого пути.Введенные блоки фиксации путей служат для передачи информации о путях, поступившей на них с различных блоков выделения направлений, на свои блоки формирования путей, а также выдачи перечня вершин, составляющих пути различного ранга, в том числе и гамильтоновы, на свои блоки суммирования и формирования гамильтонова цикла Введенные блоки формирования гамильтонова цикла предназначены для формирования гамильтонова цикла в виде перечня вершин Введенные блоки суммирования служат для получения весов путей и циклов, Введеннье блоки выбора минимума предназначены для определения меньшего по весу пути (цикла) среди всех путей различного ранга (циклов), в том числе и гамильтоновых, к каждой вершинеСущность предлагаемого решения состоит в том, ч го при вьделении направлений передачи путей и их промежуточной фиксации формирование путей различных оа:гов к одной вершине происходит в одом блоке, что уменьшает число блоков формирования путей с В до 4 В. Кромеого. введение бло 2ков выбора минимума позволяет определять минимальные веса путей и циклов, что расширяет функциональные воэможости устройства, заключающиеся в способности определять кратчайшие пути различного ранга, а также гамильтоновы пути и циклы,Возможность достижения положительного эффекта подтверждается тем, что введение блоков формирования корневой вершины и синхрониэирующих сигналов, задания матрицы весов ребер формирования путей, выделения направлений, фиксации путей, формирования гамильтонова цикла, суммирования, выбора минимума и обусловленных ими связей позволяют упростить устройство и расширить его функциональные воэможности. На чертеже представлена функциональная схема устройства для определения путей и циклов в графе. устройство для определения путей ициклов в графе содержит генератор 1 импульсов. блок 2 формирования корнвойвершины и синхрониэируюших сигналов,5 блок 3 задания матрицы весов ребер, бгок 4переименования вершин, блоки 5 1 .5 (В -- 1) формирования путеи, блоки 6.16.(Е - 1)выделения направлений, блоки 7 1,(Е 1)фиксации путей, блоки 8. 18 (В - 1) форми 10 рования гэмильтонова цикла, блоки9.19.(В - 1) суммирования. блоки10,1.,10.В выбора минимума, выход 1 тактовых импульсов, выход 12 корневой вешины, выход 13 синхронизирующих сигналов15 пересылки путей, выход 14 синхронизирующих сигналов получения весов путей, выход15 связей вершин, выходы 16,116(В - 1)номеров вершин, входы 17.1,17.(В - 1 перечня вершин чужих путей К-го ранга в оды20 18,1,18 (В - 1) задания путей К-го ранга,выходы 19.1 .19.(В - 1) сформированных путей К-го ранга, входы 20,1, 20.(В - 1) заданиявправленй передачи путей К-го ранга,выходы 21.121,(В - ) выбранных направ 25 лений передачи путей К-го ранга, входы с22,1.122,(В - 1), по 22 1.(В - 1).22 (В -- 1),(В - 1) совокупности путей К-го ранга,выходь 23 1 .,23.(В - 1) зафиксирова ныкпутей К го ранга аьходь 24.24(3 1)30 зафиксированныхамильтоновцх пей,входы 25,1 25.(В - 1) задаия ци;л: воды26 1,26 (В - 1) идентификации верши, икла, выходы 27.127.(В - 1) пе еня всрш,нцикла, входы 28,1,. 28 (Р - 1) задания в.сов35 путей К-го ранга, входь 29 1 .29(В 1 и- речня вершин свои; утей К-о ранга, в о,ь30 130 (Е 1 иден;ифкации веса кла,выходы 3 31,(Я - 1) реэ"льтата определения сумм. вь ходы 32.1,. 32.(В 1, веса40 цикла, выходы 33,1, 33,(В - 1) результатаопределения минимума весов путей, вход34 результата определения минимума зесацикла,Генератор 1 импульсов подает на ;код45 блока 2 формирования корневой вершины исинхронизирующих сигналов последовательность тактовых импульсов, управляющих паботой блоков устройства. Блок 2формирования корневой вершины и синхро 50 ниэирующих сигналов управляет раб.тойблоков 3, 4, 7,1,7,(В - 1), 9.1.,9.(В - 1) ислужит для записи номера корневой вешины. Выход 12 корневой вершины подкл.ченк входу блока 3 задания матрицы восоре 55 бер, входу блока 4 переименования вершини входу корневой вершины каждого 6 ока5.15.(В - 1) формирования путеи, В ыхсд 13синхронизирующих сигналов пересылки путей блока 2 соединен с управляющим входом каждого блока 7.17,(В - 1) фикс;ции1 у гей, а выход 14 синхронизирующих сигналое получения ессое путей - с управляю;ц;м входом каждого блика 9.19.(В - 11 суммироеачия Блок 3 задан л глатрицы весов т)ебер пргз 7( аз гзчг;н,(11 гг хоан нля 1 выдачи и;1(орлаи О сглзя): е(;е .:ерши г)афа ме)кду гэобо: Выхсгд 15 саязей еери 1 г бло к 3 рас э,;,1.ъ)ен по еходал( 18.1 .8 (В 1) зац гн)ля Нуей к 1 О ранга бло),ое 5 1, 5 (Р -1,ирг;ИрОЕ )НИЯ Путвй, Екг)даы 10 201,.20.1 тВ 1) задания на)равленй пере д;гч; путеи Л ги рана блоков б 1,6,Рг 1; ВЫдг. ЛЕ;ИЯ а ораелвг Лй: ХОдагх 25.1,25 (В - ) (37)аг)я Ои и г лс:;Ое,л; пуКй 1 т) Гг.-. гга бло,ов 5 подклочены .эИНфОР; ( Ог ЫМ ВХОДаМ СООГВтзтегРО 1(и; блокс, б 1 .6.)В 1) выделения аправгОний, к,торые гэбеспечиваОт гередачу информации о и;тях на те блоки фиксации и )ей, номера к. эрых соответствуют номе 35 (аМ ВЕРШИН,г)е ОЩИМ СВЯЗЬ С ПОСЛЕД Ей. рШИНОй ГфОр ЛирОВаННОГО Пугт И НЕ есгречавши ся расе е перечне но ерс.Л ЗРШИ 1 Зти)то ЦУГИВыходы 21 1 21(В - 1) выбранных 1)в б подключ(ль к входам с 22,1.1 22.(В1 1 о 22,1 В 1) 22 (В . 1).(В - 1; сгэв- .УНОСтг ц, тЕй К (С раНа бЛОКОЕ 7 1 7 (Гфиксгции и;тей при этом вы;гд 24, ,лпреде;)е 1 по зходам 22 1,1 .22(В - 11,нход 21,2 г о входал 22,2,1 . 22,2 (В - 1) , т СБлоки 7,1, ", (В 1) фиксации п, й сжаг для передачи информации о путях, :гг СтуПИВШЕй На ИХ С раЗЛИЧНЫХ бЛОКСЕ выделения направлений, на свои блики ( ор.мироеания путей а также вь)дачи перечня ОЕРГВИН, ГОСтав" ЯЮЩИХ ПУТИ Раэ,(ЛгНГ)тг) ")янга. в тсч л члслг и гаклильтоновы, на (,ео б оки сумми)-сев 11 Я л (1 гэлл(л;)О(1:11 глчамилынот)а .1,)к л аВ(ходы ,)1,1, 23,( 11 зафисг(гэа 1 г нег)тей К г,г Оа 11 г) г гоое 7 (Ода лг;:;е"элам 17 17.(1 11 пеоеч) Я , 111"г чужих путей К го ранга соответствующихблоков 5 1. 5.(В - 1) формирования путей ик входам 29 129 (В - 1) перечня вершинсвоих путей К-го рана соответствующихблоков суммгирования 9.19,(В 1), а выходы 24 1 24 (В 1) зафиксированных гамильтонов:х пугеи блоков 7 подкло ены кинформационным входам соотее;(,теуощихбл)кое 8,1 8.(В - 1) ф(. рллироеанля амильтпноед цика,БЛОКИ СУММИРОеаНИЯ П 1)ЕДНаЗНачЕНЫДЛЯ ПОЛУЧЕНИЯ ВЕСОВ ПУтвй РаЗЛИЧНЫХ РаНгое и циклов, их выходы 31,1,31,(В - 1)1 эезультатя огределения суллтл подключеык входам соо ветствующих блоков1 Г) 1 10,(В 1) еыбсргз инимума, а еы)оды32 1,.32,(В - 1) веса цикла всех блокэе 9.1 глл еходалл блока 110 Г 1 выбора мини)умаБлоки формированияамильтоноеа цикла. / 1, х I (В " 111 еречня вере)ин ц;г га цод.гЮ)ЕНЫ К ЕХОдаЛ", ПЕрв(НЯ ВЕрВИг цИКЛасс)отег; гвующих блоко(з 9,1,9,(В - 1) сулллИРОВВНИЯ.Блоки выбора мин лллулла г)редназначедг 11 О,рвдЕЛЕНИя МЕН ШЕГО ПГ НЕСУ Пути(. кла).редл всех путей разлчноги рзнга(ц;гг:,гС(г), Е тОМ ЧИСЛЕ и аЛЛЛЬтОНОВЬХ. ВЫ); гч 33,133 (В - 1) резльтата определе.г;Я минимума весов ц 1 тей блоков10. 1).,10,(В - 1) выбора минимума подключены к входам идентификации вереин путисоответствующих блоков 7 фиксации путей1 ВХОДаМ 1 ДЕтИфИКаЦЛЛ ВЕСа ПУ)И СОг)1 Ввттвующих блоков 9 су 1;ироваг 1 Я. Выхсд 34,;езультета определения минимального веса111(ла блока О,В выбора минимума соедигг 11 с входами 26,12 б,(В - 1) соответстеую.и:х блокОе 8.18.(В - 1) фоРмиРОегниЯг;-;лидьтонтгеа цикла и входали 30 1 30.(В -:; ицентифции еса цикла соответ(.тву;них б оков 9 1 9,(В - 1, суллмирования.ход 1(л 1 гэло,. егци в блоке 2 записе)1 11;мер сорневс)и вершины, в блоке 3записаны ееа ребер всех смежных вершин,е блоке г записаны нолера всех вершин,Устоойстес для определения путей ицилов е графе работаст следующим обраЗом.По первому тактсеомтт импульсу с генеоатора 1 ноллер корневой вершины из блокагоступает на блс)ки 3 задания матрицые)(Ое ребер блок 1, ереименования верн )н и блоки 5.1.1(Р 1) формиров;)ния1)утЕ В бЛС,Н. Л ПРОИС: .(Ит ПЕрЕраСПрЕдЕлние нг)г еров верши, (номер корнвойееги н. Нсклпав) .я, я на его месте црис,);. (ганг) номер и-; . зй вершины В; ес 170584155 ли корневая вершина - В, то перераспределения не происходит) и эти номера с выходов 16.116,(В - 1) поступают на соответствующие блоки 5.1.5.(В - 1) формиоования путей О блоке 3 присходит перераспределение связей вершин графя в соптве;ствии с перераспределением номеров вео вин в блоке 4 и связи каждой(кроме вторн:ой) вершины (веса ребер, соед няющих в;-ршпну с остальными вершинами графа; если связи нет, то на месте веса ребра передается О") выдаются в соответсгвующие блоки 5 15 (В - 1) формирования путей, блоки 6.1 .,6.(В - 1) выделения направлений, блоки 8,18,(В - 1) формирования гамил тонова цикла и блоки 9,19,(6 - 1 суммированияВ блоках 5, нержины которых имеют связь с корневой вершиной, формируются пути первого ранга. которые с выходов 19 поступают в саотвнтс 1 вующие блоки 6 выделения направлений. В этих блоках учитыва. ется, что путь пгошел уже через две вершины и цикл не должен образоваться ;т,е. дважды через одну вершину путь не должен пройти), а также определя отся вершины, с которыми;.вязана последняя (вторая) вср. ина пути, чтобы образовать пути второго ранга) и после этого пути первого ранга иэ блоков 6 передются в соответствующие блоки 7 фик.ации путей. Затем нз каждого бгпка ". по поиходу сигналл с выхода 13 блока 2 путь первого ранга к своей верцнлне 1 ередаетс н соответствующий блок 9 суммирования,; ос гальные пути первого ранга к чужим вероивам передаются на соответствующий блок 5 формирования путей.В блоках 8 суммирования по сигналу с выхода 14 блока 2 происходит определение веса пути 1 ервого ранга. Это вес передаетсч чв соответствуя)ший блок 1., ьыбор ми" нимума и определяе 1 ся там как минимальный (путь первого ранга к каждой вер вине может быть только один), а сигнал с выхода 33 результата определения минима ьных весов путеи позволяет зафиксировать этот путь в блоках 7 (перечень вершин пути) и 9 (вес пути), Б блоках 5,1,5,(В - 1) формируются пути второго ранга, которые через блоки 6.16.(В - 1) выделения направлений передаются на соответствующие блоки 7,17.(В - 1) фиксации путей, а из них - опять на "свои" блоки 5 формирования путей, где формируются пути третьего ранга, и "свои" блоки 9 суммирования и 10 выбора минимума - определяются кратчайшие пути второго ранга (в блоке суммирования определяются веса путей, а в блоке выбора минимума находится меньший из этих весов),5 10 15 20 25 30 35 40 45 50 Таким образом, при одном цикле работы устройства определяются кратчайшие пути какого-то ранга к каждой вершине, На (В - 1) цикле в блоках 5 формируются гамильтоновы пути, которые также через бло-. ки 6 передаются в блоки 7, а из них в блоки 9 и 10,110,(В - 1) - определяются кратчайшие гамильтоновы пути.Кроме того, гамильтоновы пути иэ блоков 7.1.7.(В - 1) фиксации путей передаются а соответствующие блоки 8,1,8.(В - 1) формирования гамильтонова цикла, в которых определяется наличие связи между последними верьвинами гамильтоновых путей и корневой вершиной и при наличии такой связи сформированные гамильтоновы циклы в виде перечня вершин передаются в соотг ветствующие блоки 9,19.(В - 1) суммировачия, где определяются веса гамильтоновых циклов. Веса циклов передаются нв блок 10,В выбора минимума, где определяется цикл с минимальным весом и идентифицирующий сигнал об этом с выхода 34 блока 1 О,В передается на соответствующий блок 8 формирования гамильтонова цикла (фиксируется перечень вершин цикла) и соответствующий блок 9 суммирования (фиксируется вес цикла), устройство зачершает работу.Гехнико-зкономическая эффек ивность предлагаемого изобрстения .включается в том, что возможность определения кратчайших путсй различного ранга а также гамильточодых путей и цикл;в позволяет с высоким быс-,родейстнием решагь большой к,асс задя, имеющих:. оакти еское примен:нио в различных оба-,тх ,вычислительные сисгемы и сети, транспорт, системы управ. ения и др.1. Крогле того, изобретение проще по сравненио с прототипом, .ак как уменьшено число блоков формирования пуртей с В до 4 В и уменьшено число связей между блокамл.Положительный эффект, который может быть достигнут при использовании предлагаемого изобретения по сравнению с прототипом, состоит в том, что повышается гибкость и эффективность управления вычислительными сис 1 емами и сетями Э В М. Формула изобретения Устройство для решения задач на графах, содержащее генератор импульсов и блок переименования вершин, о т л и ч а ющ ь е с я тем, что, с целью расширения функциональных возможностей устройства путем определения кратчайших путей и циклов определенного ранга, в него введены блок формирования корневой вершины исинхронизирующих сигналов, блок задания матрицы весов ребер, (В - 1) блок формирования путей, где В - количество вершин в графе, В - 1 блок выделения направлений, В - 1 блок фиксации путей, В - 1 блок формирования гамильтоновых циклов, В - 1 блок суммирования и В блоков выбора минимума, причем выход генератора импульсов подключен к тактовому входу блока формирования корневой вершины и синхронизирующих сигналов, выход номера корневой вершины которого подключен к одноименным входам блока задания матрицы весов ребер блока переименования вершин и всех блоков формирования путей, выходы синхронизирующих сигналов пересылки путей и выходы получения веСов путей блока формирования корневой вершины и синхронизирующих сигналов подключены к управляющим входам всех блоков фиксации путей и всех блоков суммирования соответственно, выход связей вершин блока задания матрицы весов ребер подключен к входам задания путей К-го ранга всех блоков формирования путей (К = 1 В - 1), к входам задания направлений передачи путей К-го ранга всех блоков выделения направлений, к входам задания цикла каждого блока формирования гамильтонова цикла и к входам задания весов путей К-го ранга каждого блока суммирования, выходы номеров вершин блока переименования вершин подключены к входам одноименных вершин соответствующих блоков формирования путей, выход сформированных путей К-го ранга каждого блока формирования путей подключен к информационному входу соответствующего блока выделения нап равлений. выход выбранных направлений пере дачи путей К-го ранга М-го блока выделениянаправлений (М = 1 В - 1) подключен к М-му входу совокупности путей К-го ранга всех блоков фиксации путей, выход зафиксированных путей К-го ранга каждого блока 10 фиксации путей подключен к входу перечнявепшин ччжих пчтей К-го оанга соответствчющего блока формирования путей и к входу перечня вершин своих путей К-го ранга соответствующего блока суммирования, вы ход зафиксированных гамильтоновых путейкаждого блока фиксации путей подключен к информационному входу соответствующего блока формирования гамильтонова цикла, выход перечня вершин цикла которого под ключен к одноименному входу соответствующего блока суммирования, выход суммы каждого блока суммирования подключен к информационному входу соответствующего блока выбора минимума, выход результата 25 каждого иэ которых (исключая В-й) подключен к входу идентификации вершин пути соответствующего блока фиксации путей и к входу идентификации веса пути соответствующего блока суммирования, выход ре эультата В-го блока выбора минимумаподключен к входам идентификации вершин цикла всех блоков формирования гамильтонова цикла и к входам идентификации веса цикла всех блоков сум мирования,1705841 оставитель В Певнеехред М.Моргентал Реда кто орректор Т, Патай овск оизводственно-издательский комбинат "Патент" г. Ужгород, ул.Гагарина. 1 каз 195 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5