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

'''Преобразование в 3-перестановки'''

Перестановка называется ''простой'', если ее граф разрывов содержит только k-циклы, где <math>k \le 3</math>. Простая перестановка также называется ''3-перестановкой'', если она не содержит 2-циклов. Преобразование из <math>\pi</math> в <math>\hat{\pi}</math> называется ''безопасным'', если <math>n(\pi) - c_{odd}(\pi) = n(\hat{\pi}) - c_{odd}(\hat{\pi})</math>. Было показано, что любая перестановка <math>\pi</math> может быть преобразована в простую перестановку <math>\pi'</math> при помощи безопасных преобразований и, более того, что любая сортировка <math>\pi'</math> имитирует сортировку <math>\pi</math> с тем же количеством операций [6, 11]. Хартман и Шаран [8] также показали, что любая простая перестановка <math>\pi'</math> может быть преобразована в 3-перестановку <math>\hat{\pi}</math> при помощи безопасных операций заполнения (преобразующих эти 2-циклы в 1-скрученные 3-циклы) и, более того, что любая сортировка <math>\hat{\pi}</math> имитирует сортировку <math>\pi'</math> с тем же количеством операций. Основываясь на этих двух свойствах, можно заключить, что произвольная перестановка <math>\pi</math> может быть преобразована в 3-перестановку <math>\hat{\pi}</math>, такую, что любая сортировка <math>\hat{\pi}</math> имитирует сортировку <math>\pi</math> с тем же количеством операций, предполагая, что можно ограничить рассмотрение только циклическими 3-перестановками.

'''Типы циклов'''

Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется k-операцией, если она увеличивает число нечетных циклов на k. (0, 2, 2)-последовательностью называется последовательность из трех операций, первая из которых является 0-операцией, а две другие – 2-операциями. Нечетный цикл называется ориентированным, если существует 2-операция, действующая на трех его черных ребрах; в противном случае он является неориентированным. Конфигурация циклов представляет собой подграф графа разрывов, содержащий один или несколько циклов. Как показано на рис. 2(a-d), существуют четыре возможных конфигурации одиночных 3-циклов. Черное ребро называется скрученным, если два его смежных серых ребра пересекают друг друга в циклическом графе разрывов. Цикл является k-скрученным, если k из его черных ребер скручены. Например, 3-циклы на рис. 2(a-d) являются 0-, 1-, 2- и 3-скрученными, соответственно. Хартман и Шаран заметили, что 3-цикл является ориентированным в том или только том случае, если он оказывается 2- или 3-скрученным.