Многие проблемы управления и проектирования сводятся к задаче построения маршрутов специального вида в графах. Вид маршрута определяется заданными локальными и/или глобальными ограничениями. В монографии изложены подходы к решению подобных задач. Основной акцент сделан на случай плоских графов. Предложен способ представления гомеоморфного образа плоского графа, позволяющего эффективно решать задачи маршрутизации на компьютере. Формализован ряд возможных технологических ограничений: упорядоченное охватывание, А-цепь, самонепересекающаяся цепь. Даны полиномиальные алгоритмы построения маршрутов, удовлетворяющих указанным ограничениям, и оценка количества таких маршрутов. Предложенные алгоритмы могут быть применены в проектировании программ вырезания деталей по заданному раскройному плану с исп...
Mnogie problemy upravlenija i proektirovanija svodjatsja k zadache postroenija marshrutov spetsialnogo vida v grafakh. Vid marshruta opredeljaetsja zadannymi lokalnymi i/ili globalnymi ogranichenijami. V monografii izlozheny podkhody k resheniju podobnykh zadach. Osnovnoj aktsent sdelan na sluchaj ploskikh grafov. Predlozhen sposob predstavlenija gomeomorfnogo obraza ploskogo grafa, pozvoljajuschego effektivno reshat zadachi marshrutizatsii na kompjutere. Formalizovan rjad vozmozhnykh tekhnologicheskikh ogranichenij: uporjadochennoe okhvatyvanie, A-tsep, samoneperesekajuschajasja tsep. Dany polinomialnye algoritmy postroenija marshrutov, udovletvorjajuschikh ukazannym ogranichenijam, i otsenka kolichestva takikh marshrutov. Predlozhennye algoritmy mogut byt primeneny v proektirovanii programm vyrezanija detalej po zadannomu raskrojnomu planu s isp...
