Построение гамильтонова пути в графах перестановочных многогранников

• Published in: Кибернетика и системный анализ
• Date: 2010
• Main Authors: Донец, Г.А., Колечкина, Л.Н.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2010
• Subjects: Кибернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/45121
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос.

Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, який використовує цю властивість побудови гамільтонового шляху в графі, що відповідає множині переставлень для n = 4. The problem of finding an extremum of a linear function on a set of permutations is considered. The polyhedron of admissible values on the permutation set is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path on the graph corresponding to the set of permutations for n = 4.