Центры транспортного тяготения

Для этой задачи имеются две основные постановки. Задача отыскания прямолинейных связей заданных центров тяготения с запретом выбора других направлений сети или, иначе говоря, с запретом образования узлов ТС вне заданных центров транспортного тяготения (задача Прима). Задача отыскания прямолинейных связей заданных центров тяготения с возможностью образования неограниченного количества узлов, не совпадающих с заданными центрами Транспортного тяготения (обобщенная задача Штейнера). Задача Прима имеет простые и удобные для практики графические и вычислительные методы решения, которые сводятся к использованию двух принципов: 1) прямолинейной связи любого изолированного центра тяготения с ближайшим соседом; 2) кратчайшей прямолинейной связи любого изолированного фрагмента сети с ближайшим центром тяготения, еще не вошедшим в сеть. Фрагментом сети называют любое, связанное прямыми звеньями подмножество центров тяготения (в простейшем случае — два центра тяготения, связанные прямолинейным звеном) на еще недостроенной сети.

Принцип 1 используют обычно только для получения простейшего изолированного фрагмента в виде oтрезка, соединяющего два ближайших центра тяготения, а принцип 2 — для расширения его до полного построения кратчайшей ТС. Принцип 1 используют обычно только для получения простейшего изолированного фрагмента в виде oтрезка, соединяющего два ближайших центра тяготения, а принцип 2 — для расширения его до полного построения кратчайшей ТС.