Граф Кэли

Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.

Определение

Пусть дана дискретная группа $G$ и система образующих $S$ .

Предположим $S=S^{-1}$ , то есть $\forall s\in S\ \ \exists s^{-1}\in S$ .

Графом Кэли группы $G$ по системе образующих $S$ является граф, вершинами которого являются элементы группы, и элемент $g$ соединён ребром в точности с теми элементами, которые получаются домножением $g$ на элемент из $S$ .

Замечание: В случае если $S\not =S^{-1}$ , вместо $S$ берут объединение $S\cup S^{-1}$ .

Примеры

Граф Кэли свободной группы с двумя образующими a и b
Граф Кэли свободного произведения $\mathbb {Z} _{2}*\mathbb {Z} _{3}$
Граф Кэли прямого произведения $\mathbb {Z} _{2}\times \mathbb {Z} _{3}$

См. также

Похожие исследовательские статьи

Фундамента́льная гру́ппа — одна из простейших конструкций в алгебраической топологии. Сопоставляется группа всякому связному топологическому пространству. Для подмножеств плоскости эта группа измеряет количество «дырок». Наличие «дырки» определяется невозможностью непрерывно продеформировать (стянуть) некоторую замкнутую кривую в точку.

Счётное множество — бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество $\text{[math]}$ является счётным, если существует биекция со множеством натуральных чисел: $\text{[math]}$ , другими словами, счётное множество — это множество, равномощное множеству натуральных чисел. В иерархии алефов мощность счётного множества обозначается $\text{[math]}$ («алеф-нуль»).

А́белева гру́ппа — группа, в которой групповая операция является коммутативной; иначе говоря, группа $\text{[math]}$ абелева, если $\text{[math]}$ для любых двух элементов $\text{[math]}$ .

В математике, если заданы две группы (G, ∗) и (H, •), гомоморфизм групп из (G, ∗) в (H, •) — это функция h : G → H, такая, что для всех u и v из G выполняется

\text{[math]}

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

Циклическая группа — группа $\text{[math]}$ , которая может быть порождена одним элементом a, то есть все её элементы являются степенями a. Математическое обозначение: $\text{[math]}$ .

Прямое произведение групп — операция, которая по группам $\text{[math]}$ и $\text{[math]}$ строит новую группу, обычно обозначающуюся как $\text{[math]}$ . Эта операция является теоретико-групповым аналогом декартова произведения множеств и одним из основных примеров понятия прямого произведения.

Изоморфизм групп — взаимно-однозначное соответствие между элементами двух групп, сохраняющее групповые операции. Если существует изоморфизм между двумя группами, группы называются изоморфными. С точки зрения теории групп изоморфные группы имеют одни и те же свойства и их можно не различать.

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

<span class="mw-page-title-main">Конечная группа</span> алгебраическая структура - группа, содержащая конечное число элементов

Конечная группа в общей алгебре — группа, содержащая конечное число элементов. Далее группа предполагается мультипликативной, то есть операция в ней обозначается как умножение; аддитивные группы с операцией сложения оговариваются особо. Единицу мультипликативной группы будем обозначать символом 1. Порядок группы $\text{[math]}$ принято обозначать $\text{[math]}$

Гиперболическая группа — конечно-порождённая группа, граф Кэли которой, как метрическое пространство, является гиперболическим по Громову.

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

Порождающее множество группы $\text{[math]}$ — это подмножество $\text{[math]}$ в $\text{[math]}$ , такое, что каждый элемент $\text{[math]}$ может быть записан как произведение конечного числа элементов $\text{[math]}$ и их обратных.

Теорема Кэли — теоретико-групповое утверждение об изоморфности всякой конечной группы $\text{[math]}$ порядка $\text{[math]}$ некоторой подгруппе группы перестановок $\text{[math]}$ . При таком соответствии каждый элемент $\text{[math]}$ сопоставляется с перестановкой $\text{[math]}$ , задаваемой тождеством $\text{[math]}$ , где $\text{[math]}$ — произвольный элемент группы $\text{[math]}$ .

Решётка — набор векторов евклидова пространства $\text{[math]}$ , образующий дискретную группу по сложению.

Бесконечная группа — группа с бесконечным числом элементов, в противоположность конечным группам. Первое исследование бесконечных групп восходит к Жордану (1870).

В общей алгебре, термин кручение относится к элементам группы, имеющим конечный порядок, или к элементам модуля, аннулируемым регулярным элементом кольца.

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

Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует $\text{[math]}$ времени, где $\text{[math]}$ — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за $\text{[math]}$ , если исследуемая бинарная операция обратима. Первый вероятностный тест, улучшающий время работы с $\text{[math]}$ до $\text{[math]}$ , был предложен в 1996 году Шридхаром Раджагопаланом и Леонардом Шульманом. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время $\text{[math]}$ , что является улучшением по сравнению с поиском Гровера, работающим за $\text{[math]}$ .

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

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.