Двудольно-пороговые графы и повышающие вращения ребер в двудольных графах

Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек $(x,v,y)$ таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. Любой двудольный граф $H = (V_1, E, V_2)$ можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности таких двудольных повышающих вращений ребер. В нашей предыдущей работе мы изучили свойства двудольно-пороговых графов и отметили их важность для класса пороговых графов. Теперь мы хотим показать важность этих графов для класса двудольных графов. Под разбиением мы всегда будем понимать невозрастающую последовательность целых неотрицательных чисел, которая содержит лишь конечное число ненулевых компонент. Для любых разбиений $\alpha$ и $\beta$ таких, что $\mathrm{sum}(\alpha) = \mathrm{sum}(\beta)$ и $\alpha\leq\beta^*$, где $\beta^*$ — сопряженное к $\beta$ разбиение, через $\mathrm{BG}(\alpha, \beta)$ будем обозначать семейство двудольных графов $H = (V_1, E, V_2)$, реализующих пару разбиений $(\alpha, \beta)$, т. е. всех таких двудольных графов, что исходная пара разбиений составлена из степеней вершин соответственно первой и второй долей этого графа, дополненных нулями. В данной работе мы даем описание двудольно-пороговых графов, составляющих семейство $\mathrm{BTG}_\uparrow(\alpha, \beta)$, всех двудольно-пороговых графов, которые можно получить из графов семейства $\mathrm{BG}(\alpha, \beta)$ с помощью двудольных повышающих вращений ребер. Также находим наименьшую длину последовательностей двудольных повышающих вращений ребер, переводящих графы из $\mathrm{BG}(\alpha, \beta)$ в графы из $\mathrm{BTG}_\uparrow(\alpha, \beta)$, даем алгоритм, который находит двудольно-пороговый граф, принадлежащий семейству $\mathrm{BG}(\alpha, \beta)$, и получаем описание процедуры, которая позволяет из одного графа семейства $\mathrm{BG}(\alpha, \beta)$ получить все графы этого семейства.