
Линейные симметрии многогранника паросочетанийи автоморфизмы графа
| Категория реферата: Рефераты по математике
| Теги реферата: ответы по контрольной, государство реферат
| Добавил(а) на сайт: Harlam.
1 2 3 | Следующая страница реферата
Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Р.Ю. Симанчёв, Омский государственный университет, кафедра математического моделирования
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 2 3 | Следующая страница реферата