� 10. �������� �������� �������� ���� � ������
���������
����� I ���� � �������� ������ N={1,2�} � �������� ����� E={(1,2),(2,3),�}. � ����� ���������
���������������� ������ B
��������� ������ � ����, ��� ���� ����������� ���� � ����� �����������.
BB(I), ��B(I)
B,�
B(I)
B.
����� Gr1(V1,E1),
Gr2(V2,E2)
─ �����, kÎN. ³���������� f ������� V1 �� ������� V2 ���������� k-����������, ���� B(f(x),1)Í f(B(x,k)) ��� ������� xÎV1. ���� 10.1 ��������,
�� ����������� f: V1 �V2 � -������������ ������� ��������� B(Gr1) �� ������� ��������� B(Gr2) ��� � ����� ���, ���� f ─ ��������� ����������� ���
������� kÎN.
���� 10.1. ����� Gr1(V1,E1),
Gr2(V2,E2)
─ �����, kÎN, f ─ k-���������
����������� V1 ��� V2 .
��� B(f(x),m)Í f(B(x,km)) ��� ��� xÎV1, m Îw.
���������. ��������� ������� xÎV1, m Îw. ��� �������� yÎB(f(x),m) �������� �������� y1, y2,
�, yn, n<m � ��� B(f(x),m), ���
�� y1=f(x), yn=y � (yi, yi+1)ÎE2 ��� ��� i£ n-1. ��
����������� ������� �������� x1,x2,�,xnÎV1, ��� �� x=x1, f(x1)=y1, f(x2)=y2,�, f(xn)=yn �� d(xi, xi+1)£ k ���
���� i£ n-1 .
������� y=yn, n£ m,� �� yÎf(B(x,km)).
���� 10.2. ����� Gr1(V1,E1),
Gr2(V2,E2)
─ �����. ���������� �� ����
����������� g: w�w, ����� �� |B(x,m)|£ g(m)� ��� ��� xÎV1, m Îw. ���� B(Gr1) B(Gr2), �� ���� kÎw, ����� �� |B(y,m)|£ g(km) ���
��� yÎV2, m Îw.
���������. ����� f ─ -����������� B(Gr1) �� B(Gr2). �������� kÎw ���, �� B(f(x),1) Í f(B(x,k)) ��� ��� xÎV1. �� ����� 10.1� B(f(x),m)Í f(B(x,km)) ���
��� xÎV1. ����, |B(f(x),m)|£ g(k,m) ��� ��� xÎV1, m Îw.� ������� f �������� V1 ��� V2
, �� |B(y,m)|£ g(km)� ��� ��� yÎV2, m Îw.
���� 10.3. ��� ��������� ������������ ����� Gr(V,E),
B(I) B(Gr) ��� � ����� ���, ���� ������� �������� V=ÈiÎw Vi � ���������� ����� m, ��� �� |Vi|£ m � B(x,1)ÇVj=Æ ï¿½ï¿½ï¿½ ��� xÎVi, i Îw� � ��� j>i+1.
���������. ����������, �� B(I)B(Gr) �
���������
-����������� f:
N� V.
�������� ���������� ����� k ���, �� B(f(y),1) Í f(B(y,k)) ���
��� yÎN. ��������� m=2k+1
� ����'��� ������� ����������� ����� N �� ��������� ������ A0, A1,� ������� m. ���������
V0 =f(A0), V1
=f(A1)\V0 , V2=f(A2)\(V1ÈV2), �.
����,
�� |Vi|£ m � V=ÈiÎw Vi. ��������� iÎw �� ������� �������� ������� xÎVi. �������� aÎAi, ��� ����� f(a)=x. ���
B(x,1) =B(f(a),1)Í f(B(a,k))Í f(Ai-1ÈAi ÈAi+1).
����, B(x,1) ÇVj = Æï¿½ ��� ��� j>i+1.
����������,
�� ���� �������� V=ÈiÎw Vi � ���������� ����� m, �� ������������� ���������� ����.
��������� ᳺ���� f: N� V ���, ��
� ���� a,bÎN, a<b � f(a)ÎVi, f(b)ÎVj�� �������
i<j. ��������� iÎw �� ������� �������� ������� xÎVi. �������� aÎN � f(a)=x.
���
B(f(a),1)=B(x,1) Í Vi-1ÈViÈVi+1 .
����, B(f(a),1)Í B(a,2m). ����� �������, �� f ─ 2m- ��������� �����������. �� ����� 10.1, f � -����������� B(I) �� B(Gr).
����� B(X,P,B) ─ ������� ������� ���������, aÎP. ��'������� ������������ <xn>nÎw
�������� ������� X ������� a-��������, ���� xn+1 Î B(xn,a) ��� ��� nÎw.
���� 10.4. ����� B(X,P,B) ─ ������� ���������, aÎP. ���� B(I) B, ��
����� ���'������ ��'� a-��������
�� ������� X ��������.
���������. �����
f: N� X -�����������. �������� mÎw ���, ��
(*) B(f(y),a)Í f(B(y,m))
��� ��� yÎN. ����� <xn>nÎw �a-������. �������� y0ÎN � f(y0)=x0. ������������
������������� (*), �������� ���������� ������������ <yn>nÎw � N, ���� �� f(yn)=xn � |yn+1 - yn|£ m ��� ��� nÎw. ������� ������������ <yn>nÎw
��'�������, �� ������ [a,b]ÌN ������� m, ������ ����� e, ���� �� f(e)Î{xn: nÎw}. ����� �������, �� �����
���'������ ��'�� a-�������� � X ��
���������� £ m.
���
������� ����������� <ki>iÎw
����������� ����� ��������� [ki]= {1,2,�,ki}, iÎw. ������
�������� X=ÄiÎw [ki] ���������� ������� ���
������� x=(x(0), x(1),�, x(i),�), �����
�� x(i)Î[ki]� � x(i)=1 ���
��� iÎw, ��
�������� ������� ���������� ����� �������. ��� �������� xÎX, mÎw ����������
B(x,m)={yÎX: y(i)=x(i) ���
��� i³ m}.
�������
���������
(X, w, B) ��������� ����� B(<xi>iÎw).
���� 10.5. ����� �<ki>iÎw , <mi>iÎw
����������� ����������� ����� . ���� ki³ mi ��� ��� iÎw, ��
B(<ki>iÎw) B(<mi>iÎw),�� B(<mi>iÎw)
B(<ki>iÎw).
���������. ��� ������� iÎw ��������� ����� ����������� �fi� [ki] �� [mi]. ³����������� f: ÄiÎw [ki]�ÄiÎw [mi] ���������� �� ��������
f(x(0), x(1),�, x(i),�)=(f0 (x(0)), f1 ( x(1)),�, fi ( x(i)),�).
��� B(f(x),m)=f(B(x,m)) ���
��� xÎÄiÎw [ki], mÎw .
����, �f ─ -�����������.
���
������� iÎw ��������� ��'������� ����������� gi: [mi] �[ki] ����� �� gi(1)=1.
��������� ����������� �g: ÄiÎw [mi]�ÄiÎw [ki] ���� ��������
g((y(0), y(1), �, y(i) ,�))
= (g0(y(0)), g1( y(1)), �, gi( y(i)) ,�).
��� g(B(y,m))Í� B(g(y),m) ���� ��� yÎÄ [mi], mÎw. ����, g �� -������������.
���� 10.6. ����� <ki>iÎw ─ ������������
����������� �����,
g: w�w ─ �������� �����������. ��������� m0=k0 k1 � kg(0), mi+1=kg(i)+1 kg(i)+2
� kg(i+1). ��� ������ ��������� B(<ki>iÎw) � �B(<mi>iÎw) ���������� .
���������. ��������� ������� ᳺ���� f0: [m0]�[k0] ´ [k1]´ï¿½´[kg(0)]� � ��� ������� iÎw ��������� ����� ᳺ����
fi: [mi]�[kg(i)+1] ´ [kg(i)+2]´ï¿½´[kg(i+1)] .
������� f: ÄiÎw [mi]�ÄiÎw [ki] ����������� �� ��������
f((x(0), x(1), �, x(i) ,�))
= (f0(x(0)), f1( x(1)), �, fi( x(i)) ,�).
�������
f(B(x,m))=B(f(x),g(0) + g(1)+ �g(m-1)) ��� ������� xÎ ÄiÎw [mi]� � ������� ������������ ����� m,
�� f ─ ����������.
���� 10.7. ����� <ki>iÎw � <mi>iÎw ─ ����������� ����������� �����,
ki>1, mi>1 ���
��� iÎw . ���
B(<ki>iÎw) B(<mi>iÎw),�
B(<mi>iÎw)
B(<ki>iÎw).
���������. �� ����� 10.6 ���� ������������ <Ki>iÎw ����������� ����� ���� ��
������ ��������� B(<ki>iÎw) � B(<Ki>iÎw)� ���������, ������� Ki ³ mi ��� ��� iÎw. �� ����� 10.5
B(<ki>iÎw) B(<mi>iÎw),�
B(<mi>iÎw)
B(<ki>iÎw).
���� 10.8. ����� <ki>iÎw, <mi>iÎw ─ ����������� �����������
�����. ��� ������� iÎw
��������� Ki=k0k1�ki,
Mi=m0m1�mi. ������ ��������� B(<ki>iÎw) � B(<mi>iÎw) ��������� ��� � ����� ���,
���� ��� ������� kÎw� ������� l,mÎw� ���, �� Kk|Ml i Mk|Km.
���������. ����������, �� �� ������ ��������� ��������� � ��������� ������
����������
f: ÄiÎw [ki]�ÄiÎw [mi].
������� f -�����������, �� ���� lÎw, ����
�� f(B(x,k))Í B(f(x),l) ��� ������� xÎ ÄiÎw [ki]. ��������� �������� ������� aÎÄiÎw [mi] � �������� xÎ ÄiÎw [ki], ��� ����� f(x)Î B(a,l). ��� B(f(x),l)=B(a,l) i f(B(x,k)) Í B(a,l). ����� �������, �� f -1(B(a,l))
� ���'������� ��'�������� ���� ������ k.
�������, �� ����� ���� ������ l � ÄiÎw [mi] �� ���������� Ml , � ����� ���� ������ k � ÄiÎw [ki]�� ���������� Kk. ����, Kk|Mb . ��� ����, ��� ������ ����� m ������ ��������� �� ��������� ��� ����������� f -1.
����������,
�� ��� ������� kÎw� ������� l,mÎw , ��� �� Kk|Ml , Mk|Km.
������������ ���� 10.6, ����� �������, ��
K0|M0 ,� M0|K1 ,�� K1|M1,�� M1|K2 ,�� K2|M2, �
���������
s0=K0,� �s1=M0/K0,� s2=K1/M0,� s3=M1/K1 ,�� s4=K2/M1, �
�� ����� 10.6 ������
���������� B(<ki>iÎw) � B(<si>iÎw)� ���������.
���� 10.9. ����� ����� G � ��'��������
����������� ������� ���� ��������� ������ G0ÌG1Ì�ÌGiÌ�, G0={e}, e ─
������� ����� G. ��������� ki=|Gi+1:Gi|,
iÎw. ��� ������� ��������� B(G) ���������
B(<ki>iÎw).
���������. ��� ������� iÎw ����������
Gi+1 �� ���� ������
����� �� ������ Gi �
�������� ����� ������� Xi ������������
������� �����, eÎXi. ����� �����, Gi+1 =GiXi. ³������ �������� ������� gÎG � �������� �������� ������� Gm+1, ��� ��� yÎGm+1. ��� g=e �������� ������� G1. ��� g= gm-1� xm-1,
gm-1ÎGm , xmÎXm-1 .
������� gm-1ÎGm , �� gm-1=gm-2 xm-1 ���� ������ �������� gm-2 ÎGm-1, xm-1ÎXm-1. ϳ��� m+1 ����� �������� �������������
g=x0x1�xm-1xm,��� x0 ÎX0,� x1Î X1,�
�,� xmÎXm.
���������,
�� ���� ������������� ����������. ��� ������� iÎw ��������� ������� ᳺ���� fi: Xi�[ki], ���� �� fi(e)=1.
��������� ᳺ���� f: G�ÄiÎw [ki] �� ��������
f(g)= (f0(x0),
f1( x1), �, fm( xm), 1,1,1,�).
�������
����� �������� ��������� ����� G
�������� � ����� ��������� ������, �� f
─ ���������� �� B(G)� �� B(<ki>iÎw).
���� 10.10. ����� G=Äw Z2 ─ ����� ���� w ����
����� Z2={0,1}. ��� B(I) B(G).
���������. ������ �������, �� I ─
���� � �������� ������ w � �������� ����� E={(i,i+1): iÎw}. ���
������� kÎw
���������� ������� �������
k=a020+a121+�+an2n.
���������
����������� f: w�G �� ��������
f(k)=(a0, a1,�,
an, 0,0,0,�).
���
������� mÎw
���������
Gm={gÎG: g=(z0,z1,�, zm, 0, 0,
0, �),�� z0,�, zmÎ{0,1}}.
�������, ��
B(f(k), Gm)Íf([k-2m+1, k+2m+1]).
�����
�������, �� f ─� - ����������� B(I)� �� B(G) .
������� 10.1. ��� ��������� ������������ ��'������ ����� Gr(V,E) ���������� ����������
B(Gr) B(I),� B(I)
B(Gr).
���������. �� �������� 4.4 ���� Gr(V,E)
������������ �� �����������. ����� ���������� ������� 3-���������
����������� �� I. ����, B(Gr) B(I).
��������
���������� B(I) B(Gr).
���������� ��������, �� ���� Gr
�������� ���������. �� ����� �������
���� ������ <xn>nÎw �
����� Gr. ��������� f(n+1)=xn, nÎw �
�������, �� f(B(x,m))Í B(f(x),m) ���� ��� x,mÎw. ����, f ─
-�����������. ����������, �� ���� Gr �� � �������� ��������� � ���������
������� vÎV �
����������� ����� B(v,1). ��������
������� ������� ���������, {yn:
nÎw} ������� B(v,1)\{v}. ��������� f(n)=yn
, nÎw . �������� f(B(x,m))Í B(f(x),2)� ��� ���� xÎw, nÎw , f ─
-����������� .
������� 10.2. ��� ����� ���������� ����� G
��� ���������� ����������
(i) B(G) B(I);
(ii) B(I) B(G);
(iii)
����� G �� ��������� ��������
���������.
���������.� (i) Þ (iii). ����������, �� B(G) B(I) ���
����� �������� �������� ����� G.
���������
-����������� f:
G � N �
�������� �������� ������� HÌ G, ���� �� B(f(g),1)Í f(B(g,H)). ��������� �������� ������� g0ÎG � �������� �����������
���������� ����� mÎf(B(g0,H)).
�������� g1ÎB(g0,H) � f(g1)=m. ������� H ─ �������, �� B(g1,H)Í B(g0,H). ���� B(f(g1,1))Í f(B(g0,H)) � m+1Îf(B(g0,H)), �� ���������� ������ m. ����,
����� G �� ���� ���� ��������
���������.
(ii) Þ (iii). ����������, �� B(I)B(Gr), ���
����� G �� � �������� ���������.
���������
-����������� f:
N�G �
�������� �������� ������� H Ì G, ���� ��
f(B(n,1)) Í B(f(n),H)
��� ������� nÎN. �������� ����������� ����� mÎf -1 (B(f(1)),H). ������� f(m)ÎB(f(1),H) � H ─ �������, �� B(f(m),H)=B(f(1),H).
�������
f(B(m,1)) Í B(f(m),H), �� m+1ÎB(f(1),H), �� ���������� ������ ����� m.
(iii) Þ (i).
�������� ������� ���������� �������� ��������� ������� G¢ Í G.
����'��� G �� ���� ������ ����� ��
G¢ �� ��������� ����� ������� X �� ������������. ����� �����,
G=G¢X � ����� ������� gÎG ���������� ���������� �
������ g=g¢ x¢ , g¢ ÎG¢ , xÎX.
��������� ����������� f¢: G� G¢ ��� �������� f¢(g)=g¢ . ��������, �� f¢ ─ -����������� B(G) �� B(G¢). ���������� B(G¢) � �������� ���������� B(Cay) ����� ��� ��� ����� G. �� �������� 10.1, ����
-����������� f¢¢ �������
���������
B(Cay) �� B(I).
���� f=f¢¢ f¢ï¿½ ─ �
-����������� B(G) �� B(I).
(iii) Þ (ii). �������� ���������� ��������
��������� ������� G¢ Í G �
���������� �� � �������� ���������� B(Cay).
��������� ������� 10.1.
������� 10.3. ����� G ─� ���������� �����. ��� B(I) B(G)� ��� � ����� ���, ���� ����� G
������ ���������� ������� ������� ���������� �������, ��� G ─ ������� �������� �������� �����.
���������. ����������, ��
B(I) B(Gr)� � ���������� ��� �������.
������� 1. ����� G ������ ������� g ������������
�������. ����� C � ������� ��������� ��������� g, e ─ ������� ����� G. ��������� a={e,g} �
�������, �� ��� ������� �������� xÎG
������������ <gnx>nÎw � a-��������
� B(G). �� ����� 10.4 C ─ ������� ���������� �������.
������� 2. ����a G ���������. ����������, �� G �� �
�������� �������� � �������� �������� ��������� FÌG, ��
������� ���������� ������� G¢. ���������� G �a ���� ������ ����� �� G¢.
�������� ����� ������� X
������������ ������� �����. ��� G=G¢ X � ����� ������� gÎG ����������
���������� � ������ g=g'x, g'ÎG', xÎX.
��������� ����������� f: G� G¢ �� �������� f(g)=g'. ��������,
�� f ─ -����������� B(G) �� B(G'). �������, B(I)
B(G').
���������� B(G') �
�������� ���������� B(Cay) ��
����� ���. �� ����� 10.2. ����� G¢ �������� ������. �� �������� ������� [21] G¢ ��
������������ ������� ���������� �������. ������� H ─ ��������
��������� ��������� ������������ �������, �� H ��������. ����, G'
��������, �� ���������� �� ������.
����� G ─
�������� �������� �����. �� ����� 10.9 ���� ������������ <kn>nÎw
����������� �����, ���� �� B(G)
��������� B(<kn>nÎw ).
��������� ����� H ����� ���� w ����
����� Z2. ��
����� 10.7� B(H) B(<kn>nÎw ). ��
����� 10.10�� B(I)
B(H).
����,� B(I)
B(G).
����������,
�� G ─ �������� ���������� ���������� ������� ������� C, ��������� ��������� g. ����� �������, �� ������� C ���������� � x-1gxÎ{g,g-1} ���
��� �������� xÎG. ���������� G �� ���� ������ ���� �� ������ C � �������� ����� ������� ������������
H={h1,h2,�,hn},� ������� H=H-1.
��� ��� i,j Î {1,2,..,n} �������� a(i,j)ÎZ ���, �� hi,hjÎga(i,j)H. ��������� a=max{|a(i,j)+1|: i,j
Π{1,2,..,n}. ���������� ���� ���
��� ����� G, ���������� ��������
������ HÈ {g,g-1}. ��������� V0={gkH:
|k|£ a}, V1={gkH:
a<|k|£ 2a}, V2={gkH:
2a<|k|£ 3a},�� .
��
�����10.3 B(I) B(Cay).
������� 10.4. ��� ������� ����� G ���
���������� �����������
(i) |
B(I) |
(ii) |
G � ��������� �����������
���������� ������� �����. |
���������
������� � ������� 10.2 � 10.3.
������ 10.1. �������, �� ������� ��������� B(G) ����� G ���������
������� �������� B(Z) ����� ����� ����� ��� � ����� ���, ���� G ─ �������� ���������� ���������� ������� �����.
������ 10.2. �������, �� ������ ��������� B(I) � B(Z) ����������.
��
��������� ����� �������, �� �� ���� ����� G,
��� ��� B(G) ���������
B(I).
������� 10.5. ��� �������� �������� ��������� �����
G1, G2 ���������� ���
����������
B(G1) B(G2),�� B(G1)
B(G2).
���������
������� � ��� 10.9 � 10.7.
������� 10.6. ����� G1, G2�
─ ������� �������� �������� �����. ������ ��������� B(G1) i B(G2) ��������� ��� � ����� ��� ���� ���������� �������� ������ ���������� :
(i) ���
����� �������� ������� FÌ G1 ����
�������� ������� HÌ G2 , ����
��� |F|
─ ������ |H|;
(ii)
��� ����� �������� ������� HÌ G2 ����
�������� ������� FÌ G1 , ����
�� |H| ─ ������� |F|;
���������. �������� ������������ F0 Ì F1Ìï¿½Ì Fi Ì� ����������� ������ ����� G1 ����, �� G1 = ÈnÎw Fi , F0 ─ �������� �������. ��������� ki=|Fi+1 : Fi|,
nÎw. �������� ������������� H0 Ì H1Ìï¿½Ì Hi Ì� ���������
������ ����� G2 ����, �� G2 = ÈiÎw Hi ,� H0 �─ ��������
�������.� ��������� mi=|Hi+1 : Hi|,
iÎw. �� ����� 10.9 B(G1), B(<ki>iÎw ) � B(G2)� B(<mi>iÎw ) �������
��������� ������ ���������. ³������, �� ����� �������� ������� ����� G1 �������� � ����� ������ Fk
� ����� �������� ������� ����� G2
�������� � ����� ������ Hm.
����, �� ������ ����������� ���� 10.8.
���������
��������� ���������� �������� ������ ���� �������.
����� B1, B2 ─
������� ������ ���������. �� ����, �� B2 �B1 (�������� B2
�B1) ���� B1
�B2 (�������� B1
�B2 )?
³������
������� ������� �������� �������� ����� G.
�� �������� 10.3 B(I) B(G). ��
�������� 10.2 ������������ B(G)
B(I)
������. ����, ������� �� ����� ��������� ���������.
����������
������ ���� Gr � �������� ������ w.
��������� ����� Im ���� �
�������� ������ {1,2,�,m} � ��������
����� {(1,2), (2,3),�,(m-1,m)}.
�������� ����� ���� Im+1,
mÎw ������
(m,1) �� ������� m ����� Gr. ���������
���� ��������� ����� Gr'. ��������,
�� B(Gr) B(Gr'), ���
������������ B(Gr')
B(Gr) ��
����. ���� ������� �� ����� ��������� ��� ���������.
������ 10.3. ������� �������� �������� ��������� ���� Gr, ����� �� B(Gr) B(G) ���
����� ������� ����� G.
��������
������ Grw(V,E) ������� ���� Gr(V,E) ����� � �������� w: E � N, �� ������� ������� ����� e ΠE ����
���� w(e)ÎN. ������� ����� x1, x2, �, xn � ��������� ����� ─ �� ���� ������ w(x1,x2), w(x2,x3),�,
w(xn-1,xn.).
��������� d(x,x)=0, xÎV �� d(x,y)= ¥, ���� x,y �������� �����
������� ����������� ����� Gr. ���� �
x,y �������� ����� ������� ���������
����� Gr, ��������� ����� dw(x,y) ������� ������������
��������� ����� �� x � y. ��������� Bw(x,m)={yÎV: dw(x,y)£ m}, mÎw. ������� ��������� (V,w,Bw) ��������� ����� B(Grw).
������ 10.4. �������, �� ������� ��������� B(G)
������� ������� ����� G ���������
������� �������� B(Grw)
������� ��������� ����� Grw.
�������� 10.1. ����� G1, G2 ─ ���������� �������� �������� ����� ���� ���������. �� ����, �� B(G1) B(G2)? �� ����, �� B(G1)
B(G2)? �� �������� 10.5 �� ���, ���� ����� G1,
G2� �������.
��
�������� 10.6. ���� ���� ��������� ������� ����������� �������� ��������
�������� �������� ��������� ����.
�������� 10.2. ����� a ─ �������� �����������
��������. ��� ����������� ������� ���� ��������� a �
������� ������������ ��������� �����������?