Об NP-полноте задачи размещения графа

В работе приводится доказательства NP-полноты задачи размещения графа. Таким образом, делается вывод о том, что для алгоритмизации задачи размещения графа требуется подход, основанный на эвристических или стохастических методах. Для доказательства NP-полноты задачи размещения графа используется известная NP-полная задача поиска гамильтонова цикла. Показывается, что задача размещения графа является обобщением над задачей гамильтонова цикла. Также приводится постановка задачи размещения графа как оптимизационной,и приводятся вспомогательные результаты, которые устанавливают связь между двумя задачами: NP-полной и оптимизационной задачей размещения графа.

Ключевые слова: задача размещения графа, NP-полнота.

doi:10.34219/2078-8320-2019-10-1-51-54

F. Melnikov 1,2, V. A. Dudnikov

On the NP-completeness of the problem of placement of the graph

 This paper provides a proof of NP-completeness of the problem of the placement of the graph. Thus, it is concluded that the algorithmization of the graph placement problem requires an approach based on heuristic or stochastic methods. To prove the NP-completeness of the graph placement problem, we use the well-known NP-complete Hamiltonian cycle search problem. It is shown that the graph placement problem is a generalization over the Hamiltonian cycle problem. Also the problem of the placement of the graph as the optimization and presents some auxiliary results, which are set nalivayut the connection between the two problems: NP-complete optimization problem and embed the graph.

Keywords: graph placement problem, NP-completeness.

doi:10.34219/2078-8320-2019-10-1-51-54