Построение модели

Изобразим каждый город точкой на плоскости и пометим ее соответствующей меткой A_i (i = 1, 2, 3, 4). Соединим эти точки отрезками прямых: они будут изображать дороги между городами. Для каждой «дороги» укажем ее протяженность в километрах (рис. 7.2). Получился граф – математический объект, состоящий из некоторого множества точек на плоскости (называемых вершинами) и некоторого множества линий, соединяющих эти точки (называемых ребрами). Более того, этот граф меченый, так как его вершинам и ребрам приписаны некоторые метки – числа (ребрам) или символы (вершинам). Циклом на графе называется последовательность вершин V₁, V₂,…,V_k, V₁ такая, что вершины V₁, V₂,…,V_k – различны, а любая пара вершин V_i, V_i+1 (i = 1, …, k-1) и пара V₁, V_k соединены ребром. Рассматриваемая задача заключается в отыскании такого цикла на графе, проходящего через все четыре вершины, для которого сумма всех весов ребер минимальна.

Рисунок 7.2

2. Решение математической задачи, к которой приводит модель. Найдем перебором все различные циклы, проходящие через четыре вершины и начинающиеся в А₁: 1) А₁, А₄, А₃, А₂, А₁; 2) А₁, А₃, А₂, А₄, А₁; 3) А₁, А₃, А₄, А₂, А₁. Найдем теперь длины этих циклов (в км): L₁ = 160, L₂ = 180, L₃ = 200. Итак, маршрут наименьшей длины – это первый.

Заметим, что если в графе п вершин и все вершины попарно соединены между собой ребрами (такой граф называется полным), то число циклов, проходящих через все вершины, равно . Следовательно, в нашем случае имеется ровно три цикла.

3. Интерпретация полученных следствий из математической модели. Порядок посещения городов, при котором длина соответствующего пути коммивояжера минимальна, следующий: А₁, А₄, А₃, А₂, А₁ или в обратном порядке.