[МУЗЫКА] [МУЗЫКА] Добрый день, дорогие слушатели нашего замечательного курса! Сегодня мы с вами начинаем модуль № 3, в котором будет показана связь теории графов и теории групп. Графы, которые задаются на группе, называются графами Кэли, и они были введены в 1878 году английским математиком Артуром Кэли для представления и объяснения такого понятия, как абстрактная группа, которая порождается множеством генераторов. В последние годы теория графов Кэли становится всё более самостоятельной областью алгебраической теории графов. Сами графы Кэли возникают в различных отраслях знаний, а также используются при решении различных задач, как классических, так и прикладных. Кроме этого, известно, например, что основой геометрической теории групп стала геометрия графов Кэли. В рамках нашего модуля — модуля № 3 — мы поговорим о том, как возникают автоморфизмы на множестве вершин и множестве рёбер графа, как транзитивность графа связана с таким понятием, как их регулярность. Мы также узнаем, всякие ли вершинно-транзитивные графы являются графами Кэли, а кроме этого, поговорим о том, вообще откуда возникают графы Кэли в других областях знания. Мы рассмотрим два семейства важных графов, а именно графа Хэминга и графа Джонсона, которые в первом случае являются графами Кэли, а во втором, в общем случае не являются графами Кэли. Но они будут являться очень важным объектом исследования в нашем последнем, шестом модуле этого цикла. Итак, наша первая лекция сегодняшнего нового модуля — модуля № 3 — будет посвящена автоморфизмам графа. По определению, автоморфизмом графа называется отображение α множества вершин на себя, при котором сохраняется смежность вершин, то есть если {u, v} является ребром графа, то тогда {α(u), α(v)} также является ребром графа. Очевидно, что автоморфизм переводит друг в друга только вершины, имеющие одну и ту же степень. Если же у графа имеется единственный, тождественный автоморфизм на множестве вершин, то граф в этом случае называется асимметричным. Известно, что не существует асимметричных графов на множестве вершин с двумя, тремя, четырьмя и пятью вершинами. Но имеется первый граф, который возникает у нас и является асимметричным — он возникает на шести вершинах. Вы его сейчас видите на слайде. На самом деле это один из восьми возможных асимметричных графов. Легко видеть, что ни одна вершина этого графа не может быть переведена ни в какую другую вершину никаким автоморфизмом. Потренируйтесь, пожалуйста, самостоятельно и попробуйте найти все остальные асимметричные графы на шести вершинах. А теперь мы с вами поговорим о группах автоморфизмов графа. Множество автоморфизмов графа образует вершинную группу графа, или ещё её называют просто группой графа. Группа автоморфизмов на множестве рёбер называется рёберной группой графа. Заметим, что вершинные автоморфизмы естественным образом индуцируют рёберные автоморфизмы, и о том, как это происходит, мы с вами сейчас посмотрим на примере. Давайте с вами рассмотрим граф с четырьмя вершинами и пятью рёбрами — вы его сейчас видите на слайде. Вершинная группа этого графа состоит из перестановок следующего вида: это у нас тождественная перестановка, далее — перестановка второй и четвёртой вершин, далее — перестановка первой и третьей вершин и, наконец, их попарные перестановки. Таким образом, мы построили с вами вершинную группу автоморфизмов нашего графа. Нетрудно показать, что соответствующие этим автоморфизмам рёберные автоморфизмы получаются так, что мы с вами имеем тождественную перестановку, далее у нас имеется перестановка первого и четвёртого, а также второго и третьего рёбер, далее — перестановка первого и второго, а также третьего и четвёртого рёбер, и, наконец, первого и третьего, а также второго и четвёртого рёбер. Тем самым мы с вами получили рёберную группу автоморфизмов нашего графа. Заметим только, что рёберная и вершинная группа автоморфизмов этого графа изоморфны, но не идентичны, поскольку степень первой группы — 4, а второй — 5. А вот в общем случае необходимое и достаточное условие изоморфизма рёберной и вершинной групп графа формулируются следующей теоремой: рёберная и вершинная группы графа изоморфны тогда и только тогда, когда граф имеет не более одной изолированной вершины, а полный граф на двух вершинах не является его компонентой. Доказательство этого факта можно найти в книге Фрэнка Харари «Теория графов». И вот сейчас давайте мы с вами рассмотрим несколько примеров графов, а также групп их автоморфизмов. Начнём с семейства полных графов. Нетрудно показать, что группой автоморфизмов изолированной вершины — точки, а это у нас K1 — будет являться симметрическая группа степени 1. Граф K2 имеет симметрическую группу степени 2, а группами автоморфизмов графов K3 и K4 будут соответственно являться симметрическая группа степени 3 и степени 4. Таким образом, в самом общем виде симметрическая группа степени n является группой автоморфизмов любого полного графа на n вершинах. Также нетрудно показать, что эта же самая группа будет являться группой автоморфизмов пустого графа на n вершинах. В целом известен следующий факт, который был доказан в 1938 году Робертом Фрухтом. Он говорит нам следующее: что любая конечная группа изоморфна группе автоморфизмов некоторого конечного неориентированного графа. Так, например, диэдральная группа степени n является группой автоморфизмов любого цикла длины n. Напомню вам, что по определению диэдральная группа степени n состоит из 2n-элементов, таких что у нас имеется n элементов, соответствующих поворотам на угол 2πκ/n, а также ещё n элементов, которые соответствуют отражению относительно прямых, которые проходят через центр нашего многоугольника, а также середины его сторон или же через сами вершины этого n-угольника. И порождающее множество диэдральной группы степени n состоит из двух преобразований — это поворот на угол 2π/n и любого из отражений. Таким образом, диэдральная группа степени n состоит из вращений и отражений правильного n-угольника, или же n-цикла. Теперь давайте мы с вами поговорим немного о регулярных графах с тривиальной группой автоморфизмов. Напомню вам, что граф называется регулярным степени κ, если все его вершины имеют степень κ, а регулярный граф степени 3 называется кубическим. Мы рассматривали подробно такие графы в первом модуле нашего курса. Напомню также, что всякий цикл является 2-регулярным, а значит, его группой автоморфизмов является только что рассмотренная диэдральная группа. Минимальным примером кубического графа с тривиальной группой является граф Фрухта, который вы сейчас видите у себя на слайде. Таким образом, этот граф — граф Фрухта — является асимметричным графом. На самом деле известно, что существует бесконечное число асимметричных кубических графов.
