� 5 ���Dz��̲������² �������
���������
��'����� ���� Gr(V,E) � �������� ������ V=V(Gr) � �������� ����� E=E(Gr),
���������� ������������, ���� ���� ���� ��������� f: {1,2,...,n}�V ������� ���� ������, ��
d(f(1),f(2))=d(f(2),f(3))=...=d(f(n-1),f(n))=d(f(n),f(1))=1.
��� ����� ������������ f(1),f(2),�,f(n) ���������� ������������ ������. ������ �������������� ������������
������ - ���� � ���������� ������'������ ������� ���� ������ (���. [5, ����. 85], [12, ����. 72]).
��
�������� 4.1 ������� ������ ��������� ���������� �������� ����� Gr(V,E) ����� ������������ f: {1,2,...,n}�V� ���, ��
d(f(1),f(2))£3, d(f(2),f(3))£3, ..., d(f(n-1), f(n))£3, d(f(n), f(1))£3.
������������
������ f(1),f(2),�,f(n) ���������� ������ ���������� �����. � ��'���� � ��� ����������� ��������
��������� ��� ��������� � ��������.
��������� 1. ��������� f: {1,2,...,n}�V
������� ������ ���������� ��'������ ����� Gr(V,E) ������� ����������������
������ (��������� qh-������), ����
d(f(1),f(2)) £2, d(f(2),f(3)) £2, ..., d(f(n-1),f(n)) £2, d(f(n),f(1)) £2.
����,
�� ������� ���� ��������� ������ ������� ���������������� ������ (��������� qhc-������).
��������� 2. ��������� f: {1,2,...,n}�V
������� ������ ���������� ��'������ ����� Gr(V,E) ������� ����������������
������ (��������� qh-������),
����
d(f(1),f(2))£2, d(f(2),f(3))£2, ..., d(f(n-1),f(n))£2.
����,
�� ������� ���� ��������� ������, ������� qhp-������.
�������� 5.1. ���������������� qhc-�����.
�������� 5.2. ���������������� qhp-�����.
� �����
��������� �������� 5.1 �� 5.2 ����'����� ��� �����, �������� ������ ������� ij���� ��� ��� qhc-������, � ����� ���������� ���� ������� �������� 5.2 ��� �����������
������.
����� T(V,E) - �������� ������, xÎV, B(x,1)={x,y1,y2,...,ym}.
ϳ��� ��������� ������� x � ����� {x,y1}, {x,y2},..., {x,ym}
������ T ����������� �� ������� ,
, ... ,
�� ��������
y1, y2 ,..., ym .
������� ��� ����� ��������� t(x)={
,
, ... ,
}.
���� 5.1. ����� T(V,E)- �������� ������,
xÎV, t(x)={,
, ...
,
,�,
},
ïV()ï>1, ïV(
)ï>1, ..., ïV(
)ï>1, ïV(
)ï= ... = ïV(
)ï=1.
���� T -� ghc-����,
�� k£2.
���������. ���������� ���������� k>2 � ��������� gh-���� x=x0, x1,
x2, ..., xn-1 � ����� T. 3 ����������� x0,
x1, x2, ..., xn-1� ���������� �� �������, �� �� ��������
������� V() È V(
) � V(
). �������� ������������
��������� z1, z2,
..., zs. ���������� ��� �����������, �� z1ÎV(
). ���� z1=y1,
�� ��������� z2, z3,..,
zs ÎV(
). ����, z1¹y1. �������� ������������ ������ tÎ{1,2,...,s}, ����� �� ztÎV(
). ��������, �� zt=y1� �� z1, z2, ..., ztÎV(
). ���������� ��� �����������, �� zt+1ÎV(
). ��� ��������� zt+1=y2 � zt+1 , ..., zs ÎV(
). �������� ������������ � ������
V()Í{z1, z2,
..., zs}.
������� 5.1. �������� ������ T(V,E)� ��������� qhc-�������, ��� � ����� ���, ���� ���� ����� ���� x0, x1, ...,xd,
�� �� ������� � ������� V\ { x0,
x1, ...,xd} � �������� ��������� ������.
���������. ������������. ����� d - ������ ������, ����� ������� ��
����� ������� ���������� ���� ��������� x0,
xd. ��������� ����� x0,
x1, ...,xd ����������� ���� �� x0 �� xd.
���
B(x0,1)={x0,x1}, B(xd,1)={xd-1,
xd}
� ����� ������� � ������
B(x1,1)\{x0,x1,x2},
B(xd-1,1)\{xd-2,xd-1,xd}
� �������. ³������
�������� ������ iÎ{2,3,...,d-2}. �������
½B(xi-1,1)½³ 3, ½B(xi+1,1)½ ³3,
�� �� ����� 5.1 �����
������� � ������� B(xi,1)\{xi-1,xi,xi+1}
� ������� �������� ������.
�����������. ��� d=0 ������� ��������:
����-��� ��������� ������� V � qh-������. ����������, �� d>0 � ��������� �� d �������� ��������� qh-����� z0, z1,�, zn-1, ������ �� z0=x0, z1=x1.
����� �������, �� � ���� ������� x0,
xd-����� ������� ������. ��� d=1 ��������� z0=x0,
z1=x1. ����� d>1
� B(x1,1)={x0,x1,x2,y1,y2,�ym}.
�������� ������� x0,y1,y2,�ym
� ����� {x0,x1}, {x1,y1},
{x1,y2},� {x1,ym}. ��������
������ T¢ � ������ x1,x2,�,xd,
�� ����������� ����� �������. �� ����������� �������� � T¢ ���� qh-���� V1, V2, � Vs,
����� �� v1=x1, v2=x2
. ���
x1, x0, y1,y2,�ym,
v2 ,v3, � vs -
qh-���� � ����� T, �� ����������� ������������
����������.
������ 5.1. �������, �� ������ T �
������������ ������ ��� � ����� ���, ���� V(T)=1 ��� V(T)=2.
������ 5.2. ����� Gr(V1,E) - qhc-����, |V|=n, r - ������ ����� n. �������, �� ���� ����������� ��������
V0, V1,�, Vr-1
�, ���� ��
dist(V0, V1)£ 2, dist(V1, V2)£ 2,�, dist(Vr-2, Vr-1)£ 2, dist(Vr-1, V1)£ 2 .
����� Gr(V,E) - ��������� ��'����� ����, |V|=n. ���� |B(x,1)|³+1 ��� ����-��� ������� xÎV, �� ��
�������� ij���� [5, ����. 74] ���� Gr(V,E)
� ������������. �� �������� �������� ������ ����������������� �����, �� �
�������� ���� ������� ij����.
������� 5.2. ����� Gr(V,E) - ���������
��'����� ����, |V|=n. ���� |B(x,2)|³+1 ��� ����-��� ������� xÎV, ��
���� Gr(V,E) � ����������������.
���������. ����� ������������� y1,y2,�,yk
����� ������ ����� � ������ d(y1,y2)£2, d(y2,y3)£2,�, d(yk-1,yk)£2, �������� ������������ x1,x2,�,xt
����������� �������. ��������, �� B(x1,2)Í{x1,x2,�,xt},
B(xt,2)Í{x1,x2,
�, xt}. ������� t£n � |B(x1,2)|³+1, |B(xt,2)|³
+1,� �� ���������� ��� ������� xi,xi+1,
iÎ{1,2,�,t-1} �� xi+1ÎB(x1,2), xiÎB(xt,2).
������������ ������� x1,x2,�,xt
� ������ �������
x1,xi+1,xi+2,�,xt,xi,xi-1,�,x2
.
��������
�� ������������ �� z1,z2,�,zt
� �������, ��
d(z1,z2)£2, d(z2,z3)£2, �, d(zt-1,zt)£2, d(zt,z1)£2.
����������,
�� t<n � �������� ������� xÎV\{z1,z2 ,�,zt} � ������� zj, jÎ{1,2,�,t} ���, �� d(zj,x)=1. ��� ������� �� �������� ���������
����������� x,zj,zj+1,..,zt,z1,z2,..,zj-1
�� �������� 2, �� ����������
������������� t. ����, t=n � z1,z2,..,zn
- qh-���� � ����� Gr(V,E).
��������
�������� 5.1 �������������� ���������������� ������ ����� ��������� �� ���
������� ��� �������� ������ �����������������. ��� ���� �� � ���.
�������� 5.3. �� ����� ������ ���� � ����������������? ��������, �� ������� ����
���������� ���������, ���� ��������� ������ ����� ���� ������� � ������
������.
�������� 5.4. �� ����� ��������� ���� � ����������������?
�������
x qhc-�����
Gr(V,E) ������� ���������, ���� ����
qh-���� x1,x2,�,xn � Gr, ����� �� x=x1
� d(x1,x2)=1.
���� V={x}, �� ����� ������� �������
x ���������. � ���������
����������� � ������ 5.1 �������, ��
����� qhc-������ �� ��������
�������. ��� ��������������� �������� qhp-�����
������� �� �������� ���������.
�������� �. ����� Gr1(V1,E1)
- qhp-���� � qh-������ y1,y2,�ym.
³������ �������� qhc-���� Gr2(V2,E2),
V1ÇV2=Æ ï¿½
��������� �������� x � qh-������ x=x1,x2,�,xn, d(x1,x2)=1.
�������� ����� ���� Gr(V1ÈV2,E), �� E=E1ÈE2È{(ym,x1)}. ���������, �� ������������ ������
y1, y2,
�, ym, x2, x1, xn, xn-1, � , x3
� qh-������ � ����� Gr.
����, � ��������� �������� ��������� � �������� ����� qhp-���� Gr. ��� ����, ���� Gr1,
Gr2-������, �� Gr -
��� ������.
�������� �. ����� Gr(V,E) - qhp-���� � qh-������ y1,y2,�ym.
³������ ������� ������� yt,
���� �� d(y1,yt)=1.
�������� �������� ������� xÏV � ���������� ���� Gr¢(VÈ{x},E¢), �� E¢=EÈ{(x,yt)}.
³������, �� ������������
x, y1, y2,�,
yt, yt+1 , �, ym
� qh-������ � ����� Gr¢. ����,
� ��������� �������� ��������� � �������� ����� qhp-���� Gr¢. ��� ����, ���� ���� Gr ���
�������, �� Gr¢ ���
������.
������� 5.3. �������� ������ T(V,E)
��������� qhp-������ ��� � �����
���, ���� T(V,E) � qhc-�������, ��� T(V,E) ����� �������� � ������� qhc-������
���������� ������������� �������� �, � ��������� qhc-�����.
���������. ����������� ������� � ��������� �������� ��������� � � �. ��� ���������
����������� ��������� ������ qh-����
y1,y2,�,ym �
����� T(V,E) � ���������� ���
�������.
������� 1: ������� y1 �� �
������� �������� ������ T(V,E).
�������� ������������ ������ tÎ{1,2,�,m}, ����� �� d(y1,yt)=1. ��������� ����� ������ � �������� y1,
yt, �������� ���������� � ������ T(V,E)� ����� {y1,yt}. ���� t=m, �� T(V,E) - qhc-����.
����������, �� t<m. ��������, �� {yt+1,�,ym}ÇV(
)=Æ.
�������,
�� qhp-������ � qh-������ yt, yt+1,�,
ym. ��� ���� V(
)={y1,y2,�,yt-1},� d(y1, yt-1)=1.
����,
- qhc-������ � ��������� ������ y1. ���������� �������, �� T(V,E) ����� �������� ���������
��������� � ��
������
.
������� 2: ������� y1 �
������� �������� ������ T(V,E).
�������� ������ tÎ{1,2,�,m} ���, �� (y1,yt)ÎE.
��������� ����� ������� � ������� yt,� �������� ���������� � T(V,E)
����� (y1,yt).
����, �� V(
)={y2, y3,�, yt,�, ym}
�
�- qhp-���� � qh-������ y2, y3,�,
yt, yt+1 ,�, ym. ���� t=2, �� T(V,E) �����
�������� �
���
��������� �������� �. ���� � t >2, ��
T(V,E) ����� �������� �
�� ��������� �������� �.
��������,
�� ����������� ��'����� ���� Gr(V,E)
���������� qr-������, ���� ����
ᳺ���� f:w�V, ���� �� d(f(i),f(i+1))£3 ���
����-����� iÎw.
��'�����
���� ���������� �������� ���������, ���� ��������� ������ ����� ����
������� ���������.
���������
������������ ������ T(V,E)
���������� ��'������� ������������ {xn:nÎw} ����
������, �� ����������� ��� �����
(�) d(xn, xn+1)=1 ���
��� nÎw;
(��)
���� ��������� ������ {xn:nÎw} ������
T(V,E) ����������� �� ��������
������.
���������,
�� �� ����� ���������� �������� �������� ������ �� �������, ��� �� �����
������� � ������� ������������ �������� ���������� ����� ���� ��'������� ������������
������, �� ����������� ����� (�).
������� 5.4. ���������� �������� �������� ������ T(V,E)
��������� qr-������ ��� � �����
���, ���� T(V,E) �� �������.
���������. ������������. ����� {xn:nÎw} -
��'������� ������������ ������ � ������ d(xn,xn+1)=1,
nÎw.
��������� ����� U ������� ��� ������
� V\{xn:nÎw}, �������� � ��������� ������� {xn:nÎw}. ���
����� ������� yÎU ��������� ����� Ty ������ � ������� y, �������� ���������� ����� (y,xm), �� xm - �������, ������ � y. ����������, �� ���������� ������� zÎU, ����
�� ������ Tz ����������.
�������� ������� xi, ���
��� {xi,z}ÎE. �� ������ ������� ���� ����
��������� {vn:nÎw} ������
������ T(V,E) , �� d(vn,vn+1)£3 ��� ��� nÎw.
�������� ������ sÎw ���,
��� B(xi,3)Í{v1,v2,�,vs}. ������� ������ Tz� ����������, �� ���������� ������ t>s, ����� �� �vtÎTz. ���
{vt, vt+1,
�}Ç {xn: nÎw}=Æ.
��������
������������ � ���, �� ������������ {vn:nÎw}
������ ��� ������� ������ V.
�����������. ����� {xn:nÎw} -
������� ������ T(V,E). ���������
����� T0 ������ � ������� x0, �������� ���������� � T(V,E) ����� {x0,x1}. ��� ������� nÎw, n>0 ��������� ����� Tn ������ �
������� xn, ��������
���������� ����� {xn-1,xn},
{xn,xn+1}. ���� |V(Tn)|=1,
��������� xn¢=xn. ���� � |V(Tn)|>1, ���������
������� ������� xn¢ÎV(Tn), ������ � �������� xn.
��������� kn=|V(Tn)|,
nÎw. ��
�������� 4.1 ������� ᳺ����
f0:{1,2,�,k0}�V(T0), f0 (x0¢)=1, f0 (x0)=k0,
f1:{k0+1,k0+2,�,k0+k1}�V(T1), f1 (x1¢)=k0+1, f1 (x1)=k0+k1,
f2:{k0+k1+1,k0+k1+2,�,k0+k1+k2}�V(T2), f2(x2¢)=k0+k1+1, f2(x2)=k0+k1+k2,
���
�� ������������� �����
d(fn(i),fn(i+1))£3
��� ��� nÎw, iÎ{k0+k1+�+kn-1+1,
k0+k1+�+kn}.
���������
ᳺ���� f:{1,2,�}�V �� �������� f(i)=fn(i) ��� � �����
���, ���� i ������ � ������� ���������� ������� fn. ������� ������� � ����� T(V,E) �� ��������� xn
�� xn¢ ��
��������� 2, �� f - ������ ���������.
�������� 5.5. ���������������� qr-������.
��������
���� ��������� � ���� �������� ������ qr-������.
�������
x ��'������ ����� Gr(V,E) ������� �������� �������� ���������� (�������� ������������), ���� ���� B(x,1) �������� (����������).
������� 5.5. ����� T(V,E) - qr-������, x,yÎV,� x1,
x2, �, xn� - ����������� ���� �� x
�� y, x=x1 y=xn.
��������� ����� Tx,Ty ������
� �������� x, y, �������� ����������
����� {x,x1}, {xn-1,y}.
���� ������ Tx, Ty ����������, �� x2, x3,�, xn-1�� - ������� �������� ������������.
���������. ³������ ���������� {vn:
nÎw}, �� ��������� ����� ��
������� ������. ������ �������, �� xn-1
- ������� �������� ������������ � ����������� ���������� ���������. ����������
����������: ���� B(xn-1,1)
��������. �������� �������� ���������� ����� t, ���� ��
B(xn-1,1)Í {v0, v1, �,vt}, vt
Î Ty, y¹ vt .
��� {vt+1 , vt+2 ,�}Ç Tx= Æ, �� ���������� ������������ ������ Tx.
������� 5.6. ���� �� ������� ������� ��������� ������ T(V,E) � ��������� ��������
������������, �� T(V,E) - qr-������.
���������. ����� {vn: nÎw} -
��������� ������ ������. ���������� {yn:
nÎw}, �� ��������� ����� ��
������� ������, �������� ����������. ��������� y0=v0. ����������, �� ��� ��������� ������
{y0,y1,�,yk}
�����������. ³������ ����� ������� vÎ{vn: nÎw}, ����� ��� �� ������� ������
{y0,y1,�,yk}.
����� z1, z2,�,zm -
����������� ���� �� yk� �� v, yk =z1, v=zm. ������� z2,
z3,�,zm-1 - ������� �������� ������������, �� ����� �������
�������
yk+1Î B(z2,1)\ {z1,
z2, z3}, yk+2Î B(z3,1)\ {z2,
z3, z4},�,
yk+m-2Î B(zm-1,1)\ {zm-2,
zm-1, zm},
����� � ���� �� ��������
������ {y0,y1,�,yk}. ���������� ������ {y0,y1,�,yk} ���������� �� ���� ����
������ {yk+1,yk+2,�,yk+m-2, v}.
��������� ����� Gr(V,E) -
�������� ������� ����. ������� f: w�V
������� ���������������� �������� (��������� qh-��������), ���� d(f(i),
f(i+1))£2 ���
��� iÎw. ����,
�� ������� ���� ᳺ���� ������� qhr-������.
�������� 5.6. ���������������� qhr-������.
��������� �������� ������ ������, �� ���� qhr-����� ������ ������ �� ���� qr-�����.
��������� ������ 5.3.
����� T(V,E) - ������� ������, xÎV,
,
, �,
Î t (x), |V(
)|>1, |V(
)|>1,�|V(
)|>1.
���� T(V,E) - qhr-����, �� k£ 4 �
����� ����� ,
, �,
��� ����� ������
������������ ������.
��������� ���������� ���� ����������� ������ � ��������, ���'�����
� ������������ �������� ���� ����������.
��������� ������ 5.4.
���������� �� ��������� ������� 4.1, ������� �������� �������� �������
��������� � ��������� ���������� �������� �����. ������� ���� ����������.
��������� ������ 5.5.
������� ���������, �� �� �������� ���������� ������ ����������, �� � ��
������ qhc-������, qhp-������? ������� �� ���������.
��������� ³����, �� ������ ��������, �� � ������� ���������� ������� ���� ������������, ��������� NP-������ [6].
��������� ��������
5.7. �� � NP-������ ������
���������� ���������� �������� ����� �� ��������� � ����� qh-�����? qh-�����?