Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mce.biophys.msu.ru/archive/doc21754/doc.pdf Дата изменения: Fri May 16 00:38:00 2008 Дата индексирования: Mon Oct 1 21:43:15 2012 Кодировка: Windows-1251

О ЛОКАЛЬНО-СБАЛАНСИРОВАННЫХ 2-РАЗБИЕНИЯХ НЕКОТОРЫХ ДВУДОЛЬНЫХ ГРАФОВ Баликян С.В. В работе получено необходимое и достаточное условие существования такого разбиения множества вершин двудольного графа G, в котором любые два простых цикла имеют не более одной общей вершины, на два непересекающихся подмножества V1 и V2 , при котором для любой вершины v V (G) выполняется неравенство ||(v) V1 | - |(v) V2 || 1, где (v) есть множество вершин, смежных вершине v. В работе рассматриваются неориентированные графы без кратных ребер и петель. Множество вершин графа G обозначается через V (G), множество ребер через E (G). Степень вершины v V (G) в графе G обозначается через dG (v). Для вершины v V (G) определим множество () { V (G)/(, ) E (G)}. 2-разбиением графа G называется функция f : V (G) {0, 1}. 2-разбиение f графа G называется локально-сбалансированным, если для любой вершины v V (G) ||{ ()/ f () = 1}| - |{ ()/ f () = 0}|| 1. Некоторые исследования задач о существовании локально-сбалансированных 2-разбиений графов проведены в [1, 2, 3]. Для любой функции g : Xg {0, 1} и любого множества X Xg положим: P(X , g) |{ X /g() = 1}| - |{ X /g() = 0}|. Множество всех простых циклов графа G обозначим через T (G). Будем полагать, по определению, что в простом цикле повторяющихся ребер нет. Множество вершин простого цикла C графа G обозначим через VG (C). Положим:
c VG (S) CS c Положим L(G) = V (G)\VG (T (G)). Для u V (G) положим LG (u) (u) L(G). Через V2 (G) обозначим подмножество вершин графа G, принадлежащих хотя бы двум простым циклам графа G. Для x V (G) через CG (x) обозначим множество всех простых циклов графа G, которые проходят через вершину x. Пусть G произвольный граф, а V0 V (G) некоторое подмножество его вершин. Определим граф < V0 >G следующим образом:

VG (C), где S есть произвольное подмножество множества T (G).

V (< V0 >G ) V0 ,

E (< V0 >G ) {(v1 , v2 ) E (G)/v1 V0 , v2 V0 }.


Пусть A множество графов, в которых любые два простых цикла имеют не более одной общей вершины. Целью работы является установление необходимого и достаточного условия существования локально-сбалансированного 2-разбиения для графов класса A. Не определяемые понятия можно найти в [4]. Различные циклы C1 T (G) и C2 T (G) назовем смежными циклами в графе G, / если VG (C1 ) VG (C2 ) = 0. Последовательность (C1 , C2 , . . . , C p ) различных простых циклов графа G, где p 2, назовем гирляндой в графе G, если для j, 1 j p - 1, циклы C j и C j+1 являются смежными циклами в G. Гирлянду (C1 , C2 , . . . , C p ) графа G назовем простой гирляндой в графе G, если для любых i и j, удовлетворяющих неравенствам 1 i < j p, j - i 2, циклы Ci и C j не смежны. Гирлянду (C1 , C2 , . . . , C p ) графа G, где p 3, назовем ожерельем в графе G, если циклы C1 и C p смежны. Ожерелье (C1 , C2 , . . . , C p ) графа G назовем простым ожерельем в графе G, если выполнено одно из следующих двух условий: / 1. p = 3 и VG (C1 ) VG (C2 ) VG (C3 ) = 0; 2. p 4 и выполнены условия (a) последовательность (C1 , C2 , . . . , C
p-1

) является простой гирляндой графа G,
p-1

(b) C p смежен и с циклом C1 , и с циклом C (c) для j, 2 j p - 2, C p не смежен с C j . Легко видеть, что имеет место

,

Теорема 1 Если G A, то в G не существует простого ожерелья. Подмножество Q T (G) простых циклов графа G назовем циклично-связанным, если для любых C Q и C Q существует гирлянда (C1 , C2 , . . . , C p ) в графе G, такая, что C1 совпадает с C , C p совпадает с C , а при любых C Q и C Q / не существует гирлянды (C1 , C2 , . . . , C p ) в графе G, такой, что C1 совпадает с C , C p совпадает с C . Граф G назовем циклически-связанным, если множество T (G) является циклично-связанным. Граф G назовем абсолютно циклически-связанным, если он является циклически-связанным и для любого ребра (x1 , x2 ) E (G) по меньшей мере одна из вершин x1 и x2 принадлежит некоторому циклу. Легко видеть, что для любого графа G множество T (G) можно представить в виде
t

T (G) =
i=1

Qi , где при 1 i < j t G

j / Qi QG = 0, G


так, что для i, 1 i t , Qi является циклично-связанным подмножеством множеG ства T (G); положим QG {Q1 , Q2 , . . . , QtG }. G G Ясно, что по любому графу G множество QG определяется однозначно. 1 2 t Рассмотрим множество подграфов {WG , WG , . . . , WG } графа G, таких, что для i, 1 i t,
i c c WG =< VG (Qi ) { V (G)/dG () = 1 и VG (Qi ) такое, что (, ) E (G)} >G . G G

Положим DG < V (G)\(

t i=1 VG

i (WG )) >G .

Ясно, что DG является лесом. Пусть {D1 , . . . , DG G } есть множество компонент G связности леса DG , где через N (DG ) обозначается количество компонент связности леса DG . N (D ) 1 t Положим St ruct (G) {D1 , . . . , DG G } {WG , . . . , WG }. G / Пусть G1 и G2 связные графы, для которых V (G1 ) V (G2 ) = 0, a e1 = (x1 , w1 ) и e2 = (x2 , w2 ) их висячие ребра, соответственно, причем dG1 (w1 ) = dG2 (w2 ) = 1. Определим граф G1 + (e1 = e2 ) + G2 , который в дальнейшем будем называть графом, полученным из графов G1 и G2 операцией склейки ребер e1 и e2 , следующим образом: V (G1 + (e1 = e2 ) + G2 ) (V (G1 )\{w1 }) (V (G2 )\{w2 }), E (G1 + (e1 = e2 ) + G2 ) (E (G1 )\{e1 }) (E (G2 )\{e2 }) {(x1 , x2 )}. Теорема 2 Для связного графа G существует множество Const r(G) {G1 , . . . , Gk } таких подграфов графа G, что: 1. граф G получается из графов множества Const r(G) последовательными операциями, каждая из которых является операцией склейки ребер; 2. для i, 1 i k, Gi является деревом или абсолютно циклически-связанным графом. Доказательство проведем индукцией по |St ruct (G)|. Если |St ruct (G)| = 1, то возьмем Const r(G) {G}, и доказывать нечего. Пусть теперь |St ruct (G)| > 1, и предположим, что для любого связного графа G с |St ruct (G )| = |St ruct (G)| - 1 существует множество Const r(G ) таких подграфов графа G , что выполняются условия 1 и 2. Покажем, что и для графа G существует множество Const r(G) таких его подграфов, что выполняются условия 1 и 2. Из связности G и из определения St ruct (G) следует, что существует граф G0 St ruct (G), такой, что существует единственное ребро e0 = (v1 , v2 ) V (G), удовлетво00 ряющее условиям v1 V (G0 ) и v2 V (G)\V (G0 ). 0 0 Рассмотрим граф G0 < (V (G)\V (G0 )) {v1 } >G . 0 Так как |St ruct (G0 )| = |St ruct (G)| - 1, то, по предположению индукции, для графа G0 существует множество Const r(G0 ) его подграфов, удовлетворяющих условиям 1 и 2. С другой стороны, граф G получается из графов G0 и G0 < V (G0 ) {v2 } >G 0

N (D )


операцией склейки ребер. Таким образом, множество Const r(G) Const r(G0 ) {G0 } удовлетворяет условию 1. Из определения St ruct (G) вытекает, что граф G0 и, следовательно, граф G0 являются абсолютно циклически-связанными графами или деревьями. Теорема доказана. Легко доказуема / Теорема 3 Пусть G1 и G2 связные графы, для которых V (G1 ) V (G2 ) = 0, e1 и e2 их висячие ребра, соответственно, и по меньшей мере один из графов G1 и G2 является двудольным. Чтобы для графа G1 + (e1 = e2 ) + G2 существовало локально-сбалансированное 2-разбиение, необходимо и достаточно, чтобы для обоих графов G1 и G2 существовали локально-сбалансированные 2-разбиения. Для G A цикловой расцветкой графа G назовем функцию F : V2 (G) Ч T (G) {-1, 0, 1, 2}, удовлетворяющую условию: для (x, C) V2 (G) Ч T (G) F (x, C) 0 тогда и только тогда, когда C CG (x). Пусть C простой цикл графа G A, некоторое направление обхода цикла C, и F произвольная цикловая расцветка графа G. (F, , C)-костью длины k(k 2) в графе G назовем последовательность (vi1 , . . . , vik ) вершин цикла C, такую, что выполняются условия: 1. среди вершин vi1 , vi2 , . . . , vik повторяющихся вершин нет, за исключением единственного возможного случая повторения, когда vi1 = vik . 2. для j, 1 j k - 1, существует вершина u j, j+1 цикла C (которую назовем промежуточной для vi j и vi j+1 ), которая при обходе цикла C по направлению следует непосредственно после vi j , и непосредственно после которой следует vi j+1 , причем вершина u j, j+1 удовлетворяет одному из следующих двух условий: (a) dG (u (b) u
j, j+1

) = 2,
j, j+1

j, j+1

V2 (G) и 0 F (u

, C ) 1.

(F, , C)-кость (vi1 , vi2 , . . . , vik ) в графе G назовем циклической, если vi1 = vik . (F, , C)-кость графа G назовем монополярной (гетерополярной), если число ее промежуточных вершин x, удовлетворяющих условию ?dG (x) = 2 или x V2 (G) и F (x, C) = 1?, является четным (нечетным). Множеством вершин (F, , C)-кости = (vi1 , vi2 , . . . , vik ) графа G назовем множеb ство {vi1 , vi2 , . . . , vik } и обозначим его через VG (). b Скажем, что (F, , C)-кость графа G проходит через вершину , если VG (). Для данной вершины VG (C) через M B(F, C, ) (сокращение от Maximum Bones) обозначим множество всех (F, , C)-костей графа G, проходящих через вершину и имеющих максимальную длину. Пусть G A является циклически-связанным графом. Определим функцию FG : V2 (G) Ч T (G) {-1, 0, 1, 2}. / Не ограничивая общность дальнейших рассуждений, можем считать, что V2 (G) = 0.


Алгоритм построения функции FG . Шаг 1. Для любого (x, C) V2 (G) Ч T (G), где C CG (x), положим FG (x, C) -1. / / Шаг 2. Положим C[0] = 0, t = 1. Шаг 3. Пусть цикл Ct графа G удовлетворяет условиям
c Ct T (G)\C[t - 1] и |VG (Ct ) VG ((T (G)\C[t - 1])\Ct )| = 1.

Существование такого цикла Ct вытекает из неравенства |T (G)\C[t - 1]| 2, теоремы 1 и из того, что G является циклически-связанным графом класса A. Обозначим через ut вершину цикла Ct , удовлетворяющую условию
c VG (Ct ) VG ((T (G)\C[t - 1])\Ct ) = {ut }.

Пусть VG (Ct ) (ut ) = {v1t , v2t }. / Замечание 1 Если (VG (Ct )\{ut }) V2 (G) = 0, то на множестве ((VG (Ct )\{ut }) V2 (G)) Ч T (G) функция FG уже определена. Пусть t такое направление обхода цикла Ct , при котором вершина ut не следует непосредственно после вершины v1t . Положим 0 (1), если существует монополярная (гетерополярная) (FG , t , Ct )-кость (vi1 , . . . , vik ), такая, что vi1 = v1t , vi2 = v2t . FG (ut , Ct ) если не существует (FG , t , Ct )-кости (vi1 , . . . , vik ), такой, 2, что vi1 = v1t , vi2 = v2t . Положим C[t ] C[t - 1] {Ct }. Если |CG (ut )\C[t ]| = 1, то обозначим через Ct цикл, удовлетворяющий условию CG (ut )\C[t ] = {Ct }, и положим / / если {C (CG (ut )\{Ct })/FG (ut , C) = 2} = 0 или LG (ut ) = 0 2, / / 0 (1), если {C (CG (ut )\{Ct })/FG (ut , C) = 2} = 0, LG (ut ) = 0 и FG (ut , Ct ) число |{C (CG (ut )\{Ct })/FG (ut , C) = 0}| нечетно (четно). Шаг 4. Если |T (G)\C[t ]| = 1, то положим t = t + 1 и перейдем к Шагу 3, в противном случае положим C|T (G)| C , где {C } = T (G)\C[t ], и Алгоритм завершен. Замечание 2 Легко видеть, что функция FG , построенная при применении описанного алгоритма, является цикловой расцветкой графа G. Лемма 1 Пусть G A является циклически-связанным графом, а f локально-сбалансированное 2-разбиение графа G. Тогда, если последовательность (vi1 , vi2 , . . . , vin ) является (FG , , C)-костью в графе G при некотором направлении обхода цикла C, то имеет место равенство f (vi1 ) = f (vin ), если (FG , , C)-кость монополярна; 1 - f (vin ), если (FG , , C)-кость гетерополярна.


Доказательство проведем индукцией по параметру t , используемому в алгоритме построения функции FG . Будем считать, что вершины и подграфы графа G, описываемые с применением значений параметра t в индексе обозначения, совпадают с соответствующими объектами, определяемыми при работе алгоритма. Докажем утверждение леммы для случая, когда C = C1 . c Ясно, что |VG (C1 ) VG (T (G))| = 1. Отсюда следует, что VG (C1 ) V2 (G) = {u1 }. Случай 1. u1 не является промежуточной вершиной (FG , , C1 )-кости . В этом случае для любой промежуточной вершины x (FG , , C1 )-кости dG (x) = 2, откуда и следует нужное равенство. Случай 2. u1 является промежуточной вершиной (FG , , C1 )-кости . В этом случае ясно, что 0 FG (u1 , C1 ) 1, причем из алгоритма построения FG следует, что FG (u1 , C1 ) = 0 (FG (u1 , C1 ) = 1) тогда и только тогда, когда существует монополярная (гетерополярная) (FG , 1 , C1 )-кость 1 (v11 , z j1 , . . . , z jm , v21 ) в графе G, для которой вершина u1 не является промежуточной. Применяя рассуждение, используемое при рассмотрении случая 1, к (FG , 1 , C1 )-кости 1 , можно показать, что f (v21 ), если (FG , 1 , C1 )-кость 1 монополярна; 1 - f (v21 ), если (FG , 1 , C1 )-кость 1 гетерополярна, из чего вытекает, что f (v11 ) = f (v11 ) = f (v21 ), если FG (u1 , C1 ) = 0; 1 - f (v21 ), если FG (u1 , C1 ) = 1.

Отсюда, из определения монополярной (гетерополярной) кости и из рассуждения, проведенного для случая 1, вытекает доказываемое равенство. Допустим, что утвеждение леммы верно для любого цикла Ct , при 1 t k - 1, где 1 < k |T (G)| - 1. Докажем утверждение леммы для случая, когда C = Ck . Случай 1ind . uk не является промежуточной вершиной (FG , , Ck )-кости . Рассмотрим произвольную вершину u j, j+1 , которая является промежуточной вершиной для вершин vi j и vi j+1 , где 1 j n - 1 и u j, j+1 V2 (G) (отметим, что если такой вершины u j, j+1 не существует, то справедливость утверждения леммы для (FG , , Ck )-кости устанавливается так же, как и при t = 1). Заметим, что справедливость утверждения леммы для (FG , , Ck )-кости будет доказана, если мы докажем равенство f (vi j ) = f (vi j+1 ), если FG (u 1 - f (vi j+1 ), если FG (u
j, j+1 j, j+1

, Ck ) = 0; , Ck ) = 1.

Из алгоритма построения функции FG вытекает, что для C CG (u j, j+1 ) существует некоторое значение s, 1 s k - 1, параметра t , используемого в алгоритме, такое, что u j, j+1 = us и C совпадает с Cs , причем 0 FG (u j, j+1 , Cs ) 1. Выберем C CG (u j, j+1 ). В силу сказанного выше, существует s, 1 s k - 1, такое, что u j, j+1 = us и C совпадает с Cs . Покажем, что f (v1s ) = f (v2s ), если FG (u 1 - f (v2s ), если FG (u
j, j+1 j, j+1

, Cs ) = 0; , Cs ) = 1.


Случай 1ind a). FG (u j, j+1 , Cs ) = 0 Ясно, что FG (us , Cs ) = 0. Следовательно, существует монополярная (FG , s , Cs )кость s = (v1s , li1 , . . . , lim , v2s ) в графе G. По предположению индукции, имеет место равенство f (v1s ) = f (v2s ). Случай 1ind b). FG (u j, j+1 , Cs ) = 1 Ясно, что FG (us , Cs ) = 1. Следовательно, существует гетерополярная (FG , s , Cs )кость s = (v1s , li1 , . . . , lim , v2s ) в графе G. По предположению индукции, имеет место равенство f (v1s ) = 1 - f (v2s ). Таким образом, искомая связь между f (v1s ) и f (v2s ) установлена. Отсюда и из алгоритма построения функции FG вытекает искомая связь между f (vi j ) и f (vi j+1 ). Случай 2ind . uk является промежуточной вершиной (FG , , Ck )-кости . В этом случае ясно, что 0 FG (uk , Ck ) 1, причем из алгоритма построения FG следует, что FG (uk , Ck ) = 0 (FG (uk , Ck ) = 1) тогда и только тогда, когда существует монополярная (гетерополярная) (FG , k , Ck )-кость k (v1k , z j1 , . . . , z jq , v2k ) в графе G, для которой вершина uk не является промежуточной. Применяя рассуждение, используемое при рассмотрении случая 1ind , к (FG , k , Ck )-кости k , можно показать, что f (v1k ) = f (v2k ), если (FG , k , Ck )-кость k монополярна; 1 - f (v2k ), если (FG , k , Ck )-кость k гетерополярна, f (v2k ), если FG (uk , Ck ) = 0; 1 - f (v2k ), если FG (uk , Ck ) = 1.

из чего вытекает, что f (v1k ) =

Отсюда, из определения монополярной (гетерополярной) кости и из рассуждения, проведенного для случая 1ind , вытекает утверждение леммы для (FG , , Ck )-кости графа G. Допустим, что утверждение леммы верно для любого цикла Ct , при 1 t |T (G)| - 1. Докажем утверждение леммы для случая, когда C = C|T (G)| . Легко видеть, что в этом случае справедливость утверждения леммы устанавливается так же, как в случае 1ind . Лемма доказана. Следствие 1 Пусть G A является циклически-связанным графом, а f локально-сбалансированное 2-разбиение графа G. Тогда, если последовательность (vi1 , . . . , vin ) является (FG , , C)-костью в графе G при некотором направлении обхода цикла C, то значение f (vi j ) для j, 1 j n, однозначно определяется значением f (vik ) при k, 1 k n. Теорема 4 Пусть G A является абсолютно циклически-связанным, двудольным графом. Для того, чтобы существовало локально-сбалансированное 2-разбиение графа G, необходимо и достаточно, чтобы для C T (G) и любого направления обхода цикла C не существовало гетерополярной циклической (FG , , C)-кости в графе G.


Необходимость. Доказательство проведем от противного. Пусть C0 T (G) и последовательность 0 (vi1 , vi2 , . . . , vin ) вершин цикла C0 является гетерополярной циклической (FG , 0 , C0 )-костью в графе G при некотором направлении 0 обхода цикла C0 , и пусть f является локально-сбалансированным 2-разбиением графа G. Из леммы 1 следует, что f (vi1 ) = 1 - f (vin ), но это невозможно, так как 0 является циклической (FG , 0 , C0 )-костью в графе G. Достаточность. Предположим, что для любого C T (G) и любого направления обхода цикла C не существует гетерополярной циклической (FG , , C)-кости в графе G. Сначала дадим несколько определений. Для любых u V2 (G), C T (G) и i {0, 1, 2} положим: CG (u, i, C) {C CG (u)/FG (u, C ) = i}\{C}. Пусть u0 V2 (G) произвольная вершина, а C0 T (G) произвольный цикл. Осуществим произвольным образом разбиение множества CG (u0 , 0, C0 ) на подмножества C01 (u0 , C0 ) и C02 (u0 , C0 ) так, что / CG (u0 , 0, C0 ) = C01 (u0 , C0 ) C02 (u0 , C0 ), C01 (u0 , C0 ) C02 (u0 , C0 ) = 0, |C01 (u0 , C0 )| =
|CG (u0 ,0,C0 )| 2

, |C02 (u0 , C0 )| =

|CG (u0 ,0,C0 )| 2

.

c Для j {1, 2} положим: V0 j (u0 , C0 ) (u0 ) VG (C0 j (u0 , C0 )). Положим V0 (u0 , C0 ) V01 (u0 , C0 ) V02 (u0 , C0 ). c Положим: V1 (u0 , C0 ) (u0 ) VG (CG (u0 , 1, C0 )).

Замечание 3 Для C CG (u0 , 1, C0 ) имеет место равенство |V1 (u0 , C0 ) VG (C)| = 2. Осуществим произвольным образом разбиение множества V1 (u0 , C0 ) на подмножества V11 (u0 , C0 ) и V12 (u0 , C0 ) так, что / V1 (u0 , C0 ) = V11 (u0 , C0 ) V12 (u0 , C0 ), V11 (u0 , C0 ) V12 (u0 , C0 ) = 0, и для C CG (u0 , 1, C0 ) |VG (C) V11 (u0 , C0 )| = 1, |VG (C) V12 (u0 , C0 )| = 1. c Положим V2 (u0 , C0 ) ((u0 ) VG (CG (u0 , 2, C0 ))) LG (u0 ). Для любого натурального числа m0 осуществим произвольным образом разбиение множества V2 (u0 , C0 ) на подмножества V21 (u0 , C0 , m0 ), V22 (u0 , C0 , m0 ) и V23 (u0 , C0 , m0 ) так, что V2 (u0 , C0 ) = V21 (u0 , C0 , m0 ) V22 (u0 , C0 , m0 ) V23 (u0 , C0 , m0 ), / / V21 (u0 , C0 , m0 ) V22 (u0 , C0 , m0 ) = 0, V22 (u0 , C0 , m0 ) V23 (u0 , C0 , m0 ) = 0, / V21 (u0 , C0 , m0 ) V23 (u0 , C0 , m0 ) = 0, и имеет место одно из нижеуказанных условий: / / 1. |V2 (u0 , C0 )| m0 , V21 (u0 , C0 , m0 ) = V2 (u0 , C0 ), V22 (u0 , C0 , m0 ) = 0, V23 (u0 , C0 , m0 ) = 0.


2. |V2 (u0 , C0 )| > m0 , |V21 (u0 , C0 , m0 )| = m0 , |V22 (u0 , C0 , m0 )| = |V23 (u0 , C0 , m0 )| =
|V2 (u0 ,C0 )|-m 2
0

|V2 (u0 ,C0 )|-m 2

0

,

.

/ Заметим, что (u0 )\(V0 (u0 , C0 ) V1 (u0 , C0 ) V2 (u0 , C0 )) = 0 и (u0 )\(V0 (u0 , C0 ) V1 (u0 , C0 ) V2 (u0 , C0 )) VG (C0 ). Пусть 0 V (G) произвольная вершина графа G. Для любого натурального числа m0 осуществим произвольным образом разбиение множества LG (0 ) на подмножества L1 (0 , m0 ), L2 (0 , m0 ) и L3 (0 , m0 ) так, что / LG (0 ) = L1 (0 , m0 ) L2 (0 , m0 ) L3 (0 , m0 ), L1 (0 , m0 ) L2 (0 , m0 ) = 0, / / L2 (0 , m0 ) L3 (0 , m0 ) = 0, L1 (0 , m0 ) L3 (0 , m0 ) = 0, и имеет место одно из нижеуказанных условий: / / 1. |LG (0 )| m0 , L1 (0 , m0 ) = LG (0 ), L2 (0 , m0 ) = 0, L3 (0 , m0 ) = 0. 2. |LG (0 )| > m0 , |L1 (0 , m0 )| = m0 , |L2 (0 , m0 )| = |L3 (0 , m0 )| =
|LG (0 )|-m0 2 |LG (0 )|-m 2
0

,

.

Дадим алгоритм построения функции f : V (G) {0, 1}. Будем считать, что вершины и подграфы графа G, описываемые с применением значений параметра t в индексе обозначения, используемого в нижеуказанном алгоритме построения 2-разбиения f , совпадают с соответствующими объектами, определяемыми при работе алгоритма построения функции FG . Алгоритм Шаг 1. Положим t = |T (G)|. Шаг 2. Если значение функции f на всех вершинах множества VG (Ct ) определено, то перейдем к шагу 3. Пусть вершина v0 VG (Ct ) такова, что значение функции f на нем не определенo. Положим f (v0 ) 0. / Если M B(FG , Ct , v0 ) = 0, то определим значение функции f на вершинах множеb ства VG ( )\{v0 }, где произвольный элемент из M B(FG , Ct , v0 ), на основе значения f (v0 ) по схеме, вытекающей из следствия 1. Перейдем к шагу 2. Шаг 3. Если t = 1, то перейдем к шагу 5.
c Замечание 4 Для u V2 (G) VG (Ct ) VG ({Ct -1 , . . . , C1 }) значение функции f на множестве (u)\(V0 (u, Ct ) V1 (u, Ct ) V2 (u, Ct )) уже определено и еще не определено на множестве V0 (u, Ct ) V1 (u, Ct ) V2 (u, Ct ). c Для каждой вершины u0 V2 (G) VG (Ct ) VG ({Ct -1 , . . . , C1 }) дадим ряд определений. Пусть 0 (u0 )\(V0 (u0 , Ct ) V1 (u0 , Ct ) V2 (u0 , Ct )).


Для Для Для Для





V01 V02 V11 V12

(u (u (u (u

0 0 0 0

, , , ,

Ct Ct Ct Ct

) ) ) )

положим положим положим положим

f f f f

( ( ( (

) ) ) )



1 - f (0 ). f (0 ). 0. 1.

Замечание 5 Для всех вершин множества (u0 )\V2 (u0 , Ct ) значение функции f уже определено. Положим p(u0 ) P((u0 )\V2 (u0 , Ct ), f ). Для V21 (u0 , Ct , | p(u0 )|) положим: f () 0, если p(u0 ) > 0; 1, если p(u0 ) < 0.

Для V22 (u0 , Ct , | p(u0 )|) положим f () 0. Для V23 (u0 , Ct , | p(u0 )|) положим f () 1. Шаг 4. Положим t = t - 1. / Если M B(FG , Ct , ut ) = 0, то определим значение функции f на вершинах множеb ства VG ( )\{ut }, где произвольный элемент из M B(FG , Ct , ut ), на основе значения f (ut ) по схеме, вытекающей из следствия 1. / Если M B(FG , Ct , v1t ) = 0, то определим значение функции f на вершинах мноb ( ))\{v , v }, где жества VG произвольный элемент из M B(FG , Ct , v1t ), на основе 1t 2t значения f (v1t ) по схеме, вытекающей из следствия 1. / Замечание 6 Если M B(FG , Ct , v1t ) M B(FG , Ct , v2t ) = 0, то значение функции f на вершине v2t , определяемое на основе значения f (v1t ) по схеме, вытекающей из следствия 1, совпадает с уже определенным значением f (v2t ). / / Если M B(FG , Ct , v2t ) = 0 и M B(FG , Ct , v1t ) M B(FG , Ct , v2t ) = 0, то определим значеb ( )\{v }, где ние функции f на вершинах множества VG произвольный элемент 2t из M B(FG , Ct , v2t ), на основе значения f (v2t ) по схеме, вытекающей из следствия 1. Перейдем к шагу 2. Шаг 5. Замечание 7 Для всех вершин множества V (G)\L(G) значение функции f уже определено. Для каждой вершины 0 V (G)\(L(G) V2 (G)) дадим следующие определения. Положим q(0 ) P((0 )\LG (0 ), f ). Для L1 (0 , |q(0 )|) положим: f () 0, если q(0 ) > 0; 1, если q(0 ) < 0.

Для L2 (0 , |q(0 )|) положим f () 0. Для L3 (0 , |q(0 )|) положим f () 1. Алгоритм завершен.


Докажем, что полученное 2-разбиение f графа G является локально-сбалансированным. Выберем произвольную вершину u V (G). Случай 1. u L(G). В этом случае dG (u) = 1 и, следовательно, |P((u), f )| = 1 1. Случай 2. u V (G)\(L(G) V2 (G)). Случай 2а). |LG (u)| > q(u). Легко видеть, что в этом случае из определения функции f следует, что P((u)\LG (u), f ) + P(L1 (u, |q(u)|), f ) = 0 и |P(L2 (u, |q(u)|), f ) + P(L3 (u, |q(u)|), f )| 1. Следовательно, |P((u), f )| = |P((u)\LG (u), f ) + P(LG (u), f )| = |P((u)\LG (u), f )+ + P(L1 (u, |q(u)|), f ) + P(L2 (u, |q(u)|), f ) + P(L3 (u, |q(u)|), f )| 1 Случай 2б). |LG (u)| q(u). Легко видеть, что в этом случае из определения функции f следует, что |P((u), f )| = |P((u)\LG (u), f ) + P(LG (u), f )| = |P((u)\LG (u), f )| - |LG (u)|. Заметим, что |(u)\LG (u)| = 2, следовательно, |P((u)\LG (u), f )| 2. Из последнего неравенства следует, что если |LG (u)| > 0, то |P((u), f )| 1. Предположим, что |LG (u)| = 0, следовательно, dG (u) = 2. В этом случае из определения кости следует, что u является промежуточной вершиной в некоторой кости. С другой стороны, согласно схеме, вытекающей из следствия 1, на вершинах кости, имеющих в качестве промежуточной вершины вершину степени 2, любое локально-сбалансированное 2-разбиение должно принимать различные значения. Следовательно, из определения функции f получаем, что |P((u), f )| = 0 1. Случай 3. u V2 (G). Пусть C CG (u) есть цикл, имеющий максимальный номер в нумерации циклов, данном в алгоритме построения функции FG . Случай 3а). |V2 (u, C)| > p(u). Легко видеть, что в этом случае из определения функции f следует, что P((u)\V2 (u, C), f ) + P(V21 (u, C, | p(u)|), f ) = 0 и |P(V22 (u, C, | p(u)|), f ) + P(V23 (u, C, | p(u)|), f )| 1. Следовательно, |P((u), f )| = |P((u)\V2 (u, C), f ) + P(V2 (u, C), f )| = = |P((u)\V2 (u, C), f ) + P(V21 (u, C, | p(u)|), f ) + P(V22 (u, C, | p(u)|), f )+ + P(V23 (u, C, | p(u)|), f )| 1


Случай 3б). |V2 (u, C)| p(u). Легко видеть, что в этом случае из определения функции f следует, что |P((u), f )| = |P((u)\V2 (u, C), f ) + P(V2 (u, C), f )| = |P((u)\V2 (u, C), f )| - |V2 (u, C)|. С другой стороны, из определения функции f следует, что |P((u)\(V0 (u, C) V1 (u, C) V2 (u, C)), f ) + P(V0 (u, C), f )| 2, P(V1 (u, C), f ) = 0. Следовательно, |P((u)\V2 (u, C), f )| = |P((u)\(V0 (u, C) V1 (u, C) V2 (u, C)), f ) + P(V0 (u, C), f )+ + P(V1 (u, C), f )| = |P((u)\(V0 (u, C) V1 (u, C) V2 (u, C)), f ) + P(V0 (u, C), f )| 2 Из последнего неравенства следует, что если |V2 (u, C)| > 0, то |P((u), f )| 1, а если |V2 (u, C)| = 0, то из алгоритма построения функции FG следует, что |P(V0 (u, C), f ) + P((u)\(V0 (u, C) V1 (u, C) V2 (u, C)), f )| = 0, следовательно, |P((u), f )| = 0 1. Теорема доказана. Легко видеть, что имеет место Теорема 5 Для любого дерева существует локально-сбалансированное 2-разбиение. Из теорем 2, 3, 4, 5 вытекает Теорема 6 Пусть G A является двудольным связным графом. Для того, чтобы существовало локально-сбалансированное 2-разбиение графа G, необходимо и достаточно, чтобы для G Const r(G), не являющегося деревом, для C T (G ) и любого направления обхода цикла C не существовало гетерополярной циклической (FG , , C)-кости в графе G .

СПИСОК ЛИТЕРАТУРЫ 1. Баликян С.В., Камалян Р.Р. Об NP-полноте задачи существования локально-сбалансированного 2-разбиения двудольных графов G с (G) = 3. // Доклады НАН РА. 2005. T. 105, ћ 1. С. 21 27. 2. Баликян С.В., Камалян Р.Р. Об NP-полноте задачи существования локально-сбалансированного 2-разбиения двудольных графов G с (G) = 4 при расширенном определении окрестности вершины. // Доклады НАН РА. 2006. T. 106, ћ 3. С. 218 226. 3. Berge C. Graphs and Hypergraphs. North-Holland, 1973. 528 p. 4. Харари Ф. Теория графов. Москва: Мир, 1973. 302 с.


ON LOCALLY-BALANCED 2-PARTITIONS OF SOME BIPARTITE GRAPHS Balikyan S.V. Necessary and sufficient condition is obtained for the problem of such partitioning of the set of vertices of a bipartite graph G, in which arbitrary two simple cycles have at most one common vertex, into two disjoint subsets V1 and V2 , which satisfies the condition ||(v) V1 | - |(v) V2 || 1 for any vertex v of G, where (v) is the set of all vertices of G adjacent to v.