Теоретическая кибернетика

Рассматривается задача оценки сложности разложения элементов симметрической группы в произведение транспозиции (12) и циклических сдвигов. Задачу разложения удобно интерпретировать как задачу о кратчайших путях в специальном графе, вершинами которого являются перестановки, а рёбра соответствуют применению транспозиции и сдвигов. Такой граф называется графом Кэли; его диаметр отражает наибольшую сложность разложения, то есть длину самого длинного минимального представления элемента через выбранные операции. Установлена нижняя оценка диаметра графа Кэли, равная верхней гипотетической.