Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Линейные симметрии многогранника паросочетанийи автоморфизмы графа
Раздел: Рефераты по математике
Тип: статья Добавлен 13:58:06 24 марта 2007 Похожие работы
Просмотров: 220 Комментариев: 2 Оценило: 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.

Лемма 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, что также противоречит выбору вершины 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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:53:12 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:53:01 24 ноября 2015

Работы, похожие на Статья: Линейные симметрии многогранника паросочетанийи автоморфизмы графа

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151059)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru