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