Статья Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Работа добавлена на сайт bukvasha.net: 2015-10-29Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
![](https://bukvasha.net/assets/images/emoji__ok.png)
Предоплата всего
от 25%
![](https://bukvasha.net/assets/images/emoji__signature.png)
Подписываем
договор
Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования
1. Введение
Паросочетанием в графе G=(VG,EG) называется любое (возможно пустое) множество попарно несмежных ребер. Семейство всех паросочетаний графа G обозначим через
Пусть RG - пространство вектор-столбцов, компоненты которых индексированы элементами множества EG. Для всякого
назовем многогранником паросочетаний. Так как всякое ребро графа G является паросочетанием, то dimMP(G)=|EG|.
Полиэдральная структура многогранника MP(G) исследовалась многими авторами. В частности, Эдмондсом в [3] впервые дано линейное описание многогранника паросочетаний, Хваталом в [4] найден комбинаторный критерий смежности его вершин. Нас будет интересовать группа линейных преобразований пространства RG, переводящих многогранник MP(G) в себя. Более точно: линейной симметрией многогранника MP(G) назовем матрицу
Множество всех линейных симметрий многогранника MP(G) образует группу относительно умножения матриц (композиции преобразований), которую мы будем обозначать через L(G). Переходя к изложению результатов, отметим, что все основные понятия теории графов используются в настоящей работе в соответствии с монографией [1]. Кроме того, для всякой
В течение всей статьи граф G предполагается связным, не имеющим петель и кратных ребер, |VG|>4.
2. Линейные симметрии и перестановки на EG
Легко заметить, что всякая матрица
Предложение 1. Пусть
Доказательство. Так как A булева матрица и включение
Следовательно,
Обратное доказывается аналогично, если заметить, что A-1 также является линейной симметрией многогранника 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.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/