Линейные симметрии многогранника паросочетанийи автоморфизмы графа
![]()
![]()
Ясно,
что последнему пересечению может принадлежать только ребро
.
Таким
образом, доказано, что
является
автоморфизмом графа 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.