TY - JOUR

T1 - АЛГОРИТМ ПРИВЕДЕНИЯ ДВУДОЛЬНОГО ГРАФА К ДВУДОЛЬНО-ПОРОГОВОМУ ВИДУ

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

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

PY - 2022

Y1 - 2022

N2 - Тройка (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-вращений ребер.

AB - Тройка (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-вращений ребер.

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

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

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

U2 - 10.21538/0134-4889-2022-28-4-54-63

DO - 10.21538/0134-4889-2022-28-4-54-63

M3 - Статья

VL - 28

SP - 54

EP - 63

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

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

SN - 0134-4889

IS - 4

ER -