Тройка (x,v,y) различных вершин графа G=(V,E) такая, что xv∈E и vy∉E, называется повышающей, если deg(x)≤deg(y), и понижающей, если deg(x)≥2+deg(y). Преобразование ϕ графа G такое, что ϕ(G)=G−xv+vy, называется вращением ребра в графе G вокруг вершины v, отвечающим тройке (x,v,y). Вращение ребра в графе G, отвечающее тройке (x,v,y), называется повышающим, если тройка (x,v,y) повышающая, и понижающим, если тройка (x,v,y) понижающая. Вращение ϕ ребра в графе G является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе ϕ(G) является понижающим. Двудольный граф H=(V1,E,V2) будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что x,y∈V1, v∈V2 или x,y∈V2, v∈V1. Вращение ребра, отвечающее тройке вершин (x,v,y), такое, что x,y∈V1 и v∈V2 (x,y∈V2 и v∈V1), будем называть V1-вращением (V2-вращением) ребра. Любой двудольный граф H=(V1,E,V2) можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности V1-вращений (V2-вращений) ребер. Целью работы является построение полиномиального алгоритма, который преобразует любой двудольный граф H=(V1,E,V2) в двудольно-пороговый граф с помощью кратчайшей последовательности, состоящей из V1-вращений ребер.
