[МУЗЫКА] [МУЗЫКА] Наша сегодняшняя лекция посвящена графам Кэли. Это графы на группах, которые порождаются некоторым множеством. Итак, рассмотрим конечную группу G с порождающим множеством S. Множество S называется свободным от единичного элемента, если единичный элемент не принадлежит этому множеству, и называется симметричным, если для всякого порождающего элемента обратный к нему также принадлежит этому множеству. Графом Кэли на конечной группе G относительно порождающего множества S называется граф с с множеством вершин, содержащим все элементы группы и с множеством рёбер, состоящих из элементов группы и его произведения справа на элемент порождающего множества. Таким образом, по определению, всякий граф Кэли не содержит петель, поскольку порождающее множество свободно от единичного элемента, и граф является неориентированным в силу симметричности порождающего множества. Давайте рассмотрим простейшие примеры графов Кэли. Полный граф на n вершинах является графом Кэли на конечной аддитивной группе целых чисел по модулю n относительно порождающего множества всех его ненулевых элементов. Если же мы рассмотрим цикл длины n, то он также будет являться графом Кэли на той же самой группе, только в том случае, если мы с вами возьмём два элемента, два порождающих элемента — сам элемент и обратный к нему. С другой стороны, например, цикл длины 6 можно построить как граф Кэли на симметрической группе степени 3 в том случае, если порождающим множеством будут являться элементы транспозиции (12) и (13). И на той же самой группе, на симметричной группе степени 3 можно построить граф, который будет изоморфен двудольному графу K33, в том случае, если вы возьмёте все транспозиции. Таким образом, с одной стороны графы Кэли на одной и той же группе с разными порождающими множествами необязательно будут являться изоморфными, это показывают первый и второй рассмотренные нами примеры. На аддитивной группе мы получили с вами полный граф и цикл на n вершинах. С другой стороны, графы Кэли на разных группах могут оказаться изоморфными. И это показывают второй и третий примеры. А теперь давайте рассмотрим основные свойства графов Кэли, которые формулируются следующими фактами. Итак, пусть у нас имеется порождающее множество S некоторой конечной группы G. Тогда граф Кэли на этой конечной группе G относительно порождающего множества S является связным, регулярным, при этом его регулярность совпадает с порядком, или с мощностью порождающего множества, а кроме этого, граф является вершинно‐транзитивным. В самом деле, поскольку S является порождающим множеством, следовательно, для любой вершины нашего графа существует путь, который соединяет единичный элемент с любой другой вершиной. Значит, граф является связным. Далее. Поскольку множество S является симметричным, следовательно, каждая вершина этого графа будет иметь степень, равную мощности порождающего множества. Тем самым, мы имеем регулярный граф. Ну и наконец, граф Кэли является вершинно‐транзитивным, поскольку отображение любой вершины v в вершину gv является автоморфизмом для любой вершины нашего графа. Для этого нужно проверить то соотношение, которе вы сейчас видите у себя на слайде. То есть мы берём обратный элемент gu, умножаем его на элемент gv, и мы получаем с вами, что это то же самое, что взять элемент u в (-1) степени и умноженное на v. По определению графа Кэли, вершины u и v являются смежными, если существует S такой, что он будет равен u ∧ (-1) * v. А это и значит, что наши образы gu и gv также являются смежными вершинами. Тем самым мы с вами показали, что указанное отображение действительно является автоморфизмом, а всякий граф Кэли будет являться вершинно‐транзитивным. А вот обратное утверждение не всегда является верным, то есть не всякий вершинно‐транзитивный граф является графом Кэли. Приведём идею доказательства этого факта, которая принадлежит Норману Биггсу. Он показал, что простейшим примером вершинно‐транзитивного графа, который не будет являться графом Кэли, служит граф Петерсена. В самом деле, граф Петерсена является кубическим связным графом на 10 вершинах, и диаметр этого графа равен 2. Теперь давайте мы с вами предположим, что существует граф Кэли, который будет изоморфен графу Петерсена. Для этого нам нужно с вами найти группу и порождающее множество, такие, чтобы мы могли построить соответствующий граф Кэли. Пусть группа G содержит 10 элементов, а порождающее множество содержит три элемента. Тогда в этом случае имеются только две неизоморфные группы порядка 10, и именно такими будут являться диэдральная группа порядка 5 и аддитивная группа на 10 элементах. Если проверить все трёхэлементные порождающие множества этих групп, то вы увидите, что невозможно построить граф, диаметр которого был бы равен 2. Давайте с вами рассмотрим какой‐нибудь один случай. Возьмём аддитивную группу Z10 и посмотрим, какие трёх элементные множества могут быть использованы в качестве порождающих множеств. Это у нас будут множества {1, 9, 5}... Почему так? Мы помним о том, что множество должно быть симметричным. То есть если какой‐то элемент принадлежит множеству, то и обратный тоже должен ему принадлежать. Тем самым, если мы выбрали 1, 9 тоже попадает, а 5 является инволюцией. Другими множествами будут являться {2, 8, 5}, {3, 7, 5}, а также {4, 6, 5}. Так вот, если мы любое из этих множеств будем брать, у нас всегда будет получаться граф диаметра больше 2. Давайте с вами проверим какой‐нибудь один случай. Возьмём, например, первое порождающее множество, состоящее из элементов {1, 9, 5}, и начнём постепенно строить граф Кэли таким образом, что у нас имеется начальная вершина 0, и относительно её мы будем строить граф. Тогда соседство этой вершины — это будут элементы порождающего множества, а во второй слой попадут вершины 2, 6, 4, 8, а в третий слой попадут вершины 3 и 7. Что мы с вами имеем? Мы имеем граф диаметра 3. Он никак не может быть изоморфен нашему графу Петерсена. Более того, построенный нами граф содержит четыре цикла, в то время как граф Петерсена такие цифры не содержит. Таким образом, мы с вами только что доказали утверждение о том, что не всякий вершинно‐транзитивный граф является графом Кэли.
