Линейные симметрии многогранника паросочетанийи автоморфизмы графа Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования 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-1xe11. Предположим, что ребра образа не имеют общей вершины. Тогда среди ребер , , есть несмежные, либо является циклом длины 3. В первом случае получаем противоречие с условием теоремы, ибо uui, , попарно смежны. Второй случай рассмотрим подробнее.
    Пусть p=3 и , и . Так как G связен и |VG|>4, то существует вершина , которая смежна с какой-либо из вершин u1,u2,u3, - скажем, с u1. ............