Критерий смежности вершин политопов, порождаемых подмножествами симметрической группы

Предложена характеризация смежности вершин в классе подстановочных политопов, порождаемых произвольными подмножествами симметрической группы. Указанному классу принадлежат политопы известных классических задач о назначениях, $2$- и $3$-сочетаниях, коммивояжере и их различных модификаций. До настоящего времени вопросы, связанные со смежностью вершин, исследовались в основном для отдельных политопов. В данной работе для подстановочного политопа общего вида получены необходимые и достаточные условия (не)смежности его вершин, которые сформулированы в терминах подстановок и разрешимости специального вида систем линейных уравнений. Известные критерии смежности вершин политопа задачи о назначениях являются простыми следствиями предложенных условий. На основе последних разработана общая алгоритмическая схема для распознавания смежности вершин подстановочного политопа общего вида и оценена ее трудоемкость.
Библиография: 20 названий.