Рефетека.ру / Математика

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

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

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. Пусть Линейные симметрии многогранника паросочетанийи автоморфизмы графа, Линейные симметрии многогранника паросочетанийи автоморфизмы графатаковы, что xH1=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.

Рефетека ру refoteka@gmail.com