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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

1) P
0
P
(0)
a
=
0
c
0
f
c
c
= P
(1)
a
2) P
0
P
(1)
a
=
a
b
c
d
e
f
bc
ec
df
fc
df
bc
P
(2)
a
=
0
ec
df
fc
df
bc
3) P
0
P
(2)
a
=
a
b
c
d
e
f
bec
cdf + edf
dfc
cdf + fbc
cdf + dfc
bec + cdf
P
(3)
a
=
0
cdf + edf
0
fbc
cdf + dfc
bec
4) P
0
P
(3)
a
=
a
b
c
d
e
f
0
ecdf + edfc
dfbc
fbec
dfbc
bcdf + bedf
P
(4)
a
=
0
ecdf + edfc
0
fbec
dfbc
0
5) P
0
P
(4)
a
=
a
b
c
d
e
f
becdf + bedfc
edfbc
dfbec
0
dfbec
becdf + bedfc
P
(5)
a
=
becdf + bedfc
0
0
0
0
0
(a,b,e,c,d,f,a)
(a,b,e,d,f,c,a),
                                                                                  
                       0                            a   bc                         0
                     c                            b  ec                      ec   
         (0)         0        (1)        (1)      c  df       (2)            df   
1)   P0 Pa        = f 
                          = Pa ; 2) P0 Pa =               , Pa =                   ;
                                                  d     
                                                       fc 
                                                                         
                                                                                 fc   
                                                                                       
                       c                            e   df                        df
                       c                           f    bc                        bc
                                                                   
                     a       bec                              0
                     b 
                       
                          cdf + edf 
                                                       cdf + edf 
            (2)      c      df c              (3)          0       
3) P0 Pa          = d  cdf + f bc  ,         Pa =   
                                                                      ;
                                                                      
                                                         f bc      
                     e   cdf + df c                    cdf + df c
                     f    bec + cdf                         bec
                                                                     
                     a          0                              0
                     b 
                       
                         ecdf + edf c 
                                                       ecdf + edf c 
            (3)      c       df bc             (4)          0        
4) P0 Pa          =                    ,     P     =                 ;
                     d       f bec    
                                                 a          f bec      
                                                                       
                     e       df bc                         df bc
                     f    bcdf + bedf                          0
                                                                              
                    a       becdf + bedf c                      becdf + bedf c
                    b          edf bc                              0          
                                                                              
            (4)     c          df bec              (5)              0
5) P   0
           Pa     =                         ,     Pa     =
                                                            
                                                                                 .
                                                                                 
                    d            0                                 0          
                    e          df bec                               0
                    f       becdf + bedf c                            0

    Çäåñü ïîä÷åðêíóòû ýëåìåíòû, ïîäëåæàùèå óäàëåíèþ ïå-
ðåä âûïîëíåíèåì ñëåäóþùåé èòåðàöèè. Ýòî äèàãîíàëüíûå ýëå-
ìåíòû ïðîìåæóòî÷íûõ ñòîëáöîâ è ïðîèçâåäåíèÿ ñ ïîâòîðàìè
âåðøèí. Äèàãîíàëüíûé ýëåìåíò ïîñëåäíåãî ñòîëáöà ñîäåðæèò
äâà ïðîèçâåäåíèÿ âåðøèí. Ýòî îçíà÷àåò, ÷òî â ðàññìàòðèâà-
åìîì ãðàôå åñòü äâà ãàìèëüòîíîâûõ öèêëà: (a,b,e,c,d,f,a) è
(a,b,e,d,f,c,a), ÷òî ëåãêî ïðîâåðèòü íåïîñðåäñòâåííî íà ãðàôå.
     Ìåòîä ïîñëåäîâàòåëüíîãî ïåðåáîðà. Â ïðîòèâîïîëîæ-
íîñòü àëãåáðàè÷åñêîìó ìåòîäó, êîãäà îäíîâðåìåííî ôîðìè-
ðóþòñÿ âñå öåïè, ýòîò ìåòîä ïðåäïîëàãàåò èõ ïîñëåäîâàòåëü-
íîå ïîñòðîåíèå. Íà êàæäîì øàãå "íàðàùèâàåòñÿ" òîëüêî îäíà
öåïü ïóòåì äîáàâëåíèÿ äóãè, ñâÿçûâàþùåé åå ïîñëåäíþþ âåð-
øèíó ñ îäíîé èç ñìåæíûõ, åùå íå âêëþ÷åííûõ â öåïü. Î÷åâèä-



                                                  119

Страницы