Решение задачи. Пусть все пункты, указанные на рис. 8.3, называются вершинами сети, а линия, соединяющая две соседних вершины

Пусть все пункты, указанные на рис. 8.3, называются вершинами сети, а линия, соединяющая две соседних вершины, - звеном. Незамкнутая сеть, связывающая две и более вершины с минимальной суммарной длиной всех соединяющих их звеньев, называется кратчайшей связывающей сетью. Данная сеть находится следующим образом. На транспортной сети (см. рис. 8.3) находят наименьшее звено. В данном случае звено К-Л = 2 км. Затем рассматривают все звенья, связанные с одной из своих вершин с выбранным звеном, т. е. звенья

К - М = 5; К - И = 2; К - 3 = 6; К - Ж = 7; Л - Ж = 6; Л - И = 3; Л - З = 7. Из них выбирают звено с наименьшим расстоянием К - И = 2. Далее рассматриваются звенья, связанные с вершинами полученной линии И-К-Л, и из них выбирается наименьшее. При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины. Таким звеном является И-Л, несмотря на то что оно наименьшее из всех, связанных с выбранной сетью И-К-Л одной из вершин, его нельзя включить в кратчайшую связывающую сеть. Другими звеньями, связанными своими вершинами с уже выбранной сетью, являются

звенья М-К, З-К, И-З, И-Ж, И-А, И-М, Л-Ж, Л-З, звено И-З имеет наименьшее расстояние, равное 4, и в этом случае получим сеть З-И-К-Л.

Далее опять рассматривают все звенья, связанные с вершинами полученной сети З-И-К-Л. Звенья И-Ж и К-М имеют одинаковую длину, равную 5, берем любое, например К-М. Получаем сеть З- И-К-М (К-Л). Далее опять рассматривают все звенья, связанные с вершинами полученной сети, и из них выбирают наименьшее и так далее до тех пор, пока не будет выбрана сеть. На рис. 8.4 представлена кратчайшая связывающая сеть рассматриваемого примера, где также проставлена потребность пунктов в грузе (+).

Далее все пункты маршрута, начиная с А, связываются такой замкнутой линией, которая соответствует кратчайшему пути объезда этих пунктов. Первоначально при использовании метода сумм строится таблица, называемая симметричной матрицей. Для маршрута АЖЗИКЛМ она приведена в табл. 8.3.

Таблица 8.3