Xreferat.com » Рефераты по математике » Линейные симметрии многогранника паросочетанийи автоморфизмы графа

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

графа" width="40" height="17" />. Следовательно,

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

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

Ясно, что последнему пересечению может принадлежать только ребро Линейные симметрии многогранника паросочетанийи автоморфизмы графа.

Таким образом, доказано, что Линейные симметрии многогранника паросочетанийи автоморфизмы графаявляется автоморфизмом графа 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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: