Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Линейные симметрии многогранника паросочетанийи
автоморфизмы графа
Р.Ю. Симанчёв, Омский государственный университет,
кафедра математического моделирования
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.
Предложение
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.
Chvatal V. On certain polytopes associated with graphs // Journal of
Combinatorial Theory (B). 1975. N 18. P. 138-154.
Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/