TY - JOUR

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

AU - Баранский, Виталий Анатольевич

AU - Сеньчонок, Татьяна Александровна

PY - 2023

Y1 - 2023

N2 - Двудольный граф H=(V1,E,V2) будем называть двудольно-пороговым графом, если он не имеет повышающих троек (x,v,y) таких, что x,y∈V1, v∈V2 или x,y∈V2, v∈V1. Любой двудольный граф H=(V1,E,V2) можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности таких двудольных повышающих вращений ребер. В нашей предыдущей работе мы изучили свойства двудольно-пороговых графов и отметили их важность для класса пороговых графов. Теперь мы хотим показать важность этих графов для класса двудольных графов. Под разбиением мы всегда будем понимать невозрастающую последовательность целых неотрицательных чисел, которая содержит лишь конечное число ненулевых компонент. Для любых разбиений α и β таких, что sum(α)=sum(β) и α≤β∗, где β∗ - сопряженное к β разбиение, через BG(α,β) будем обозначать семейство двудольных графов H=(V1,E,V2), реализующих пару разбиений (α,β), т. е. всех таких двудольных графов, что исходная пара разбиений составлена из степеней вершин соответственно первой и второй долей этого графа, дополненных нулями. В данной работе мы даем описание двудольно-пороговых графов, составляющих семейство BTG↑(α,β), всех двудольно-пороговых графов, которые можно получить из графов семейства BG(α,β) с помощью двудольных повышающих вращений ребер. Также находим наименьшую длину последовательностей двудольных повышающих вращений ребер, переводящих графы из BG(α,β) в графы из BTG↑(α,β), даем алгоритм, который находит двудольно-пороговый граф, принадлежащий семейству BG(α,β), и получаем описание процедуры, которая позволяет из одного графа семейства BG(α,β) получить все графы этого семейства.

AB - Двудольный граф H=(V1,E,V2) будем называть двудольно-пороговым графом, если он не имеет повышающих троек (x,v,y) таких, что x,y∈V1, v∈V2 или x,y∈V2, v∈V1. Любой двудольный граф H=(V1,E,V2) можно преобразовать в двудольно-пороговый граф с помощью конечной последовательности таких двудольных повышающих вращений ребер. В нашей предыдущей работе мы изучили свойства двудольно-пороговых графов и отметили их важность для класса пороговых графов. Теперь мы хотим показать важность этих графов для класса двудольных графов. Под разбиением мы всегда будем понимать невозрастающую последовательность целых неотрицательных чисел, которая содержит лишь конечное число ненулевых компонент. Для любых разбиений α и β таких, что sum(α)=sum(β) и α≤β∗, где β∗ - сопряженное к β разбиение, через BG(α,β) будем обозначать семейство двудольных графов H=(V1,E,V2), реализующих пару разбиений (α,β), т. е. всех таких двудольных графов, что исходная пара разбиений составлена из степеней вершин соответственно первой и второй долей этого графа, дополненных нулями. В данной работе мы даем описание двудольно-пороговых графов, составляющих семейство BTG↑(α,β), всех двудольно-пороговых графов, которые можно получить из графов семейства BG(α,β) с помощью двудольных повышающих вращений ребер. Также находим наименьшую длину последовательностей двудольных повышающих вращений ребер, переводящих графы из BG(α,β) в графы из BTG↑(α,β), даем алгоритм, который находит двудольно-пороговый граф, принадлежащий семейству BG(α,β), и получаем описание процедуры, которая позволяет из одного графа семейства BG(α,β) получить все графы этого семейства.

UR - https://www.elibrary.ru/item.asp?id=50358603

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85159043008

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=001027106500002

U2 - 10.21538/0134-4889-2023-29-1-24-35

DO - 10.21538/0134-4889-2023-29-1-24-35

M3 - Статья

VL - 29

SP - 24

EP - 35

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 1

ER -