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


Полнотекстовый поиск по базе:

Главная >> Статья >> Математика


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




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

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

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/

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

  • Проявление симметрии в различных формах материи

    Реферат >> Естествознание
    ... системы (в иенрциальной системе координат). Среди дискретных пространственно-временных симметрий различают СРТ-симметрию и зеркальную симметрию ... , открытый независимо Гульельмини и ... их симметрии соответствуют числу и виду симметрии правильных многогранников: ...
  • Проявление симметрии в различных формах материи

    Реферат >> Естествознание
    ... симметрией. А что такое кристалл? Твердое тело, имеющие естественную форму многогранника. ... абсолютное пространство, свободное и независимое от каких-либо тел. Это ... и равномерность движения центра инер­ции системы тел в однородном пространстве. Никакие ...
  • Методика изучения объемов многогранников в курсе стереометрии

    Дипломная работа >> Педагогика
    ... кратки и доступны. Система упражнений последовательна, содержит ... независимо от их расположения в пространстве. 2. Объем многогранника, представляющего собой сумму двух смежных многогранников ... параллелепипеда; используется свойство симметрии для того, чтобы ...
  • Нейрокомпьютерные системы

    Реферат >> Информатика, программирование
    ... линиями, то все такие многогранники выпук­лы, следовательно, только выпуклые ... непрерывным осцилляциям. Однако приближенной симметрии обычно достаточно для устойчивости ... независимо от позиции образа в поле комплек­сных узлов в предшествующем слое. Эта система ...
  • Твердые кристаллы

    Реферат >> Геология
    ... многограннике можно найти плоскости симметрии, оси симметрии, центры симметрии и другие элементы симметрии так ... определять кристаллическую структуру вещества независимо от того, какова его ... . Складка –это легкоподвижный дефект в системе «ковер – пол», так как ...
  • Особенности обучения элементам геометрии в 5-6 классах с позиций пропедевтики изучения геометрии в средней школе

    Дипломная работа >> Педагогика
    ... самостоятельную роль, обеспечивая формирование системы пространственных представлений и пространственного ... восприимчивости, гибкости и независимости мышления. Введение новых ... многогранник, как «Пирамида», а во втором отсутствует такая тема. Тема «Симметрия» ...
  • Шпаргалки по геометрии, алгебре, педагогике, методике математики (ИГПИ)

    Реферат >> Математика
    ... системе аксиом. Любая система аксиом должна удовлетворять: непротиворечивость, независимость, ... о том, что преобразование симметрии относительно точки и прямой ... 1. рассмотреть модели и изображения многогранников, предметы окруж. действительности, повторить ...
  • Кристаллы в природе

    Реферат >> Физика
    ... системы. Симметрия кристаллов специфична. Например, среди кристаллических многогранников, имеющих оси симметрии ... узлах кристаллической решётки, колеблются независимо друг от друга с одинаковой ... к стеклу. Оказывается, что независимо от толщины слоя, пороговое ...
  • Измерения геометрических величин в курсе геометрии 7-9 классов

    Дипломная работа >> Педагогика
    ... общепризнанной является следующая система дидактических принципов ... Например, при изучении многогранников демонстрация и самостоятельное ... материи практически независимо от диапазона ... треугольника и осевой симметрии Применение свойств прямоугольного ...
  • Задача обработки решеток

    Реферат >> Радиоэлектроника
    ... множество Р является выпуклым многогранником, описанный вокруг первоначального ... В силу осевой симметрии системы по­верхностный интеграл (9. ... симметрии очень -сильно усложняет решение, поскольку теря­ется основное преимущество систем враще­ния — независимость ...