Линейные симметрии многогранника паросочетанийи
автоморфизмы графа
Р.Ю. Симанчёв, Омский государственный университет,
кафедра математического моделирования
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
Непосредственно
из предложения 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/