Элементы теории графов. Домнин Л.Н. - 80 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

s
t.
s
°
t
°
s
°
t
°
6
6
¾¾¾
¾
6 6
6
6
¾¾
?
?
¾¾
6
6
6
t,
s.
s t
s
°
(3, 5)
(4; 4)
t
°
s
°
t
°
r
r
r
r
r
r
r
r
r
r
r
r
r
s
t
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r r r r r r r
r r r r r r r r
e
e
ìåðå óäàëåíèÿ îò íà÷àëüíîé òî÷êè s íå óáûâàåò, à ðàñòåò11 .
Ïðîöåññ çàâåðøàåòñÿ, êîãäà ôðîíò äîñòèãàåò ÿ÷åéêè t. Ñîîò-
âåòñòâóþùàÿ ðàçìåòêà ïðèâåäåíà íà ðèñ. 4.5,a. Êîíôèãóðàöèÿ

                                                  1   2    3   4       5   6   7    8
       2   1   2   3       4   5   6   7     1 2 1 ¾2 ¾3 4 5 6 7
                                                  ?    6
       1 °
         s         4                   8     2 1 °
                                                 s             4                    8
       2   1       5       6       10 9      3 2      16        ¾6
                                                               56              10 9
       3   2       6       7   8   9 10      4 3      26        ¾76
                                                               66 ¾8 ¾9 10
                                                       ¾4 ¾5   ?
       4   3   4   5               10 11     5 4      36                       10611
       5       5   6       7       t
                                   °         6 5           5   6       7       6
                                                                               11
                                                                               t
                                                                               °
       6           7       8                 7 6               7       8
       7   8   9   8       9 10 11           8 7      8    9   8       9 10 11
                       a                                           á
                                       Ðèñ. 4.5
ñàìîé òðàññû äëÿ ïðîâîäíèêà âûÿâëÿåòñÿ ïðè äâèæåíèè ïî
ÿ÷åéêàì ñåòêè, åñëè, íà÷èíàÿ ñ ÿ÷åéêè t, ïåðåõîäèòü ê ñîñåä-
íåé ñ ìåíüøèì çíà÷åíèåì ïîìåòêè, ïîêà íå áóäåò äîñòèãíóòà
ÿ÷åéêà s. Ýòà îïåðàöèÿ îòîáðàæåíà íà ðèñ. 4.5,á, èç êîòîðîãî
ïîëó÷àåì ñëåäóþùèå âàðèàíòû êðàò÷àéøèõ ïóòåé èç s â t :
                                    (3, 5)
   s (1;2)(1;3)(1;4)(2;4)(3;4)
   °                                       (4;5)(4;6)(4;7)(5;7)°t;
                                    (4; 4)
   s (3;2)(4;2)(5;2)(5;3)(5;4)(4;4)(4;5)(4;6)(4;7)(5;7)°
   °                                                                t,
ãäå â êðóãëûõ ñêîáêàõ óêàçàíû êîîðäèíàòû ÿ÷ååê â ñîîòâåò-
ñòâèè ñ íóìåðàöèåé ñòðîê è ñòîëáöîâ ñåòêè íà ðèñ. 4.5,á. Ïðàê-
òè÷åñêè âàðèàíò, èñïîëüçóþùèé êëåòêó (3;5), íå öåëåñîîáðà-
çåí, òàê êàê ñîäåðæèò áîëüøå óãëîâ è, çíà÷èò, ìåíåå íàäåæåí.
   r r r r r r r r     êà÷åñòâå äîïîëíèòåëüíîé èëëþñòðà-
   r e
     rs r        r
   r r r r r r     öèè ê ðàññìîòðåííîìó ïðèìåðó íà ðèñ. 4.6
   r r r r r r r   èçîáðàæåí ãðàô, ñîîòâåòñòâóþùèé ïå÷àò-
   r r r r     r r íîé ïëàòå: êàæäàÿ ñâîáîäíàÿ êëåòêà ïðåä-
   r r r r t e r r
   r     r r     r ñòàâëåíà âåðøèíîé, à ôàêò ñîñåäñòâà êëå-
   r r r r r r r r òîê (ïî ãîðèçîíòàëè è âåðòèêàëè) îòîáðà-
      Ðèñ. 4.6     æåí ðåáðîì.
 11 Ïîýòîìó    àëãîðèòì íàçûâàþò òàêæå âîëíîâûì.


                                           80

Страницы