On a combinatorial optimization problem.pdf Пусть есть n стульев, каждый из которых имеет уникальный порядковый номерi = 1, 2 , . . . , n. Стулья расставлены по окружности. На стулья произвольным образомсадятся n человек так, что на каждом стуле оказывается по одному человеку. Каж-дый человек имеет уникальный порядковый номер j = 1, 2 , . . . , n. Посадка называетсяправильной, если у всех стульев порядковые номера совпадают с номерами сидящихна них людей, в противном случае посадка называется неправильной. Будем называтьперестановкой перемену мест двух сидящих рядом людей. Требуется вычислить наи-меньшее число перестановок d, которые позволят получить правильную посадку изпроизвольной начальной посадки.Перестановки (p,q), указанные в условии задачи, порождают симметрическуюгруппу Sn степени n. Запишем данную группу через порождающие элементы и опреде-ляющие соотношения. Пусть x1 = (1, 2), x2 = (2, 3), ..., x n - 1 = (n - 1, n), xn = (1, n) -порождающие элементы группы Sn. Теперь запишем определяющие соотношения Rдля Sn:x2 = e, i = 1 , 2 , . . . , n,R(x^xj )2 = e, если 1 < |j - i|

Скачать электронную версию публикации