Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне

Abstract

В статье формулируется гамильтонова задача о сельском почтальоне, являющаяся обобщением задачи коммивояжера. Предлагается процедура вершинно-рёберного преобразования, которая выполняется непосредственно перед решением задачи.

У статті формулюється гамільтонова задача про сільського листоношу, яка є узагальненням задачі комівояжера. Пропонується процедура вершинно-реберного перетворення, яка виконується безпосередньо перед розв’язанням задачі.

The Hamiltonian Rural Postman Problem which is generalisation of the Travelling Salesman Problem is formulated in this article. Procedure of vertex-edge transformation which is applied before a problem solving is offered.