�2. ����������� �������� ����������� ������

 

���������� �������� ��'����� ���� Gr(V,E). �� ����������, ��������� �� ��������� ������, ���� ���������� ���� ����'���� ���� ����� , �� , �� ��� ����� ������� . �������� ����'���� ���� ����� , ��� ����� ����������� �� �������, ���������� �������� ��������� � ����������� .

�� ����������, �������� ������� ������ ����� �� �������� ����� �������� �� ��������� ������, ���� �� ��������� �������� � ����������� ���������� �������. ��������� � ������� �������� �������� ���������� �������� ��������.

������� � ��������� �� ���������� ����� ������� 1.1.

������� 2.1. ����� Gr(V,E) - ����������� ��'����� ����, - ������� ���������� �����. ��� ���� �������� ������� ������ V �� ��������, ������ ����� �� �������� .

���������. �� � � ��������� ������� 1.1 ���� Gr(V,E) ����� ������� �������. ��������� ����� A ��'� ��� �������� , ����� �� , ���� ��'����� � ���� ������������� , �� ����������� �����

������ (*)

��� ��� , , �� - ���� � ����� ������� ������� � ������� . ��������� ����� ������� ��� ��� , ������� A, � ������������� ����������� ����� (*). ������� �� ������� ��������� ������� �� ����� ��������: ��� � ����� ���, ���� � ������������� � ������������ ������������� . ���������, �� ������� ��������� �� �������� 1.1. ��������, �� ����� ������ � ������� �� ������ �����. �� ����� �����, � ������� ���� ������������ ������� . ����������, �� � �������� ������� , ������ � ������ �������� . ������� , �� ��� ��� . �������� ����������� ����� , ��� ����� . ��� �������� ������� ����� , ���� �� . ��������� ��� ��� . �� ���������, �� ���������� ������������� . ����, - ������ ������������� ������� .

���������, �� ��� ����� ������� ������ ������� ��������� �������. ij����, ��������� ������� ������� � ��� ����� ������� ��������� , ���� ����� �������, � ���� ����� �����.

������� 2.1. ���������� �������� ��������� ������ � ����������, �� ��� ����������� ��������� ����� ����� ���� ������ ����� �����, ������ �� ����� . ��������, �� ���� 2-������������� �������� , ��� ����� ����� ���� ������ ������ ������������ �����. ��� ����� ��������� ���� � �������� ������ � �������� ����� . ��������, �� ����� ��'���� ���������� ����� ����� ������ ��������� �� �����. ���� ��������, ��������� ��� �� ������������� ������� 1.1, ���� � ���������� - ������� 2.1.

������� 2.2. ��� ������� ������������ ��'������ ����� Gr(V,E) ���� ������������� , ���� �� ��� ��� .

���������. �������� ����������, �� ����� ���� , ��������. ��� ������� ������� � ����� ����� ������� ᳺ���� .

����������, �� ����� ������� � ������� ���������� ��� . ��� ������� ��������� . ��������� , . ��������� � ���������� �� ���, ��� . ���, ��� ����� ������� ��������� . ����� ����� ��������� ����� ������������� .

³������ ������� ������� . ���� , �� , � ������� ����������. ���� , ��

,

� ������� ����������.

��'����� ���� ���������� ��������� ������� , ���� ��������� ������ ��������� ������� ������� . ��� ����� ���� ���� �� ���������, ��� � ����������� ������������ ������.

������ 2.1. ����� - ���������� �����, Gr(V,E) �������� ������ ������� . �������, �� ���� ������������� , ���� �� ����� ���� ������ 1 ������ ����� ��� �������.

������� 2.3. ����� - ����������� ��������, Gr(V,E) - ��������� ���� ������� . ��� ���� ���� ������������� , �� ����� ���� ������ 1 ������ ����� ��� �������.

���������. � ���������� Gr(V,E) ������, �� . ����, ���� ������ ������� � ��� �������� ����� ����������� ����������� ����������� ������.

� ��'���� � �������� 2.3 ������ ���� �������. ����� - ����������� ��������, Gr(V,E) - ��'����� ����, ������� ��� ��� . �� ����� ������������ ������� ������ ��������� ���, ��� ����� ���� ������ 1 ������ ����� ��� �������? ��������� ������� �� ��������� ������� �� �� �������. ������ ����, �� ������, �� ����� 3-������������� � ���� ���������� ���� �� ��������.

������� 2.2. ����� - ����������� ��������, - ������� ��������� , - ��'� ��� �������� ��������� ������� . ���������� ���� Gr(V,E) � �������� ������ � �������� ����� ������� , �� . ��������� ������� 3-������������� . ������� ������� ����������, �� ���������� ������������� ��������� ������� . ��� ��� ���� ������ ����� ���������� ���� �������. ���������� ���������, �� ��� ��� , � ��� ��� .

������ 2.2. ����� - ����������� ��������, Gr(V,E) - ������ � ��� ��� . �������, �� ���� - ������������� ������� , ���� �� ����� ���� ������ 1 ������ ����� ��� �������.

��� ����, ��� ������ ������� ������������� �������� ������� ������ ������������ ��'������ ����� ���� ���� ���������.

����� Gr(V,E) - �������� ��'����� ����. ������������ ��������� �������� ������� ������� �����������, ���� ����������� ��� �����:

(�)��� ;

(��)�� ��� ;

(���)�� ����� ����������� ������ ��'�����.

�������� ������� ������������ ������� ���������� ����������� , ����

���� ���������� �������� ���������, ���� ��������� ������ ����� ���� ������� ���������. ����� Gr(V,E) - �������� �������� ��������� ����, . ��������, �� � ����������� ������������, � ���� ����������� ���� � ����-��� �� ��������������.

������� 2.4. ��� ������� ��'������ �������� ���������� ��������� ����� Gr(V,E) � ������� ������������ ����� ���� �������� ������� ������� �� ��������, ����������� ������� ����� ���������� ����������� ��������� �������� ������� .

��� ��������� ������� ������������ ����� �����.

���� 2.1. ����� Gr(V,E) - �������� ��'����� �������� ��������� ����, - ������� ���������� �����. ��� ���� �������� ������� ������ �� �������� ��������� , ���� �� ��� ���

(�);

(��) ���� ��'�����;

(���) ���� ��'�����.

���������. �� �������� ����������, ����� �������, �� Gr(V,E) - ������. ��������� ������� ������� � ������� �� �������. ��� ������� ������� -�� �������� ������ ������� ��� ������, ������� �� ���� �� ������ ������� . ������� ������ Gr(V,E) �������� ��������, �� ����� ���� ������ ���������. ���������� ������� ������ V ����� ���������, ������� � ������, �� ����� ��������. ������� ��������� ������� �������� ��� � ����� ���, ���� ����� �� ��������� ���������� ����� ����������� ������, �� �������� � ������. ����� ��� ��������� ������� ��������. ����� ������ ������ ��������� ������ ��������. ����, �� ������� ������� ������ ����������, ����� �� ���������, �� ������� ������ ������ ��������� ���������.

���������� ������� ������� ������ ���: ������ �������� ������� , ��� �������� �� ������� ������� �������, ����� �� ���� �� ������� ������� ������� � �. �.

�� ������� �������� ����� � �� �������, �� ������ �� ������ �� ������ �� ������ ������, �� ��������� ����� ���� ������� ������� �������. �������, �� ���� ������� ������� ������� ���������� �� . ���� � ��� ������ ������ ������, �� �� � ���� ������� . ���� � ��, �� �������� �� �������� �� ������ ������� � �� ���� �������, �� ������ �� ������ �� , �� ��������� ����� ���� ������� ������� ������� � �. �. ϳ��� ���������� ������� ������ ����� �� ������� ������ �������, �� �� ������ �� , � ���������� ��� �� �� � ���������.

��������� ������� 2.4. ������������ ��������� � ���� 2.1 � ��������� . ��������, �� - ���������� ������������. �� ������� � ������ , ��������� ������� 1.2 � ��������� ����������� -������������� ������� . �� ����� 1.5 �� ������������� ����� ������� ���, �� � ������������ ������������� c, . �� ������� ����������� , �������� ����� �� ����� � �������� ������� � . ���� �� ������������� ������� -�������� ������� , ����������� ������� ����������� .

�������� 2.1. ����� Gr(V,E) - �������� �������� ��'����� ����, - ���������� �����. �� ���� - ������������� ������� ������� V, ����������� ������� ����� ���������� ����������� ��������� �������� ������� V?

� ��������� ������� 2.4 �������, �� ��� ��������� ������ �� �� ������� ������ �������� ���� 2.1 �� ������� ������� ��'���� �����. ����� ��� ���� ����������������. ij����, ���������� ������ Gr(V,E) � �������� ������ � �������� ����� . ��������, �� ������� ������ ����� ������ �� ������� ��������, �� ������������� ����� ���� 2.1 ��� .

�������� 2.2. ����� Gr(V,E) - �������� �������� ��������� ��'����� ����, , - ������� ���������� �����. �� ���� �������� ������� ������� V �� ��������, ����������� ������� ����������� ? �� � �������� ������� ����� ��� �����.

���������� ��������� ���� Gr(V,E) � �������� ������ V � �������� ��������� ����� E. �������, �� ���� �� �� ������ � ������� �����. ��� �������� ������ , ��������� � ����'������ ������ ����� ���������.

���� ��������� ���� ������� �� �� },

���� ��������� ���� ������� �� �� },

� ��� ����������� �����������, �� , ��� ��� , .

�� ���������� ��������� �� ��������� ������ , (�������� ), ���� ���������� ���� ����'���� ���� ����� , �� (�������� ). �������� ����'���� ��� �����, ��� ���� ����������� �� ������, ��������� ����� A �� ��������.

������� 2.5. ����� Gr(V,E) - ��������� ����, � ����� ������� ����� �������� ��������� ���� �������� �����. ��� ���� �������� , ���� �� , .

���������. ��� ����� ������� �������� ������� , ��� ��� ���� ����� . ����� ����� �� ��������� ����������� . ���������� ����������� ���� Grf(V,Ef) ����� ����������� � �������� ����������� ����� . ����� �������, �� ����� ��'���� ���������� Grf [S] ����� ����� ���� ���� �� ����� ������ �����.

����������, �� Grf [S] �� �� ������� �����. � ����� ������� Grf [S] - ���������� ������. �������� ������� ������� � ������� �� �������. ��������� ����� ������� ��������. ³������ ������� ������� . ���� ������� �� �� �������, ��������� ������ ��������, � ���� ����� - �������. ��������� ����� ��������� ��� ������� �� ������ ������ ��������. ����, �� .

����� � ����� Grf [S] � ���� . ���� ����� n �����, ��������� ������� ����� �� ���� ������� �� ������ ���������. ��� ��������� ����� n ��������� ������� x1, x2 ������� ��������, � ������� x3, x4 ,.., xn �� ���� - ������ �� ������� ���������. ³������ ������� ������� y, �� �� �������� �����. �������� ������� ����� xi, ��������� �� �������� �� ������� y. ���� �� ������� �����, ��������� y �������� ������� xi, ���� �������, �� � ����� � ���� �������. ��������� ����� S1 �� S2 ������� ������� �� ������ ������. ���� ����� n �����, �� S1=S2=1. ���� ����� n �������, �� S1=1, S2=2

������ 2.3. ����� S - ���������, aÎSax¹x ��� ��� xÎS. �������, �� ���� �������� S=A1ÈA2, ���� ��

S=A1È a-1A1,�� S=A2È a-1A2È a-2A2,

�� a-1Ai ={xÎS : axÎAi},a-2Ai={xÎS : a2xÎAi}.

������� 2.6. ����� Gr(V,E) - ��������� ����, � ����� ������� ����� �������� ��������� ���� �������� �����. ��� ���� �������� ������� ������ V=V1È V2, ����, �� V1=1,.V2£ 2.

���������. ������������ ������ � ������������ � ��������� ���������� �������. ���� ���� Grf [S] �� ����� �������, ��������� �� ������� ��������.

����������, �� Grf [S] �� �� �����. ��������� ����� x ����� ������ ������� ��������. ³������ ������� ������������� ������� yÎS � ��������� ������� d(x,y). ���� ����� d(x,y) �����, ��������� ������� y ������ ��������, � ������ - �������. ��������, �� S1=1, S2£2.

����������, �� ���� Grf [S] �� ���� x1, x2 ,.., xn . ����� �������, �� x2 =f(x1), x3=f(x2),�, xn=f(xn-1), x1 =f(xn). ���� ����� n �����, ��������� ������� ����� �� ���� ������� �� ������ ���������. ³������ ������� ������������� ������� y. ���� ������� �� y �� ��������� ������� xi ����� �����, ��������� y �������� ������� xi. ���� �� ������� �������, ��������� ������� ����� � ���� �������. ����, �� S1=1, S2£2.

��� ��������� ����� n ��������� ����� T1, T2, �, Tn ������ � �������� x1, x2 ,.., xn , �������� ���������� ����� �����. ���������� ��� �������.

����������, �� ���������� ������� xi �����, ��� ��� ������ Ti �������������. ������� ���������, ����� �������, �� i=1. ��������� ������� x1, x2 ������� ��������, � ������� x3, x4 ,.., xn ��������� �� ���� ������ �� ������� ���������. ��� ���������� ������������� �� S �� � � ������� ������� ����� n.

���������� ���������� �������, ���� �� ������ T1, T2, �, Tn�� � ���������������. ��������� ������� x1, x2 ,.., xn ������ ��������. ³������ ������� ������������� ������� z. ���� ������� �� z �� ��������� ������� ����� �����, ��������� z ������ ��������, ���� �������, �� �������. �� � �������, ��� � � ������� �������� S1=1, S2£ 2.

������ 2.4. ����� S - ���������, aÎSax¹x ��� ��� xÎS. �������, �� ���� �������� S=A1È A2, ���� ��

S=A1È aA1,�� S=A2È a-1A2 È a-2A2

����������� ��������� � ��� ���� ���������� ���������� � ����� ���� ����������� ������.

����� X - ������� ��������� �������, Á - ����� ��'� �� ���������� ��������. ϳ�������� AÍ X ���������� Á-�������, ���� FÇ A¹Æ ��� ����-��� ��������� FÎÁ.

��� ����������� ��������� n ������� X ���������� n- ���������� ������� ��'� Á, ���� X ����� ������� �� n Á-������� ��������. � ����������� ��������㳿 ������� Xn-���������� ������� ��'� Á, ���� X ����� ������������ n ��������� ���, �� ����� ��������� FÎÁ ������ ����� ��� n �������. ����� n-��������� ������� Xn¢-���������� ��� ��� ��������� n¢£ n. �������� ������� ��������� n, ��� ���� ������� Xn-���������� ������� ��'� Á, ���������� ���������� ����������� X ������� ��'� Á. ��������, �� ������� X 1-��������� ������� ����-��� ��'� Á. ������ ������ 2-������������, �� �������, �������� ����� ������������. ��������� (Á)= inf {|F|:FÎÁ}. ��������, �������� ����������� X ������� Á �� �������� (Á). ������� X ���������� ����������� ���������� ������� ��'� Á, ���� X(Á) -���������� ������� Á.

��� �������� ����� Gr(V,E) � ����'������ ������ ����� r ��������� ����� g (Gr,r) �������� ����������� ������� ������ V ������� ��'� ��� ���� {B(x,r): xÎV} ������ r.

� ������� ����������� ������� 1.1 � 2.1 �����������, �� g(Gr,r-1) ³ r ��� �������� ������������ ����� r � ��'������ ����� Gr, �� �� ��������� r ������. ������� 1.3 ������, �� ���� ��������� ��'����� ���� Gr � �� �������� ������� ������� ������� ��������� �������� ������, ��� ����� g (Gr,1)=2. ��������� �������������� � ������� 2.2. � ������� 2.1, 2.2 � ������ 2.3 ������������ ����������� ������������ ��������� ������ ������� ��'� ���� ������ 1.