Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями

Рисунок 1. (a) Эквивалентность операций transreversal и revrev на циклических перестановках. (b) Граф разрывов <math>G(\pi)</math> перестановки <math>\pi = [1, -4, 6, -5, 2, -7, -3]</math>, для которого <math>f(\pi) = [1, 2, 8, 7,  11, 12, 10, 9, 3, 4, 14, 13, 6, 5]</math>. <math>G(\pi)</math> удобно изображать на круге таким образом, что его ''черные ребра'' (т. е. ''толстые линии'') располагаются на окружности, а ''серые'' (т. е. ''тонкие'') являются хордами