The problems of mixed Boolean linear programming for finding the shortest routes and the shortest cycles that pass through a given number of nodes in a complete graph are formulated. Their special cases provide formulations of problems for finding the shortest Hamiltonian path and the shortest Hamiltonian cycle. The formulated problems include no more than 2n2 variables and no more than (n+1)2 constraints, where n is the number of nodes of complete graph. Refs: 3 titles.
Сформульовано задачі змішаного булевого лінійного програмування для знаходження найкоротшого шляху і найкоротшого циклу, які проходять через задану кількість вершин повного графа. Їх окремі випадки дають формулювання задач для знаходження найкоротшого гамільтонового шляху і найкоротшого гамільтонового циклу. Задачі містять не більше ніж 2n2 змінних і не більше ніж (n+1)2 обмежень, де n — кількість вершин повного графа. Бібліогр.: 3 назви.
Сформулированы задачи смешанного булевого линейного программирования для нахождения кратчайшего пути и кратчайшего цикла, которые проходят через заданное количество вершин полного графа. В частном случае из них следуют формулировки задач для нахождения кратчайшего гамильтонового пути и кратчайшего гамильтонового цикла. Задачи содержат не более чем 2n2 переменных и не более чем (n+1)2 ограничений, где n — количество вершин полного графа. Библиогр.: 3 назв.
Стецюк Петр Иванович, доктор физ.-мат. наук, заведующий отделом Института кибернетики
им. В.М. Глушкова НАН Украины, Киев,
e-mail: e-mail: stetsyukp@gmail.com