Введение 5 страниц. Первая часть теория по плотнику. Вторая часть: Для групп построить группу автоморфизмов

Линейные симметрии многогранника паросочетанийи автоморфизмы графа

Линейные симметрии многогранника паросочетанийи автоморфизмы графа

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

1. Введение

Паросочетанием в графе G=(VG,EG) называется любое (возможно, пустое) множество пар без ребра. Семья всех паросочетаний графа G обозначим через .

Пусть RG - пространство вектор-столбец, компоненты, которые индексируются элементы набора EG. Для любого определим вектор инциденций с компонентами xeR=1 , xeR=0 . Многогранник

для того, чтобы назвать многогранником паросочетаний. Так что любое ребро графа G является паросочетанием, dimMP(Г)=|EG|.

Полиэдральная структура многогранника MP(G) исследовалась многими авторами. В частности, Эдмондсом в [3] впервые дано линейное описание многогранника паросочетаний, Хваталом в [4] был найден комбинаторный критерий смежности его. Нас будет интересовать группа линейного преобразования пространства RG, переводящих многогранник МП(Г) в себе. Более точно: линейной симметрией многогранника MP(G) назовем матрицу такого невырожденного линейного преобразования пространства RG, что для любой пик x многогранника MP(G) изображение также является кончик MP(G). Это легко доказать, в частности, что это преобразование переводит избирательный блок в преддверии того же размера.

Множество всех линейных симметрий многогранника MP(G) образует группу относительно умножения матриц (композиции преобразований), которую мы будем обозначать через L(G). Переходя к экспозиции результатов, отметим, что все основные понятия теории графов используются в настоящей работе в соответствии с монографией [1]. Кроме того, для любого