Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!
Реферат

Реферат по предмету "Математика"


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

Симметрии многогранника системы независимости
О.В. Червяков, Омский государственный университет,
кафедра математического моделирования
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.

Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Nurse Essay Research Paper The occupation of
Реферат Будущая политика контроля за распространением наркотиков в странах бывшего Восточного Блока
Реферат Билеты по менеджменту за 1 семестр 2-го курса (2003г.)
Реферат Кто же изобрел телескоп ?
Реферат Электронные вычислительные сети
Реферат The Effects Of The Industrial Revolution On
Реферат Упаковочные материалы применяемые для продуктов питания и их влияни
Реферат Основные тенденции развития российского законодательства о несостоятельности банкротстве
Реферат Українські народні традиції та обрядовість у моральному вихованні молодших школярів
Реферат Понятие инвестиционного рынка
Реферат Диалог как форма психологического воздействия
Реферат Поэтические формы в обучении французскому языку
Реферат Архитектура эпохи Возрождения
Реферат Валерий Брюсов новеллист
Реферат Двигательная активность и долголетие организационные и педагогические аспекты