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

Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5) (посмотреть исходный код)

74 байта добавлено , 1 марта 2019

4501

правка

@@ Строка 11: / Строка 11: @@
 [[Файл:Sort_transp_1.png]]
-Рисунок 1. (a) Эквивалентность операций transreversal и revrev на циклических перестановках. (b) Граф разрывов G(JT) перестановки ж = [1,-4,6,-5,2, -7,-3], для которого f(n) = [1;2;8;7; 11; 12; 10;9; 3;4; 14; 13;6;5]. Граф G(n) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами
+Рисунок 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> удобно изображать на круге, так, что его ''черные ребра'' (т. е. ''толстые линии'') располагаются на окружности, а ''серые'' (т. е. ''тонкие'') являются хордами
 == Основные результаты ==