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

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

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

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.

Лемма 2. Нехай . Ребра суміжні в G, як і лише коли ребра і суміжні в G.

Доказательство. Слід з леми 1.

Основываясь у тому, що багато всіх перестановок на EG є кінцевою групою, легко показати, що й для даної перестановки образи суміжних в G ребер суміжні, те й прообрази суміжних ребер теж суміжні.

Следующая лема відіграє при побудові ізоморфізму груп Aut (G) і SG.

Лемма 3. Якщо образи суміжних в G ребер при перестановці суміжні в G, то для будь-який існує така вершина , що .

Доказательство. Для позначимо , p>1. Припустимо, що ребра образу немає загальної вершини. Тоді серед ребер , , є несмежные, або є циклом довжини 3. У першому випадку отримуємо в протиріччя з умовою теореми, бо uui, , попарно суміжні. Другий випадок розглянемо докладніше.

Пусть p=3 і , і . Оскільки G зв’язний і |VG|>4, що існує вершина , яка смежна з якоюсь з вершин u1, u2,u3, — скажімо, з u1. Оскільки uu1 і u1s суміжні, то vw і теж суміжні. У цьому якщо вони суміжні по вершині v, то отримуємо суміжність ребер і як і слідство, — суміжність ребер u1s і uu3, що це неправда. Якщо ж vw і суміжні по вершині w, то аналогічно отримуємо суміжність ребер u1s і uu2, що також суперечить вибору вершини p. s. Отже, при p=3 ребра що неспроможні утворювати циклу.

Итак, якщо не висяча вершина, то тут для неї є така , що . З умови збереження суміжності ребер і взаимнооднозначности перестановки випливає, що це включення є рівністю, тобто . Неважко побачити, що це рівність виконується й у висячих вершин графа G.

Теперь, виходячи з лемме 3, визначимо відповідність правилом: , як і лише коли , де — перестановка на EG, яка зберігає суміжність ребер. Легко помітити, що є перестановкою. Покажемо, що вона суміжність вершин графа G. Справді, всяке ребро можна уявити, як те що множин і . Отже,.

.

.

Ясно, що останньому перетинанню може належати лише ребро .

Таким чином, доведено, що є автоморфизмом графа G, причому індукує перестановку .

Проведенные міркування сформулюємо як теореми.

Теорема 1. Перестановка индуцирована деяким автоморфизмом графа G тоді і тільки тоді ми, коли образи суміжних в G ребер при перестановці суміжні.

Переход до групи SG здійснюється з допомогою наступного результату.

Теорема 2. Перестановка на безлічі EG индуцирована деяким автоморфизмом графа G тоді і тільки тоді ми, коли .

Доказательство. Достатність. З огляду на леми 2, образи суміжних в G ребер при перестановці суміжні. Отже, по теоремі 1, индуцирована деяким автоморфизмом графа G.

Необходимость. По теоремі 1, образи суміжних ребер суміжні. Покажемо, що нічого для будь-якого . Справді, якщо суміжні, то і теж суміжні, чого не може, бо і належать H.

Теорема 2 дозволяє укласти, що відповідність « індукує », певне на початку даного параграфа, є відображенням групи Aut (G) на SG. Означимо його через .

Теорема 3. Відповідність є изоморфизмом груп Aut (G) і SG.

Доказательство. Справді, якщо і — два різних автоморфизма, що існує така вершина , що . Нехай , i=1,2. Зрозуміло, що . Отже, . Тим самим було доведено взаимнооднозначность відповідності .

Далее, вважаючи і , одержимо.

.

.

Теорема доведено.

Итак, підсумовуючи отримані результати, отримуємо изоморфность групи лінійних симетрій багатогранника паросочетаний і групи автоморфизмов відповідного графа.

В висновок відзначимо, що аналогічні результати про симметриях багатогранника матроида отримані О. В. Червяковым у роботі [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.

Для підготовки даної роботи було використані матеріали із сайту internet.