В.А. Баранский, Т.А. Сеньчонок. Алгоритм приведения двудольного графа к двудольно-пороговому виду ... С. 54-63

УДК 519.176

MSC: 05A17

DOI: 10.21538/0134-4889-2022-28-4-54-63

Полный текст статьи (Full text)

Тройка $(x, v, y)$ различных вершин графа $G = (V, E)$ такая, что $xv\in E$ и $vy\notin E$, называется повышающей} если $\mathrm{deg}(x) \leq \mathrm{deg}(y)$, и понижающей, если $\mathrm{deg}(x) \geq 2 + \mathrm{deg}(y)$.  Преобразование $\phi$ графа $G$ такое, что $\phi(G) = G - xv + vy$, называется вращением ребра в графе $G$ вокруг вершины $v$, отвечающим тройке $(x, v, y)$. Вращение ребра в графе $G$, отвечающее тройке $(x, v, y)$, называется повышающим, если тройка $(x, v, y)$ повышающая, и понижающим, если тройка $(x, v, y)$ понижающая. Вращение $\phi$ ребра в графе $G$ является повышающим тогда и только тогда, когда обратное к нему вращение ребра в графе $\phi(G)$ является понижающим. Двудольный граф $H = (V_1, E, V_2)$ будем называть двудольно-пороговым графом, если он не имеет повышающих троек таких, что $x, y \in V_1$, $v \in V_2$ или $x, y \in V_2$, $v \in V_1$. Вращение ребра, отвечающее тройке вершин $(x, v, y)$, такое, что $x, y \in V_1$ и $v \in V_2$ ($x, y \in V_2$ и $v \in V_1$), будем называть $V_1$-вращением ($V_2$-вращением) ребра. Любой двудольный граф $H = (V_1, E, V_2)$ можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности $V_1$-вращений ($V_2$-вращений) ребер. Целью работы является построение полиномиального алгоритма, который преобразует любой двудольный граф $H = (V_1, E, V_2)$ в двудольно-пороговый граф с помощью кратчайшей последовательности, состоящей из $V_1$-вращений ребер.

Ключевые слова: алгоритм, разбиение целого числа, пороговый граф, двудольный граф, двудольно-пороговый граф, диаграмма Ферре

СПИСОК ЛИТЕРАТУРЫ

1.   Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. 2-е изд., испр. и доп. СПб.: Лань, 2010. 368 c.

2.   Andrews G.E. The theory of partitions. Cambridge: Cambridge Univ. Press, 1976. 255 p.

3.   Ivanyi A., Lucz L., Gombos G., Matuszka T. Parallel enumeration of degree sequences of simple graphs // Acta Univ. Sapientiae, Informatica. 2012. Vol. 4, no. 2. P. 260–288.

4.   Баранский В.А., Сеньчонок Т.А. Двудольно-пороговые графы // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 2. С. 56–67. doi: 10.21538/0134-4889-2020-26-2-56-67 

5.   Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Amsterdam: North-Holland Publishing Co., 1995. 542 p. (Ser. Annals of Discr. Math.; vol. 56).

6.   Baransky V.A., Senchonok T.A. On maximal graphical partitions that a the nearest to a given graphical partition // Sib. Elect. Math. Reports. 2020. Vol. 17. P. 338–363. doi: 10.33048/semi.2020.17.022 

Поступила 15.08.2022

После доработки 15.09.2022

Принята к публикации 26.09.2022

Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru

Сеньчонок Татьяна Александровна
канд. физ.-мат. наук
доцент
Уральский федеральный университет
г. Екатеринбург
e-mail: tatiana.senchonok@urfu.ru

Ссылка на статью: В.А. Баранский, Т.А. Сеньчонок. Алгоритм приведения двудольного графа к двудольно-пороговому виду // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 4. С. 54-63

English

V.A. Baranskii, T.A. Sen’chonok. An algorithm for taking a bipartite graph to the bipartite threshold form

A triple of different vertices $(x,v,y)$ of a graph $G=(V,E)$ such that $xv \in E$ and $vy \notin E$ is called lifting if $\mathrm{deg}(x) \leq \mathrm{deg}(y)$ and lowering if $\mathrm{deg}(x) \geq 2 + \mathrm{deg}(y)$. A transformation $\phi$ of the graph $G$ that replaces $G$ with $\phi(G) = G - xv + vy$ is called an edge rotation in the graph $G$ about the vertex $v$ corresponding to the triple of vertices $(x, v, y)$. For a lifting (lowering) triple $(x, v, y)$, the corresponding edge rotation is called lifting (lowering). An edge rotation in a graph $G$ is lifting if and only if its inverse is lowering in the graph $\phi(G)$. A bipartite graph $H = (V_1, E, V_2)$ is called a bipartite threshold graph if it has no lifting triples such that $x, y \in V_1$ and $v \in V_2$ or $x,y \in V_2$ and $v \in V_1$. The edge rotation corresponding to a triple of vertices $(x, v, y)$ such that $x,y \in V_1$ and $v \in V_2$ ($x,y \in V_2$ and $v \in V_1$) is called a $V_1$-rotation ($V_2$-rotation) of edges. Every bipartite graph $H = (V_1, E, V_2)$ can be transformed to a bipartite threshold graph by a finite sequence of $V_1$-rotations ($V_2$-rotations) of edges. The aim of the paper is to give a polynomial algorithm that transforms every bipartite graph $H=(V_1,E,V_2)$ to a bipartite threshold graph by a shortest finite sequence of $V_1$-rotations of edges.

Keywords: algorithm, integer partition, threshold graph, bipartite graph, bipartite threshold graph, Ferrers diagram

Received August 15, 2022

Revised September 15, 2022

Accepted September 26, 2022

Vitaly Anatol’evich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: vitaly.baransky@urfu.ru

Tatiana Aleksandrovna Senchonok, Cand. Phys.-Math. Sci., Prof., Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: tatiana.senchonok@urfu.ru

Cite this article as: V.A. Baranskii, T.A. Sen’chonok. An algorithm for taking a bipartite graph to the bipartite threshold form. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 4, pp. 54–63

[References -> on the "English" button bottom right]