УДК 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]
