Линейные симметрии многогранника паросочетанийи автоморфизмы графа (стр. 1 из 2)

Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования

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-1xe1<A-1xH=xe. Так как неравенство строгое, то A-1xe1=0, чего быть не может в силу линейности и невырожденности преобразования A-1.

Непосредственно из предложения 2 вытекает

Предложение 3. Если

и таковы, что xF=AxH, то |H|=|F|.

Отметим также, что в силу невырожденности матрицы A, предложение 2 эквивалентно тому, что в каждом ее столбце и каждой ее строке стоит ровно по одной единице. Это позволяет всякой линейной симметрии A взаимнооднозначно сопоставить перестановку

на множестве ребер графа G по правилу: , если и только если ae'e=1. Определив для произвольного образ , получим, что . Действительно, пусть AxH=xF. Если xeF=1, то существует такое ребро , что aee'=1. Значит, , то есть прообразом всякого ребра при перестановке является некоторое ребро из H. Теперь требуемое следует из взаимнооднозначности и равенств .

Введенное соответствие согласовано с операциями перемножения матриц и перемножения перестановок, то есть если

- перестановки на EG, соответствующие линейным симметриям A1 и A2, то перестановка соответствует линейной симметрии A=A1A2.

Таким образом, множество всех перестановок на EG, соответствующих линейным симметриям многогранника MP(G), является группой, изоморфной группе L(G). Обозначим эту группу через SG. Если

и , то из равенства следует

Предложение 4. Перестановка

на EG является элементом группы SG тогда и только тогда, когда образ паросочетания при перестановке является паросочетанием.

3. Линейные симметрии и автоморфизмы графа G

Перестановка

называется автоморфизмом графа G, если тогда и только тогда, когда . Как известно, множество всех автоморфизмов графа G относительно композиции преобразований образует группу Aut(G). Кроме того, каждый автоморфизм графа G индуцирует перестановку на EG по правилу: для любого . Целью данного параграфа будет доказательство изоморфности групп Aut(G) и SG посредством определенного здесь соответствия " индуцирует ".

Сначала несколько вспомогательных утверждений.

Лемма 1. Пусть

. Вершины xe1 и xe2 многогранника MP(G) смежны тогда и только тогда, когда ребра e1 и e2 смежны в G.

Доказательство. Вершины xe1 и xe2 одновременно удовлетворяют (|EG|-2) линейно независимым уравнениям xe=0,

, каждое из которых определяет опорную к MP(G) гиперплоскость. Следовательно, xe1 и xe2 принадлежат двумерной грани многогранника MP(G), которую можно определить опорной гиперплоскостью . Помимо вершин xe1, xe2 и 0 на этой грани может лежать только вершина (если и только если ). При этом очевидно, что тогда и только тогда, когда вершины xe1, xe2 смежны в MP(G). И наконец, ясно, что условие эквивалентно смежности ребер e1 и e2.