Учебная работа № 1472. Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования
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. Пусть
Доказательство. Так как A булева матрица и включение
Следовательно,
Обратное доказывается аналогично, если заметить, что A1 также является линейной симметрией многогранника MP(G).
Предложение 2. Всякая матрица
Доказательство. Меньше, чем |EG| единиц, в матрице A быть не может, ибо она невырождена. Покажем, что в каждом ее столбце стоит ровно одна единица.
Предположим, что ae1e=ae2e=1 для некоторых
Непосредственно из предложения 2 вытекает
Предложение 3. Если
Отметим также, что в силу невырожденности матрицы A, предложение 2 эквивалентно тому, что в каждом ее столбце и каждой ее строке стоит ровно по одной единице. Это позволяет всякой линейной симметрии A взаимнооднозначно сопоставить перестановку
Введенное соответствие согласовано с операциями перемножения матриц и перемножения перестановок, то есть если
Таким образом, множество всех перестановок на EG, соответствующих линейным симметриям многогранника MP(G), является группой, изоморфной группе L(G). Обозначим эту группу через SG. Если
Предложение 4. Перестановка
3. Линейные симметрии и автоморфизмы графа G
Перестановка
Сначала несколько вспомогательных утверждений.
Лемма 1. Пусть
Доказательство. Вершины xe1 и xe2 одновременно удовлетворяют (|EG|2) линейно независимым уравнениям xe=0,
Лемма 2. Пусть
Доказательство. Следует из леммы 1.
Основываясь на том, что множество всех перестановок на EG является конечной группой, легко показать, что если для данной перестановки
Следующая лемма играет важную роль при построении изоморфизма групп Aut(G) и SG.
Лемма 3. Если образы смежных в G ребер при перестановке
Доказательство. Для
Пусть p=3 и
Итак, если
Теперь, основываясь на лемме 3, определим соответствие
Ясно, что последнему пересечению может принадлежать только ребро
Таким образом, доказано, что
Проведенные рассуждения сформулируем в виде теоремы.
Теорема 1. Перестановка
Переход к группе SG осуществляется с помощью следующего результата.
Теорема 2. Перестановка
Доказательство. Достаточность. В силу леммы 2, образы смежных в G ребер при перестановке
Необходимость. По теореме 1, образы смежных ребер смежны. Покажем, что
Теорема 2 позволяет заключить, что соответствие «
Теорема 3. Соответствие
Доказательство. Действительно, если
Далее, полагая
Теорема доказана.
Итак, суммируя полученные результаты, получаем изоморфность группы линейных симметрий многогранника паросочетаний и группы автоморфизмов соответствующего графа.
В заключение отметим, что аналогичные результаты о симметриях многогранника матроида получены О.В.Червяковым в работе [2].
Список литературы
Емеличев В.А. и др. Лекции по теории графов. М.:Наука, 1990.
Червяков О.В. Линейные симметрии и автоморфизмы матроида // Фунд. и прикл. матем.: Сб. науч. тр. Омск: ОмГУ, 1994. C.8189.
Edmonds J. Maximum matching and a polyhedron with 0,1vertices // Jornal of Research of the National Bureau of Standards B, 1965. P.125130.
Chvatal V. On certain polytopes associated with graphs // Journal of Combinatorial Theory (B). 1975. N 18. P. 138154.