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

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

C�������� ������. �������� ����������.

������ ��������

����� ������ G ������ ���������� ������ V ( �������� ������� v0 ), ��� - E � �(v,-) - �������� �������� ������� v �� V. �� ������ ������� ��������� ����������� � ���������� ���������� USE ��� ������� V � �������� �� ������ ����.

������� ����� ��������� �������� ����������� ����� �����, � ��������� ������� ������������ ������� ������. ������ ������ �������� �� ����������� �������� ���� �� �������� ������, ����� - �� ���������������� ��������� ������ ������ 0 - ��������, 1 - ������� � ���, 2, 3 � �.�., ��. ���.

����� ������ ������ � ������ ������� ( �� ������ � ������� ):
 ����� ��������� ��������� ������������������: 0 - 1 - 4 - 5 - 2 - 6 - 7 - 8 - 3
����� ������������ ��������� ����������� ��������� WALK: 
   |--------|  |---------------------|
   |        |  |                     |
 ->� USE(v) �->�FOR  w �� �(v,-) DO  �----->
   |        |  |                     |
   |--------|  |---------------------|
                        |
                        V        � 
                                 |
                   |----+-----|  �
                   |          |  |
                   � WALK(w)  �->-     
                   |          |
                   |----------|                     


    

   �������:

	  0 |      0=v0
	    |     /|\
	    |    / | \
	    |   /  |  \
	  1 |   1   2  3
	    |  /|   |\
	    | / |   | \
	  2 |4  5   6  7
	    |           \
	    |            \
	  3 |             8

              ���.1.











 ������ ��������� ����������   WALK(v0),  ���������  USE(v)  ���������

 ��������� �������   v.


 H������������ ������� ���������� ������ ������ ������ � ������

������� ��������� ������������� ������������� ������� �����  STACK


  --------------|  |-------------------------|
  |             |  |                         |
->� v0 => STACK �->�WHILE  STACK # �����  DO �---->
  |             |  |                         |
  --------------|  |-------------------------|

                            V           �

                   |-----------------|  �
                   |                 |
                   �    v<=STACK     �  �
                   |                 |
                   �      USE(v)     �->-
                   |                 |
                   � �(v,-) => STACK �
                   -------------------       |-----------------------|
                                             |                       |
              |----------------|             � FOR  w  ��  �(v,-) DO �->
              |                |             |                       |
   ��������   ��(v,-) => STACK �   ��������  |------+----------------|
              |                |            
              |----------------|               |----v-------|  �
                                               |            |  |
(������ � ���� ����� ����������� �(v,-)  )     � w => STACK+>---
                                               |            |
                                               |------------|




������� ������������� ������:


   - ������� ������ ������� ������� �� �����


   - ������������ ������


   - ��������� "�������� � ��������" (���������� ��� H������,

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

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

       �����).



 ����� ������ ������ � �������� ������� - ������� � �������� ������.





     4 - 5 - 1 - 6 - 8 - 7 - 2 - 3 - 0

 ��������� ������ ����������� ����������� ���������  BACK(v)


     �� --------------------->------------------�

  ------+------�   ----------------------�   ---V---�    ---------�

->��(v,-) ����� �->� FOR  w  �� �(v,-) DO �->�USE(v) �-->�v<=STACK �-->

  -------------��� ------+----------------   --------    ----------

                    -----v-----�   �

                    � BACK(w)   �->-

                    ------------




    ��������� ��� �������  BACK(v0). H������������ ������ ����� ������

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

������� ������������� ������:


   - ������ ��� � ������ �����������,


   - ������������ �����,


   - ������������ ����������������.





 ����� ������ �����  (������� �������  0, ����� 1, � �.�.)


 � ����� ������:

    0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8


��������� ������������� ��� �� �����, � �������  QUEUE


     ---------�    --------------------------�

 --->�v=>QUEUE �-->�WHILE  QUEUE # �����  DO  �-------->

     ----------    ----------+----------------

                    ---------v--------�  �

                    �    w<=QUEUE     �  �

                    �      USE(w)     �>--

                    � �(w,-) => QUEUE �

                    -------------------












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









 
     SpyLOG