Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

Лемма 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. Ясно, что . Следовательно, . Тем самым доказана взаимнооднозначность соответствия .

Рекомендуем скачать другие рефераты по теме: сочинения по литературе, роботы реферат.

Предыдущая страница реферата | 1  2  3 | Следующая страница реферата