� 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) B(G),�� B(G) 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 � ������� ������������ ��������� �����������?