Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Симметрии многогранника системы независимости
Раздел: Рефераты по математике
Тип: статья Добавлен 13:18:07 24 марта 2007 Похожие работы
Просмотров: 261 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:52:51 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:52:51 24 ноября 2015

Работы, похожие на Статья: Симметрии многогранника системы независимости

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151398)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru