УДК 519.1
Об NP-полноте задачи существования
локально-сбалансированного
2-разбиения двудольных графов
G с
D(G) = 3
(Представлено академиком Ю.Г. Шукуряном 17/VI 2004)
В работе рассматриваются неориентированные
графы без кратных ребер и петель. Множество вершин графа G обозначается через
V(G), множество ребер - через E(G). Наибольшая из степеней вершин графа G
обозначается через D(G).
Не
определяемые понятия можно найти в [1-5]. Граф G(I) определен. Ясно, что D(G(I)) = 3. С помощью лемм 1.1 и 1.2 работы [7] нетрудно
показать, что G(I) является двудольным графом. Убедимся,
что если для некоторого j0, 1 Ј
j0 Ј r, f(tj0,8) = 1, то
существуют l0 О {1,3} и i0 О t(Dj0)
такие, что ui0,j0,l0 О Vj03 и
f(ui0,j0,l0) = 1. Действительно, из
f(tj0,8) = 1 следует f(tj0,6) = 0,
откуда: либо f(tj0,4) = 0 и существует l0 О {1,3} такое, что umaxt(Dj0),j0,l0
О l(tj0,5)\{tj0,4, tj0,6}
и f(umaxt(Dj0),j0,l0) = 1,
либо f(tj0,4) = 1, откуда f(tj0,2) = 0
и, следовательно, существуют l0 О {1,3} и
i0 О t(Dj0), i0 № maxt(Dj0),
для которых ui0,j0,l0 О l(tj0,1)\{tj0,2}
и f(ui0,j0,l0) = 1. Следовательно,
существуют функции g1:{1,ј,r}®{1,3} и g2:{1, ј, r}®{1, ј, n} такие, что для j = 1,ј,r g2(j) О t(Dj) и выполнены условия
ug2(j),j,g1(j) О
Vj3 и
f(ug2(j),j,g1(j)) = 1. Определим набор m є (m1,m2,ј,mn) следующим образом.
Для i = 1,ј,n положим mi = f(ui,m(1,i),1). Покажем, что K(m1,m2,ј,mn) = 1. Убедимся, что
для любого j, 1 Ј j Ј r при
xi = mi, i = 1, ј, n, дизъюнкция Dj конъюнктивной нормальной формы
K(x1,x2,ј,xn)
принимает значение 1. Если Dj О
M1(g2(j),K), то g1(j) = 1 и mg2(j) = f(ug2(j), m(1,g2(j),1)) = f(ug2(j),j,1) = 1,
и утверждение очевидно. Если Dj О
M2(g2(j),K), то g1(j) = 3 и
f(ug2(j),j,3) = 1, откуда
f(ug2(j),j,1) = 0. Но
f(ug2(j),j,1) = f(ug2(j), m(1,g2(j),1)) = mg2(j), и утверждение доказано. Для j = 1,ј, r положим Fn
(tj,4) = 1 - Fn (tj,2). Ясно, что Fn (t1,6) = Fn (t2,6) = ј =
Fn (tr,6) = 0. Этап 2: Ереванский государственный
университет
1. Harary F. Graph Theory. Addison-Wesley. Reading. MA.
1969.
||{ w О l(v)/f(w) = 1}| - |{w О l(v)/f(w) = 0}|| Ј 1.
Для
j = 1, ј, r положим:
Vij =
м
п
н
п
о
Ж,
если
Dj П M(i,K)
{ui,j,1},
если
Dj О
M1(i,K)
{ui,j,1, ui,j,2, ui,j,3},
если
Dj О
M2(i,K)
Для
j = 1, ј, r положим:
Vj1 =
n
И
i=1 Vij
Для
j = 1, ј, r положим:
Vj2 = {
tj,1, tj,2, tj,3, tj,4, tj,5, tj,6, tj,7, tj,8}.
Положим
Zr = Ж.
Vj = Vj1ИVj2.
Если r > 1, то для j = 1, ј, r - 1 положим:
Для i = 1, ј, n при s(i) > 1 и k = 1,ј,s(i) - 1 положим:
Zj = { z1ў(j), z1ўў(j + 1),
z2(j,j + 1)}.
Для
i = 1, ј, n положим:
W(i,k) = {w1ў(i,m(k,i)),w1ўў(i,m(k + 1,i)),w2(i,m(k,i),m(k + 1,i))}.
Для
i = 1, ј, n положим:
Wi1 =
м
п
н
п
о
Ж,
если
s(i) = 1
s(i)-1
И
k=1 W(i,k),
если s(i)
> 1.
Для
i = 1, ј, n положим:
Wi2 =
м
п
н
п
о
Ж,
если
s(i) = 1
{w3,1(i)},
если
s(i) = 2
{w3,1(i), w3,2(i)},
если s(i)
> 2.
Положим:
Wi = Wi1ИWi2.
Для
i = 1, ј, n, j = 1,ј, r положим:
V(G(I)) =
ж
и r
И
j=1 (VjИZj)
ц
ш
И
ж
и n
И
i=1 Wi
ц
ш .
Для j = 1, ј, r положим:
Eij1 =
м
н
о
Ж,
если
Dj П
M2(i,K)
{(ui,j,1, ui,j,2), (ui,j,2, ui,j,3)},
если
Dj О
M2(i,K).
Для
i = 1, ј, n, j = 1, ј, r положим:
Ej1 =
n
И
i=1 Eij1.
Для j = 1, ј, r положим:
Eij2 =
м
п
п
п
н
п
п
п
о
Ж,
если
Dj П
M(i,K)
{(ui,j,1, tj,1)},
если
Dj О
M1(i,K) и i №
max
t(Dj)
{(ui,j,3, tj,1)},
если
Dj О
M2(i,K) и i №
max
t(Dj)
{(ui,j,1, tj,5)},
если
Dj О
M1(i,K) и i =
max
t(Dj)
{(ui,j,3, tj,5)},
если
Dj О
M2(i,K) и i =
max
t(Dj).
Для
j = 1, ј, r положим:
Ej2 =
n
И
i=1 Eij2.
Положим
Er4 = Ж.
Ej3 = {(tj,1, tj,2), (tj,2, tj,3), (tj,3, tj,4), (tj,4, tj,5), (tj,5, tj,6), (tj,6, tj,7), (tj,7, tj,8)}.
Если r > 1, то для j = 1, ј, r - 1 положим:
Для i = 1, ј, n при s(i) > 1 и k = 1,ј,s(i) - 1 положим:
Ej4 = {(tj,8, z1ў(j)), (z1ў(j), z2(j,j + 1)), (z2(j,j + 1),z1ўў(j + 1)), (z1ўў(j + 1),tj+1,8)
}.
Для
i = 1, ј, n положим:
Eik5 = {(ui,m(k,i),1, w1ў(i,m(k,i))), (w1ў(i,m(k,i)), w2(i,m(k,i), m(k + 1,i))),
(w2(i,m(k,i), m(k + 1,i)), w1ўў(i,m(k + 1,i))), (w1ўў(i,m(k + 1,i)), ui,m(k+1,i),1)}.
Для
i = 1, ј, n положим:
Ei5 =
м
п
н
п
о
Ж,
если
s(i) = 1
s(i)-1
И
k=1 Eik5,
если s(i)
> 1.
Положим:
Ei6 =
м
п
п
н
п
п
о
Ж,
если
s(i) = 1
{(w2(i,m(1,i), m(2,i)), w3,1(i))},
если
s(i) = 2
{(w2(i,m(1,i), m(2,i)), w3,1(i)),
(w2(i,m(s(i) - 1,i), m(s(i),i)), w3,2(i))},
если s(i)
> 2.
E(G(I)) =
ж
и r
И
j=1
ж
и
4
И
p=1 Ejp
ц
ш ц
ш
И
ж
и n
И
i=1 ( Ei5ИEi6)
ц
ш .
Для i = 1, ј, n и j = 1, ј, r определим множество Vij3 Н V(G(I)) следующим образом:
f(ui,m(1,i),1) = f(ui,m(2,i),1) = ј =
f(ui,m(s(i),i),1).
Для
j = 1, ј, r положим:
V3ij =
м
п
н
п
о
Ж,
если
Dj П
M(i,K)
{ui,j,1},
если
Dj О
M1(i,K)
{ui,j,3},
если
Dj О
M2(i,K).
Легко
видеть, что для j = 1, ј, r
Vj3 =
n
И
i=1 Vij3.
Vj3 = (l(tj,1)\{tj,2})
И
(l(tj,5)\{tj,4, tj,6}).
Для i = 1, ј, n и j = 1, ј, r при Dj
О M2(i,K) положим
Для j = 1, ј, r положим Fn (tj,2) = 1 -Fn (V).
Fn
(ui,j,3) = 1 - Fn
(ui,j,1).
Так как
K(v1,v2,ј,vn) = 1, то
для j = 1, ј, r,
Fn (V) = 1.
Для j = 1, ј, r положим Fn
(tj,6) = 1 -Fn (V)
Для
j = 1, ј, r положим Fn
(tj,8) = 1.
Для j = 1, ј, r - 1 положим Fn
(z2(j,j + 1)) = 0.
Для i = 1, ј, n
при s(i) > 1 и k = 1, ј, s(i) - 1 положим Fn
(w2(i,m(k,i), m(k + 1,i))) = 1 - vi.
Этап 1 завершен.
Для j = 1, ј, r - 1 положим Fn
(z1ў(j)) = 0, Fn (z1ўў(j + 1)) = 1.
Для j = 1, ј, r - 1 положим Fn (tj,7) = 1, Fn (tj,5) = 0, Fn (tj,3) = 1, Fn (tj,1) = 0.
Положим
Fn (tr,7) = 0, Fn (tr,5) = 1, Fn (tr,3) = 0, Fn (tr,1) = 1.
Для i = 1, ј, n и j = 1, ј, r при Dj
О M2(i,K) положим Fn (ui,j,2) = 1 - Fn
(tj,1).
Для i = 1, ј, n при
s(i) > 2 и k = 2, ј, s(i) - 1
положим Fn (w1ўў(i,m(k,i))) = 1, Fn (w1ў(i,m(k,i))) = 0.
Для i = 1, ј, n при s(i) > 1 положим:
Fn
(w1ў(i,m(1,i))) =
м
н
о
1 - Fn (tm(1,i),1),
если
Dm(1,i) О
M1(i,K)
1 - Fn (ui,m(1,i),2),
если
Dm(1,i) О
M2(i,K)
Для
i = 1, ј, n при s(i) > 2 положим Fn (w3,1(i)) = 0, Fn (w3,2(i)) = 1.
Fn
(w1ўў(i,m(s(i),i))) =
м
н
о
1 - Fn (tm(s(i),i),1),
если
Dm(s(i),i) О
M1(i,K)
1 - Fn (ui,m(s(i),i),2),
если
Dm(s(i),i) О
M2(i,K)
Для
i = 1, ј, n при s(i) = 2 положим
Fn (w3,1(i)) = 1 - max {Fn
(w1ў(i,m(1,i))), Fn (w1ўў(i,m(2,i)))}.
Этап 2 завершен. Алгоритм завершен.
Институт проблем информатики и
автоматизации НАН РА
2. Cook S.A. - Proc. 3rd Ann. ACM Symp. On Theory of Computing. Association for
Computing Machinery. New York. 1971.
P.151-158.
3. Garey M.R., Jonson
D.S. Computers and Intractability: A Guid to the Theory of
NP-completeness. San Francisco: W.H.Freman & Company. Publishers.
1979.
4. Papadimitriou C.H.,
Steiglitz K. Combinatorial optimization: Algorithms and
Complexity. PRENTICE-HALL. INC Englewood Cliffs. New Jersey.
1982.
5. Karp R.M. In: Complexity of Computer Computations. Eds. R.E. Miller and J.W.
Thatcher. Plenum Press. New York. 1972. P.
85-103.
6. Яблонский С. В.
Введение в дискретную математику. М. Наука. 1986.
384 с.
7. Мкртчян В. В.
О сложности задач построения в графе максимальных
паросочетаний специального типа. Диссертация на соискание степени магистра. ЕГУ.
Факультет информатики и прикладной математики. Кафедра мат. методов и
моделирования. Ереван. 2003. 20 с.