Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности

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