Том 6, серия 1, номер 2, 1999 г., Стр. 82-96
УДК 519.1
О. В. Червяков
Аффинные симметрии многогранника, системы независимости с единичным сдвигом
Аннотация:
В терминах неразделимых множеств получен критерий существования симметрии многогранника системы независимости. Этот вопрос сводится к вопросу о существовании симметрии со сдвигом, являющимся вектором инциденций одноэлементных множеств. Для последнего случая рассмотрены приложения к многогранникам паросочетаний, матроидов и остовных деревьев. При условии существования симметрии многогранника системы независимости разработан алгоритм понижения размерности соответствующей оптимизационной задачи с аддитивной целевой функцией.
Ил. 2, библиогр. 7.
Червяков О. В. 1
1. Омский государственный университет, кафедра мат. моделирования,
пр. Мира, 55-А, 644077 Омск, Россия
е-mail: cherv@univer.omsk.su
Статья поступила 28 октября 1998 г.
