Статья : Линейные симметрии многогранника паросочетанийи автоморфизмы графа 


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

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


Линейные симметрии многогранника паросочетанийи автоморфизмы графа




Линейные симметрии многогранника паросочетанийи автоморфизмы графа

Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования

1. Введение

Паросочетанием в графе G=(VG,EG) называется любое (возможно пустое) множество попарно несмежных ребер. Семейство всех паросочетаний графа G обозначим через .

Пусть RG - пространство вектор-столбцов, компоненты которых индексированы элементами множества EG. Для всякого определим его вектор инциденций с компонентами xeR=1 при , xeR=0 при . Многогранник

назовем многогранником паросочетаний. Так как всякое ребро графа G является паросочетанием, то dimMP(G)=|EG|.

Полиэдральная структура многогранника MP(G) исследовалась многими авторами. В частности, Эдмондсом в [3] впервые дано линейное описание многогранника паросочетаний, Хваталом в [4] найден комбинаторный критерий смежности его вершин. Нас будет интересовать группа линейных преобразований пространства RG, переводящих многогранник MP(G) в себя. Более точно: линейной симметрией многогранника MP(G) назовем матрицу такого невырожденного линейного преобразования пространства RG, что для всякой вершины x многогранника MP(G) образ также является вершиной MP(G). Легко доказать, в частности, что такое преобразование переводит грань многогранника в грань той же размерности.

Множество всех линейных симметрий многогранника MP(G) образует группу относительно умножения матриц (композиции преобразований), которую мы будем обозначать через L(G). Переходя к изложению результатов, отметим, что все основные понятия теории графов используются в настоящей работе в соответствии с монографией [1]. Кроме того, для всякой через обозначим множество всех инцидентных вершине u ребер графа G.

В течение всей статьи граф G предполагается связным, не имеющим петель и кратных ребер, |VG|>4.

2. Линейные симметрии и перестановки на EG

Легко заметить, что всякая матрица является булевой. Действительно, так как всякое ребро e является паросочетанием в графе G, то Axe также является паросочетанием, то есть (0,1)-вектором. В то же время, Axe есть попросту столбец матрицы A с именем e.

Предложение 1. Пусть , таковы, что xH2=AxH, xF1=AxF. Тогда включение эквивалентно включению .

Доказательство. Так как A булева матрица и включение строгое, то при покомпонентном сравнении

Следовательно, .

Обратное доказывается аналогично, если заметить, что A-1 также является линейной симметрией многогранника MP(G).

Предложение 2. Всякая матрица содержит ровно |EG| единиц.

Доказательство. Меньше, чем |EG| единиц, в матрице A быть не может, ибо она невырождена. Покажем, что в каждом ее столбце стоит ровно одна единица.

Предположим, что ae1e=ae2e=1 для некоторых , . Так как , то . Из предположения заключаем, что . Следовательно, имеем строгое включение . Тогда, по предложению 1, A-1xe1<A-1xH=xe. Так как неравенство строгое, то A-1xe1=0, чего быть не может в силу линейности и невырожденности преобразования A-1.

Непосредственно из предложения 2 вытекает

Предложение 3. Если и таковы, что xF=AxH, то |H|=|F|.

Отметим также, что в силу невырожденности матрицы A, предложение 2 эквивалентно тому, что в каждом ее столбце и каждой ее строке стоит ровно по одной единице. Это позволяет всякой линейной симметрии A взаимнооднозначно сопоставить перестановку на множестве ребер графа G по правилу: , если и только если ae'e=1. Определив для произвольного образ , получим, что . Действительно, пусть AxH=xF. Если xeF=1, то существует такое ребро , что aee'=1. Значит, , то есть прообразом всякого ребра при перестановке является некоторое ребро из H. Теперь требуемое следует из взаимнооднозначности и равенств .

Введенное соответствие согласовано с операциями перемножения матриц и перемножения перестановок, то есть если - перестановки на EG, соответствующие линейным симметриям A1 и A2, то перестановка соответствует линейной симметрии A=A1A2.

Таким образом, множество всех перестановок на EG, соответствующих линейным симметриям многогранника MP(G), является группой, изоморфной группе L(G). Обозначим эту группу через SG. Если и , то из равенства следует

Предложение 4. Перестановка на EG является элементом группы SG тогда и только тогда, когда образ паросочетания при перестановке является паросочетанием.

3. Линейные симметрии и автоморфизмы графа G

Перестановка называется автоморфизмом графа G, если тогда и только тогда, когда . Как известно, множество всех автоморфизмов графа G относительно композиции преобразований образует группу Aut(G). Кроме того, каждый автоморфизм графа G индуцирует перестановку на EG по правилу: для любого . Целью данного параграфа будет доказательство изоморфности групп Aut(G) и SG посредством определенного здесь соответствия " индуцирует ".

Сначала несколько вспомогательных утверждений.

Лемма 1. Пусть . Вершины xe1 и xe2 многогранника MP(G) смежны тогда и только тогда, когда ребра e1 и e2 смежны в G.

Доказательство. Вершины xe1 и xe2 одновременно удовлетворяют (|EG|-2) линейно независимым уравнениям xe=0, , каждое из которых определяет опорную к MP(G) гиперплоскость. Следовательно, xe1 и xe2 принадлежат двумерной грани многогранника MP(G), которую можно определить опорной гиперплоскостью . Помимо вершин xe1, xe2 и 0 на этой грани может лежать только вершина (если и только если ). При этом очевидно, что тогда и только тогда, когда вершины xe1, xe2 смежны в MP(G). И наконец, ясно, что условие эквивалентно смежности ребер e1 и e2.

Лемма 2. Пусть . Ребра смежны в G, если и только если ребра и смежны в G.

Доказательство. Следует из леммы 1.

Основываясь на том, что множество всех перестановок на EG является конечной группой, легко показать, что если для данной перестановки образы смежных в G ребер смежны, то и прообразы смежных ребер тоже смежны.

Следующая лемма играет важную роль при построении изоморфизма групп Aut(G) и SG.

Лемма 3. Если образы смежных в G ребер при перестановке смежны в G, то для любой существует такая вершина , что .

Доказательство. Для обозначим , p>1. Предположим, что ребра образа не имеют общей вершины. Тогда среди ребер , , есть несмежные, либо является циклом длины 3. В первом случае получаем противоречие с условием теоремы, ибо uui, , попарно смежны. Второй случай рассмотрим подробнее.

Пусть p=3 и , и . Так как G связен и |VG|>4, то существует вершина , которая смежна с какой-либо из вершин u1,u2,u3, - скажем, с u1. Так как uu1 и u1s смежны, то vw и тоже смежны. При этом если они смежны по вершине v, то получаем смежность ребер и и, как следствие, - смежность ребер u1s и uu3, что не так. Если же vw и смежны по вершине w, то аналогично получаем смежность ребер u1s и uu2, что также противоречит выбору вершины s. Следовательно, при p=3 ребра не могут образовывать цикла.

Итак, если не висячая вершина, то для нее существует такая , что . Из условия сохранения смежности ребер и взаимнооднозначности перестановки вытекает, что это включение является равенством, то есть . Нетрудно увидеть, что это равенство выполняется и для висячих вершин графа G.

Теперь, основываясь на лемме 3, определим соответствие правилом: , если и только если , где - перестановка на EG, сохраняющая смежность ребер. Легко заметить, что является перестановкой. Покажем, что она сохраняет смежность вершин графа G. Действительно, всякое ребро можно представить как пересечение множеств и . Следовательно,

Ясно, что последнему пересечению может принадлежать только ребро .

Таким образом, доказано, что является автоморфизмом графа G, причем индуцирует перестановку .

Проведенные рассуждения сформулируем в виде теоремы.

Теорема 1. Перестановка индуцирована некоторым автоморфизмом графа G тогда и только тогда, когда образы смежных в G ребер при перестановке смежны.

Переход к группе SG осуществляется с помощью следующего результата.

Теорема 2. Перестановка на множестве EG индуцирована некоторым автоморфизмом графа G тогда и только тогда, когда .

Доказательство. Достаточность. В силу леммы 2, образы смежных в G ребер при перестановке смежны. Значит, по теореме 1, индуцирована некоторым автоморфизмом графа G.

Необходимость. По теореме 1, образы смежных ребер смежны. Покажем, что для любого . Действительно, если смежны, то и тоже смежны, чего быть не может, ибо и принадлежат H.

Теорема 2 позволяет заключить, что соответствие " индуцирует ", определенное в начале данного параграфа, является отображением группы Aut(G) на SG. Обозначим его через .

Теорема 3. Соответствие является изоморфизмом групп Aut(G) и SG.

Доказательство. Действительно, если и - два различных автоморфизма, то существует такая вершина , что . Пусть , i=1,2. Ясно, что . Следовательно, . Тем самым доказана взаимнооднозначность соответствия .

Далее, полагая и , получим

Теорема доказана.

Итак, суммируя полученные результаты, получаем изоморфность группы линейных симметрий многогранника паросочетаний и группы автоморфизмов соответствующего графа.

В заключение отметим, что аналогичные результаты о симметриях многогранника матроида получены О.В.Червяковым в работе [2].

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

Емеличев В.А. и др. Лекции по теории графов. М.:Наука, 1990.

Червяков О.В. Линейные симметрии и автоморфизмы матроида // Фунд. и прикл. матем.: Сб. науч. тр. Омск: ОмГУ, 1994. C.81-89.

Edmonds J. Maximum matching and a polyhedron with 0,1-vertices // Jornal of Research of the National Bureau of Standards B, 1965. P.125-130.

Chvatal V. On certain polytopes associated with graphs // Journal of Combinatorial Theory (B). 1975. N 18. P. 138-154.

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

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

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

    Статья >> Математика
    ... Aut() для матроида , в [2] - изоморфность группы линейных симметрий многогранника паросочетаний и группы автоморфизмов соответствующего графа ... .- М.:Наука, 1981. Симанчев Р.Ю. Линейные симметрии многогранника паросочетаний и автоморфизмы графа // Вестник ...
  • Лекции по линейной алгебре (МГИЕМ, ФПМ)

    Реферат >> Математика
    ... U*V)(P) = U(V(P)). Например, = * = I - тождественное перемещение. 2. Связь с линейными операторами. Теорема 1 Пусть f: X ® X - перемещение, A, B, C, D - ... 1. По теореме 12 полные группы симметрии многогранников (включающие и перемещения с определителем (-1) ...
  • Методика изучения многогранников в школьном курсе стереометрии

    Дипломная работа >> Педагогика
    ... -30) 10 §3. Правильные многогранники. Симметрия в пространстве. Понятие правильного многогранника. Элементы симметрии правильных многогранников. (п. 31-33 ... основания двугранный угол α (рис. 4.9). Постройте линейный угол этого двугранного угла. Дайте ...
  • Проявление симметрии в различных формах материи

    Реферат >> Естествознание
    ... первичного строения (из-за уникальной линейной последовательности различ­ных L и реже D аминокислот), в симметричности ... число и вид их симметрии соответствуют числу и виду симметрии правильных многогранников: m·2/3 (тетраэдр), т·4 ...
  • Методика изучения объемов многогранников в курсе стереометрии

    Дипломная работа >> Педагогика
    ... , на вычисление линейных и угловых элементов ... многогранников. Число, характеризующее величину внутренней области многогранника, называется объемом многогранника. Смежными многогранниками называются такие многогранники ... используется свойство симметрии для того, ...
  • Структура и свойство материалов (из конспекта лекций)

    Реферат >> Физика
    ... : 1). центром симметрии ( I ), 2). плоскостью симметрии (m), 3). осью симметрии (n). 1). Это некая точка m многогранника, которая хар-ся ... измерении – границы блоков и зёрен. Точечные, линейные и поверхностные явл. микроскопическими дефектами т.е. в ...
  • Шпаргалки по геометрии, алгебре, педагогике, методике математики (ИГПИ)

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

    Реферат >> Физика
    ... рёбрами и обладает симметрией. Как и всякий многогранник, кристалл имеет некоторое ... поля Е, то у сегнетоэлектриков такая линейная зависимость между Р и Е существует ... - преобразуют неполяризованный свет в линейно поляризованный, поскольку они могут пропускать ...
  • Избранные теоремы геометрии тетраэдра

    Дипломная работа >> Математика
    ... , поэтому EKN – линейный угол двугранного угла, образованного ... Пирамида»). Далее рассматриваются правильные многогранники и элементы симметрии правильных многогранников. Формула нахождения объёма ... = SNO = 45° — как линейные углы данных двугранных углов. А ...
  • Задачи Лоповок

    Реферат >> Математика
    ... параллелограмм или трапеция. Осевая симметрия 223. Найдите координаты вершин ... восьмиугольника А\А•^А^А^А^А!,А^Ау. через его линейные элементы». Поступили следующие ответы: ... на основаниях. Докажите, что объем многогранника V = — ((?1 + Ог + 4