Линейные симметрии многогранника паросочетанийи автоморфизмы графа (стр. 2 из 2)
Лемма 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.