Симметрии многогранника системы независимости
Симметрии многогранника системы независимости
О.В. Червяков, Омский государственный университет,
кафедра математического моделирования
1. Введение
Пусть
E = { e1,e2,,en} - некоторое множество мощности n. Системой
независимости на множестве E называется непустое семейство J его подмножеств,
удовлетворяющее условию: если Jи
I,
то I.
Множества
семейства называется
независимыми множествами. Максимальные по включению множества из называются
базисами.
Автоморфизмом
системы независимости называется
такое взаимооднозначное отображение множества E на себя, что (I) eIдля любого
независимого множества I. Группу автоморфизмов системы независимости будем
обозначать через Aut().
Пусть
RE - евклидово пространство, ассоциированное с E посредством взаимоодназначного
соответствия между множеством координатных осей пространства RE и множеством E.
Иными словами, RE можно понимать как совокупность вектор-столбцов размерности n
с вещественными компонентами, индексированными элементами множества E. Всякому
S E сопоставим его вектор инциденций по правилу: xSe= 1 при eS
, xSe= 0 при eS. Очевидно, что это правило задает взаимооднозначное
соответствие между 2E и вершинами единичного куба в RE. Многогранник системы
независимости определим
как P()
= Conv(xI | I). Ясно, что
векторы инциденций независимых множеств системы независимости ,
и только они, являются вершинами многогранника P()
[4].
Пусть
PRE - произвольный многогранник. Симметрией многогранника P назовем
такое невырожденное аффинное преобразование пространства RE, что (P)=P. Как известно, всякое невырожденное аффинное преобразование
определяется невырожденной (nn)-матрицей A и сдвигом hRE, то
есть (x)=Ax+h при xRE [1]. Очевидно, что невырожденное аффинное
преобразование пространства RE является симметрией многогранника P()
тогда и только тогда, когда для любого I существует
такое J, что (xI)
= xJ.
Симметрию
с нулевым сдвигом будем называть линейной симметрией. Очевидно, что множество
всех симметрий многогранника P является группой относительно суперпозиции
отображений, а множество линейных симметрий - ее подгруппой. Группу симметрий
многогранника P мы будем обозначать через S(),
а ее подгруппу линейных симметрий - через L().
Ранее
в [3] была доказана изоморфность групп L()
и Aut()
для матроида ,
в [2] - изоморфность группы линейных симметрий многогранника паросочетаний и
группы автоморфизмов соответствующего графа. Пользуясь аналогичными методами,
легко доказать изоморфность групп L()
и Aut()
для произвольной системы независимости .
В
настоящей работе показано, что группа симметрий многогранника системы
независимости выписывается с помощью подгруппы L()
и семейства некоторых специальных преобразований пространства RE.
Рассмотрим
задачу комбинаторной оптимизации на системе независимости с аддитивной целевой
функцией: