EssayAI
Блог
Блог
Естественные науки

Граф Кэли: как построить граф группы

8 ноября 2026Время чтения: 8 минут
Граф Кэли: как построить граф группы

Граф Кэли превращает действия с элементами группы в маршруты: вершина изображает элемент, а переход по ребру означает применение выбранной операции. Так таблицу умножения можно исследовать геометрически. Например, сложение вычетов по модулю 8 даёт круг из восьми вершин, если разрешено прибавлять или вычитать единицу.

Попробуйте изменить модуль и шаг в инструменте: он покажет, какие вершины достижимы из нуля и сколько получается компонент. Ниже разберём, почему выбор шага меняет картину и как читать по ней выражения и расстояния.

Вершины и переходы: определение

Пусть дана группа GG с нейтральным элементом ee и выбрано множество элементов SS. Построим ориентированный граф: его вершины - элементы GG, а для каждого g∈Gg\in G и s∈Ss\in S проведём стрелку с меткой ss из gg в gsgs. Здесь используется умножение справа. При сложении вместо gsgs пишут g+sg+s. Правило работает и для бесконечных групп: тогда и вершин бесконечно много. Такое соглашение о правом умножении используется, например, в лекциях по геометрической теории групп Университета Нью-Брансуика.

В литературе обозначение Cay⁡(G,S)\operatorname{Cay}(G,S) часто предполагает, что SS порождает всю группу. Полезно сначала построить ту же схему для любого набора шагов: если он не порождает группу, схема распадётся на части. Именно это позволяет исследовать инструмент выше. В определении важно указывать не только группу, но и набор шагов: одна группа с разными наборами может дать разные графы.

Если вместе с каждым шагом разрешён обратный, стрелки в противоположных направлениях можно объединить в неориентированное ребро. В статье и инструменте для вычетов используется простой неориентированный граф: кратные совпадающие рёбра объединены, петель нет. Например, шаг +k+k и движение по тому же ребру назад соответствуют +k+k и −k-k.

Пример: вычеты по модулю 8

Рассмотрим группу Z/8Z\mathbb Z/8\mathbb Z относительно сложения. Её элементы - остатки 0,1,…,70,1,\ldots,7, нейтральный элемент - 00, а после сложения результат снова берут по модулю 8. Возьмём шаги S={1,−1}S=\{1,-1\}. Из каждой вершины можно перейти к соседним остаткам: например, из 7 прибавление 1 ведёт в 0, а вычитание 1 - в 6.

Получается цикл из восьми вершин и восьми рёбер. Чтобы попасть из 0 в 4, можно четырежды прибавить 1: 0→1→2→3→40\to1\to2\to3\to4. На видео маркер проходит этот маршрут и возвращается по тем же рёбрам; обратный ход наглядно показывает, что у неориентированного ребра разрешены оба направления.

Маркер проходит от 0 до 4 за четыре шага по циклу вычетов и возвращается по тем же рёбрам.

Есть и второй маршрут той же длины: 0→7→6→5→40\to7\to6\to5\to4. Более короткого нет: каждый шаг меняет остаток на единицу в одном из двух направлений, а вершина 4 находится напротив нуля. Поэтому расстояние между ними равно 4. Это максимум расстояний от нуля в данном цикле; по симметрии диаметр тоже равен 4. О том, как определяется диаметр графа, можно прочитать отдельно.

Почему выбор образующих важен

Теперь оставим ту же группу, но разрешим шаги +2+2 и −2-2. Из нуля достижимы только чётные остатки: 0,2,4,60,2,4,6. Из единицы получаем только нечётные: 1,3,5,71,3,5,7. Каждая четвёрка образует собственный цикл, а перехода между ними нет. При смене разрешённых шагов группа не изменилась, но её схема переходов стала несвязной.

Шаги плюс и минус два по модулю восемь разделяют вершины на чётную и нечётную компоненты
Шаги плюс и минус два по модулю восемь разделяют вершины на чётную и нечётную компоненты

В общем случае для вычетов по модулю nn и шагов ±k\pm k число компонент равно gcd⁡(n,k)\gcd(n,k), а в каждой находится n/gcd⁡(n,k)n/\gcd(n,k) вершин. Так, gcd⁡(8,2)=2\gcd(8,2)=2, поэтому компонент две, по четыре вершины. При gcd⁡(n,k)=1\gcd(n,k)=1 граф связен. Инструмент вычисляет расстояния обходом, а число компонент - по этому правилу; проверьте, например, пары (8,1)(8,1) и (8,2)(8,2).

Почему действует формула? Все достигнутые из нуля остатки кратны d=gcd⁡(n,k)d=\gcd(n,k). Обратно, по тождеству Безу dd выражается целой комбинацией nn и kk, а значит, по модулю nn достижим и каждый кратный dd остаток. Из любой другой вершины получается сдвиг той же четвёрки или, в общем случае, того же множества. Эти сдвиги разбивают все остатки на dd классов.

Слова, маршруты и кратчайшие пути

Путь из ee с последовательными метками s1,…,sms_1,\ldots,s_m заканчивается в элементе s1s2⋯sms_1s_2\cdots s_m. Такое выражение называют словом в образующих. Если путь возвращается в ee, соответствующее произведение равно нейтральному элементу. В примере с вычетами восемь шагов +1+1 возвращают в ноль: это геометрическое проявление равенства 8⋅1=08\cdot1=0 по модулю 8.

Кратчайшее расстояние от ee до gg - минимальное число разрешённых шагов, которыми можно выразить gg. Если множество шагов симметрично, обратные элементы входят в разрешённый набор. Для поиска пути в конечном невзвешенном графе подходит обход в ширину: он посещает вершины слоями и позволяет восстановить маршрут по предкам. Если вершина лежит в другой компоненте, конечного расстояния до неё нет.

Например, в графе с шагами ±2\pm2 расстояние от 0 до 4 равно двум: 0→2→40\to2\to4. До 1 пути нет. Это отличается от расстояния 4 до вершины 4 при шагах ±1\pm1: расстояние зависит от выбранного набора операций, а не только от группы.

Ещё один способ проверить результат - выписать слои от нуля. При шаге единица в первом слое находятся вершины 1 и 7, во втором - 2 и 6, в третьем - 3 и 5, а в четвёртом остаётся вершина 4. Каждая вершина появляется впервые на минимальном расстоянии: если бы существовал более короткий маршрут, обход обнаружил бы её в одном из предыдущих слоёв. Этот приём полезен, когда граф сложнее простого цикла и расстояние нельзя сразу увидеть на рисунке.

Для шага два слои другие: сначала 0, затем 2 и 6, затем 4. После этого новых вершин не появляется. Не следует записывать расстояние до нечётных вершин как ноль: нулевое расстояние имеет только исходная вершина. В инструменте недостижимые вершины отмечены отдельно, а не включены в измерение расстояния.

Связность и симметрия

Стартуя в нейтральном элементе и проходя рёбра в обе стороны, мы получаем ровно подгруппу ⟨S⟩\langle S\rangle, порождённую выбранными шагами и их обратными. Поэтому неориентированная схема связна тогда и только тогда, когда ⟨S⟩=G\langle S\rangle=G. В ориентированной версии для движения только по стрелкам нужно отдельно учитывать допустимость обратных шагов; для произвольной бесконечной группы одна лишь порождаемость с обратными не гарантирует достижимость по направлениям стрелок.

Если группа конечна, все компоненты имеют одинаковый размер: компонента вершины gg состоит из элементов вида ghgh, где h∈⟨S⟩h\in\langle S\rangle. Это левый смежный класс подгруппы. Число компонент равно её индексу, а размер подгруппы делит порядок группы по теореме Лагранжа.

Ещё одна симметрия видна из правила стрелок: левое умножение всех вершин на один элемент aa переводит ребро g→gsg\to gs в ребро ag→agsag\to ags с той же меткой. Поэтому любая вершина может играть роль начала отсчёта. Это пример действия группы на множестве, сохраняющего структуру размеченного графа.

Как построить граф для другой группы

Сначала выпишите элементы группы и уточните порядок операции. Затем выберите набор SS и для каждого элемента gg найдите gsgs при всех s∈Ss\in S. Добавьте стрелки с метками; если нужна неориентированная схема, проверьте наличие обратных шагов и соглашение о совпадающих рёбрах. В конце проверьте, сколько вершин достижимо из единицы и какие слова соответствуют найденным маршрутам.

Для некоммутативной группы порядок особенно важен: в общем случае gsgs и sgsg различны. Например, при работе с симметриями квадрата композиция поворота и отражения зависит от порядка. Нельзя без проверки заменить умножение справа умножением слева или переставить метки в слове. Рисунок может выглядеть иначе и из-за расположения вершин на плоскости: существенны сами связи и их метки, а не форма линий.

Частые ошибки

  • Считать, что вершины - это образующие. Вершинами служат все элементы группы, а образующие задают переходы.
  • Забывать обратный шаг. В ориентированном графе движение против стрелки не разрешено автоматически; в неориентированном варианте обратный переход предусмотрен.
  • Делать вывод о связности по одному фрагменту. Нужно проверить достижимость всех вершин или доказать, что выбранные элементы порождают группу.
  • Забывать модуль или порядок умножения. Результат каждого перехода вычисляют в заданной группе и по выбранному соглашению.
  • Считать каждую стрелку отдельным неориентированным ребром. При переходе к простому графу совпадающие рёбра объединяются; если нужны кратные рёбра, соглашение надо указать.

FAQ

Граф Кэли обязательно конечен?

Нет. Для целых чисел с шагами ±1\pm1 он представляет собой бесконечную цепочку. Конечность графа следует из конечности группы.

Можно ли восстановить группу только по рисунку?

Не всегда. Без меток рёбер и указания нейтральной вершины часть алгебраической информации теряется; одинаковый неразмеченный граф может возникнуть из разных конструкций. Поэтому при задачах сохраняют обозначения шагов и соглашение об операции.

Всегда ли число соседей равно числу шагов?

В ориентированной размеченной схеме разные элементы множества SS дают разные исходящие стрелки из каждой вершины. В простом неориентированном графе обратные стрелки объединяются, а петли могут исключаться, поэтому число рёбер нужно считать с учётом соглашений.

Коротко

Граф Кэли задаётся группой и выбранными шагами: вершины изображают элементы, рёбра - операции, а маршруты - слова в образующих. Связность показывает, порождают ли шаги всю группу, а длина кратчайшего пути измеряет минимальное число операций. Для вычетов по модулю 8 шаги ±1\pm1 дают один цикл, а шаги ±2\pm2 - две компоненты.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

8 ноября 20268 минут
Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

8 ноября 20268 минут
Дополнение графа: определение и построение

Дополнение графа: определение и построение

Как построить дополнение простого графа по рёбрам и матрице смежности, проверить число рёбер и степени вершин и использовать связь клик с независимыми множествами.

8 ноября 20269 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Группа диэдра: симметрии и преобразования многоугольника

Группа диэдра: симметрии и преобразования многоугольника

Группа диэдра описывает повороты и отражения правильного многоугольника. Разбираем порядок группы, соотношения образующих и композицию на примере квадрата.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут