Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
'''Типы циклов''' | '''Типы циклов''' | ||
Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется 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-скрученным. | |||
[[Файл:Sort_transp_2.png]] | |||
Рисунок 2. Конфигурации 3-циклов. (a) Неориентированный, 0-скрученный 3-цикл. (b) Неориентированный, 1-скрученный 3-цикл. (c) Ориентированный, 2-скрученный 3-цикл. (d) Ориентированный, 3-скрученный 3-цикл. (e) Пара пересекающихся 3-циклов. (f) Пара чередующихся 3-циклов | |||
'''Конфигурации циклов''' | |||