Симметрии многогранника системы независимости
Пусть 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.
Рассмотрим задачу комбинаторной оптимизации на системе независимости с аддитивной целевой функцией:
Реклама
Мнение авторов может не совпадать с мнением редакции сайта
Перепечатка материалов без ссылки на наш сайт запрещена |