Учебная работа № 1369. Симметрии многогранника системы независимости
О.В. Червяков, Омский государственный университет, кафедра математического моделирования
1.
Пусть E = { e1,e2,,en} некоторое множество мощности n. Системой независимости на множестве E называется непустое семейство J его подмножеств, удовлетворяющее условию: если J
Множества семейства
Автоморфизмом системы независимости
Пусть RE евклидово пространство, ассоциированное с E посредством взаимоодназначного соответствия между множеством координатных осей пространства RE и множеством E. Иными словами, RE можно понимать как совокупность векторстолбцов размерности n с вещественными компонентами, индексированными элементами множества E. Всякому S E сопоставим его вектор инциденций по правилу: xSe= 1 при eS , xSe= 0 при eS. Очевидно, что это правило задает взаимооднозначное соответствие между 2E и вершинами единичного куба в RE. Многогранник системы независимости
Пусть PRE произвольный многогранник. Симметрией многогранника P назовем такое невырожденное аффинное преобразование пространства RE, что (P){(x) | xP}=P. Как известно, всякое невырожденное аффинное преобразование определяется невырожденной (nn)матрицей A и сдвигом hRE, то есть (x)=Ax+h при xRE [1]. Очевидно, что невырожденное аффинное преобразование пространства RE является симметрией многогранника P(
Симметрию с нулевым сдвигом будем называть линейной симметрией. Очевидно, что множество всех симметрий многогранника P является группой относительно суперпозиции отображений, а множество линейных симметрий ее подгруппой. Группу симметрий многогранника P мы будем обозначать через S(
Ранее в [3] была доказана изоморфность групп L(
В настоящей работе показано, что группа симметрий многогранника системы независимости выписывается с помощью подгруппы L(
Рассмотрим задачу комбинаторной оптимизации на системе независимости с аддитивной целевой функцией:
(1) |
где ve0 вес элемента eE. Пусть имеется симметрия многогранника P со сдвигом xH. Тогда задача (1) сводится к задаче, размерность которой не больше, чем EH.
Ниже приведены понятия и факты, необходимые для дальнейшего изложения.
Пусть H
Без ограничения общности будем считать, что размерность многогранника P равна n, ибо в противном случае существует элемент eЕ, не содержащийся ни в каком независимом множестве и, следовательно, вместо E можно рассматривать множество E\{e} .
2. Структура группы симметрий системы независимости
Итак, будем считать, что у нас зафиксирована система независимости
Так как
Лемма 1. Пусть SH, a 1 аффинное невырожденное преобразование пространства RE. Тогда 1SH, если и только если существует такое 2L(
Доказательство. Так как L(
Таким образом, наличие какойлибо (любой) симметрии из SH позволяет с помощью группы L(
Лемма 2. Пусть j невырожденное преобразование пространства RE. Преобразование jSH тогда и только тогда, когда j=j1j2, где
a j2 Hотображение.
Доказательство. Прямыми вычислениями легко убедиться, что j1(xS) = xSH для любого SE, и j11=j1.
Если 2 Hотображение, то для любого I
Следовательно, = 12 симметрия многогранника P и jSH.
Если же jSH, то для любого I
Значит, 2 Hотображение. Данная лемма дает возможность свести поиск представителя класса SH к поиску одного Hотображения. Причем, если Hотображений для данного H
Поиск Hотображения существенно упрощается с помощью следующего предложения.
Предложение 1. Матрица Hотображения булева.
Доказательство. Так как {ej}
3. Понижение размерности задачи на системе независимости
Рассмотрим оптимизационную задачу (1) и перейдем к полиэдральной постановки этой задачи
(2) |
где v это вектор, компоненты которого веса соответствующих элементов. Очевидно, что решение задачи (2), при условии «поиска по вершинам», будет являться вектором инциденций решения задачи (1). Кроме того, если существует симметрия многогранника P с матрицей A и сдвигом h, и x* решение задачи
(3) |
то вектор x = Ax*+h решение задачи (2).
Предложение 2. Пусть (x) = Ax+xH симметрия многогранника P и v произвольный вектор с положительными компонентами. Тогда вектор vTA имеет по крайней мере H неположительных компонент.
Доказательство. По лемме 2, симметрия представима в виде суперпозиции отображений 1, описанного в лемме 2, и Hотображения 2. Матрица A является произведением матриц преобразований 1 и 2. Так как H
Здесь I и H столбцы и строки, соответствующие элементам из этих множеств, а блок B некоторая булевa матрица. При умножении матрицы преобразования 2 на матрицу преобразования 1 блок B заменяется на блок (B). Затем, при умножении вектора vT на матрицу A, получается вектор, у которого компоненты, соответствующие элементам множества I, неположительные. Очевидно, что элементы, имеющие неположительные веса, не принадлежат оптимальному множеству задачи (3). Следовательно, исключая из рассмотрения эти элементы, переходим к задаче
(4) |
где v* = vTA, Dсовокупность элементов, у которых соответствующие компоненты вектора v* неположительные. Вектор инциденций решения этой задачи есть оптимальный вектор задачи (3). Причем, по предыдущему предложению, размерность задачи (4) не больше, чем EH.
Пример 1. Пусть E = {1,2,3,4},
a симметрия многогранника системы независимости
Пусть вектор весов v = (3,1,4,2), тогда вектор новых весов будет равен
и после отбрасывания элементов c отрицательными весами получаем множество {2} , состоящее из одного элемента, которое и будет оптимальным для задачи с новыми весами. Следовательно вектор инциденций решения исходной задачи будет
То есть оптимальное множество исходной задачи есть множество {1,2,3}.
Список литературы
Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.:Наука, 1981.
Симанчев Р.Ю. Линейные симметрии многогранника паросочетаний и автоморфизмы графа // Вестник Омского университета, 1996. N.1. C.1820.
Червяков О.В. Линейные симметрии и автоморфизмы матроида // Фундаментальная и прикладная математика. ОмГУ, 1994, с. 81 89.
Conforti M., Laurent M. On the facial structure of independence system polyhedra // Math. of operations research. 1988. V.13. N. 4. P. 543 555.