Xreferat.com » Рефераты по математике » Симметрии многогранника системы независимости

Симметрии многогранника системы независимости

О.В. Червяков, Омский государственный университет, кафедра математического моделирования

1.  Введение

Пусть E = { e1,e2,,en} - некоторое множество мощности n. Системой независимости на множестве E называется непустое семейство J его подмножеств, удовлетворяющее условию: если JСимметрии многогранника системы независимостиСимметрии многогранника системы независимостии IСимметрии многогранника системы независимости, то IСимметрии многогранника системы независимости.

Множества семейства Симметрии многогранника системы независимостиназывается независимыми множествами. Максимальные по включению множества из Симметрии многогранника системы независимостиназываются базисами.

Автоморфизмом системы независимости Симметрии многогранника системы независимостиназывается такое взаимооднозначное отображение  множества E на себя, что (I){(e) | eI}Симметрии многогранника системы независимостидля любого независимого множества I. Группу автоморфизмов системы независимости Симметрии многогранника системы независимостибудем обозначать через Aut(Симметрии многогранника системы независимости).

Пусть RE - евклидово пространство, ассоциированное с E посредством взаимоодназначного соответствия между множеством координатных осей пространства RE и множеством E. Иными словами, RE можно понимать как совокупность вектор-столбцов размерности n с вещественными компонентами, индексированными элементами множества E. Всякому S E сопоставим его вектор инциденций по правилу: xSe= 1 при eS , xSe= 0 при eS. Очевидно, что это правило задает взаимооднозначное соответствие между 2E и вершинами единичного куба в RE. Многогранник системы независимости Симметрии многогранника системы независимостиопределим как P(Симметрии многогранника системы независимости) = Conv(xI | IСимметрии многогранника системы независимости). Ясно, что векторы инциденций независимых множеств системы независимости Симметрии многогранника системы независимости, и только они, являются вершинами многогранника P(Симметрии многогранника системы независимости) [4].

Пусть PRE - произвольный многогранник. Симметрией многогранника P назовем такое невырожденное аффинное преобразование  пространства RE, что (P){(x) | xP}=P. Как известно, всякое невырожденное аффинное преобразование  определяется невырожденной (nn)-матрицей A и сдвигом hRE, то есть (x)=Ax+h при xRE [1]. Очевидно, что невырожденное аффинное преобразование  пространства RE является симметрией многогранника P(Симметрии многогранника системы независимости) тогда и только тогда, когда для любого IСимметрии многогранника системы независимости существует такое JСимметрии многогранника системы независимости, что (xI) = xJ.

Симметрию с нулевым сдвигом будем называть линейной симметрией. Очевидно, что множество всех симметрий многогранника P является группой относительно суперпозиции отображений, а множество линейных симметрий - ее подгруппой. Группу симметрий многогранника P мы будем обозначать через S(Симметрии многогранника системы независимости), а ее подгруппу линейных симметрий - через L(Симметрии многогранника системы независимости).

Ранее в [3] была доказана изоморфность групп L(Симметрии многогранника системы независимости) и Aut(Симметрии многогранника системы независимости) для матроида Симметрии многогранника системы независимости, в [2] - изоморфность группы линейных симметрий многогранника паросочетаний и группы автоморфизмов соответствующего графа. Пользуясь аналогичными методами, легко доказать изоморфность групп L(Симметрии многогранника системы независимости) и Aut(Симметрии многогранника системы независимости) для произвольной системы независимости Симметрии многогранника системы независимости.

В настоящей работе показано, что группа симметрий многогранника системы независимости выписывается с помощью подгруппы L(Симметрии многогранника системы независимости) и семейства некоторых специальных преобразований пространства RE.

Рассмотрим задачу комбинаторной оптимизации на системе независимости с аддитивной целевой функцией:

Симметрии многогранника системы независимости

(1)

где ve0 - вес элемента eE. Пусть имеется симметрия многогранника P со сдвигом xH. Тогда задача (1) сводится к задаче, размерность которой не больше, чем E-H.

Ниже приведены понятия и факты, необходимые для дальнейшего изложения.

Пусть HСимметрии многогранника системы независимости. H-отображением будем называть линейное невырожденное преобразование  пространства RE, удовлетворяющее условию: для любого IСимметрии многогранника системы независимости существует такое JСимметрии многогранника системы независимости, что (xI) = xJH, где под JH подразумевается симметрическая разность множеств J и H.

Без ограничения общности будем считать, что размерность многогранника P равна n, ибо в противном случае существует элемент eЕ, не содержащийся ни в каком независимом множестве и, следовательно, вместо E можно рассматривать множество E{e} .

2.  Структура группы симметрий системы независимости

Итак, будем считать, что у нас зафиксирована система независимости Симметрии многогранника системы независимостина множестве E={e1,e2,,en}; RE-пространство, ассоциированное с E; P-многогранник системы независимости Симметрии многогранника системы независимости.

Так как Симметрии многогранника системы независимости, то для всякой симметрии  со сдвигом h найдется такое HСимметрии многогранника системы независимости, что h=xH. Таким образом, группу S(Симметрии многогранника системы независимости) можно разбить на непересекающиеся классы Симметрии многогранника системы независимости, где SH - класс симметрий многогранника P(Симметрии многогранника системы независимости), имеющих сдвиг xH. Это позволяет свести описание группы S(Симметрии многогранника системы независимости) к описаниюСимметрии многогранника системы независимости.

Лемма 1. Пусть SH, a 1 - аффинное невырожденное преобразование пространства RE. Тогда 1SH, если и только если существует такое 2L(Симметрии многогранника системы независимости), что 1 = jj2.

Доказательство. Так как L(Симметрии многогранника системы независимости) и SH являются подмножествами группы S(Симметрии многогранника системы независимости), то j1 = jj2S(Симметрии многогранника системы независимости). Очевидно, что j1 имеет сдвиг xH. Обратно, если j1  SH, то j2 = j-1j1S(Симметрии многогранника системы независимости), причем с нулевым сдвигом. Следовательно, j2L(Симметрии многогранника системы независимости).

Таким образом, наличие какой-либо (любой) симметрии из SH позволяет с помощью группы L(Симметрии многогранника системы независимости) найти весь класс SH.

Лемма 2. Пусть j - невырожденное преобразование пространства RE. Преобразование jSH тогда и только тогда, когда j=j1j2, где

Симметрии многогранника системы независимости

a j2 - H-отображение.

Доказательство. Прямыми вычислениями легко убедиться, что j1(xS) = xSH для любого SE, и j1-1=j1.

Если 2 - H-отображение, то для любого IСимметрии многогранника системы независимостисуществует такой JСимметрии многогранника системы независимости, что 2(xI) = xJH. То есть 12(xI) = x(JH)H = xJ.

Следовательно,  = 12 - симметрия многогранника P и jSH.

Если же jSH, то для любого IСимметрии многогранника системы независимости существует такой JСимметрии многогранника системы независимости, что (xI)=xJ. Следовательно, 2(xI) =1-1(xI) = 1-1(xJ) = 1(xJ) = xJH

Значит, 2 - H-отображение. Данная лемма дает возможность свести поиск представителя класса SH к поиску одного H-отображения. Причем, если H-отображений для данного HСимметрии многогранника системы независимости не существует, то SH=.

Поиск H-отображения существенно упрощается с помощью следующего предложения.

Предложение 1. Матрица H-отображения  булева.

Доказательство. Так как {ej}Симметрии многогранника системы независимости для любого j{1n}, то ,по определению H-отображения, вектор (x{ej}), являющийся j-м столбцом матрицы отображения, булев, что и требовалось доказать.

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Симметрии многогранника системы независимостиH{Симметрии многогранника системы независимостиH | JСимметрии многогранника системы независимости}, то существует такое множество IСимметрии многогранника системы независимости, что 2 (xI) = xH. Причем, так как любое подмножество H принадлежит Симметрии многогранника системы независимостиH, то в силу линейности 2, IH. Следовательно, матрица преобразования 2 принимает вид

Симметрии многогранника системы независимости

Здесь I и H - столбцы и строки, соответствующие элементам из этих множеств, а блок B - некоторая булевa матрица. При умножении матрицы преобразования 2 на матрицу преобразования 1 блок B заменяется на блок (-B). Затем, при умножении вектора vT на матрицу A, получается вектор, у которого компоненты, соответствующие элементам множества I, неположительные. Очевидно, что элементы, имеющие неположительные веса, не принадлежат оптимальному множеству задачи (3). Следовательно, исключая из рассмотрения эти элементы, переходим к задаче

Симметрии многогранника системы независимости

(4)

где v* = vTA, D-совокупность элементов, у которых соответствующие компоненты вектора v* неположительные. Вектор инциденций решения этой задачи есть оптимальный вектор задачи (3). Причем, по предыдущему предложению, размерность задачи (4) не больше, чем E-H.

Пример 1. Пусть E = {1,2,3,4}, Симметрии многогранника системы независимости- система независимости, базисы которого являются множества {1,2,3} и {3,4}. Пусть H={1,3}. Тогда матрица H-отображения принимает вид

Симметрии многогранника системы независимости

a симметрия многогранника системы независимости Симметрии многогранника системы независимости-

Симметрии многогранника системы независимости

Пусть вектор весов v = (3,1,4,2), тогда вектор новых весов будет равен

Симметрии многогранника системы независимости

и после отбрасывания элементов c отрицательными весами получаем множество {2} , состоящее из одного элемента, которое и будет оптимальным для задачи с новыми весами. Следовательно вектор инциденций решения исходной задачи будет

Симметрии многогранника системы независимости

То есть оптимальное множество исходной задачи есть множество {1,2,3}.

Список литературы

Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация.- М.:Наука, 1981.

Симанчев Р.Ю. Линейные симметрии многогранника паросочетаний и автоморфизмы графа // Вестник Омского университета, 1996. N.1. C.18-20.

Червяков О.В. Линейные симметрии и автоморфизмы матроида //   Фундаментальная и прикладная математика. ОмГУ, 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.

Похожие рефераты: