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

Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется 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-скрученным.