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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

S
0
L
0
G
T,
t
v
1
t
v
2
t
v
3
t
v
4
-
?
]
s
Y
6
^
G
T
±°
²¯
L
0
S
0
H
H
H
H
H
H
±°
²¯
L
1
S
1
(v
1
, v
2
)
@
@
@
±°
²¯
L
3
S
3
(v
3
, v
4
)
A
A
±°
²¯
±°
²¯
L
5
L
6
S
5
(v
2
, v
3
) S
6
(v
2
, v
3
)
C
C
±°
²¯
±°
²¯
L
7
L
8
S
7
S
8
±°
²¯
L
4
S
4
(v
3
, v
4
)
±°
²¯
S
2
(v
1
, v
2
)
L
2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
±°
²¯
±°
²¯
S
9
S
10
L
9
L
10
(v
1
, v
2
).
S
1
(v
1
, v
2
), S
2
L
1
L
2
L
1
<L
2
. S
1
     5.4.2. Ìåòîä âåòâåé è ãðàíèö
     Ïðèíöèï âåòâëåíèÿ. Ðàññìîòðåíèå áóäåì âåñòè ïðèìå-
íèòåëüíî ê îðèåíòèðîâàííûì ãðàôàì. Â ïîëíîì îðãðàôå èìå-
åòñÿ ìíîæåñòâî S0 ãàìèëüòîíîâûõ öèêëîâ ðàçëè÷íîé äëèíû.
Íàñ èíòåðåñóåò öèêë ìèíèìàëüíîé äëèíû. Äëÿ íà÷àëà íàéäåì
íèæíþþ ãðàíèöó ýòîé âåëè÷èíû, ò. å. òàêîå çíà÷åíèå, ìåíüøå
êîòîðîãî äëèíà ãàìèëüòîíîâà öèêëà â çàäàííîì ãðàôå íå ìî-
æåò áûòü íè ïðè êàêèõ îáñòîÿòåëüñòâàõ. Ñîîòâåòñòâóþùóþ
ïðîöåäóðó ðàññìîòðèì ïîçäíåå, à ïîêà ïîëàãàåì, ÷òî îöåí-
êà íèæíåé ãðàíèöû L0 íàéäåíà. Îïèñûâàåìûé äàëåå ïðîöåññ
äëÿ ÷åòûðåõâåðøèííîãî ãðàôà G íà ðèñ. 5.18 ìîæíî ïðåä-
ñòàâèòü â âèäå áèíàðíîãî äåðåâà T, ïðèâåäåííîãî çäåñü æå.
                                                         ²¯
     v1 t    - tv2                                T S0
        Y                                           ±°H
       6      ]                                    L0 HH
                                                
                                        
 G                                  ²¯                           HH ²¯
                                                                        H
     ^ t    s t?         (v1 , v2 ) S1
                                    ±°                                           `
                                                                                 ±°` S2 ` ` `(v1 , v2 )
     v4                                                                        `
              v3                    L1@
                                                                             `
                                                                        ` ` ` L2 ` ` ` ` `
                                                                                              `
                                                                    ` `
                          ²¯             @@²¯                    ``
                                                                ²¯                                `²¯
                                                                                                   `
                (v3 , v4 ) S3                   S4 (v3 , v4 )    S
                                                                 9                         S
                                                                                          10
                       ±°                       ±°              ±°                        ±°
                        L3A                    L4               L9                         L10
                     ²¯
                           A²¯
            (v2 , v3 ) S5 L5    S6 (v2 , v3 )
                  ±° ±°
                    C  L6
                   ²¯
                 ²¯   C
                     S7   S8
                 ±°
                  ±°
                  L7      L8
                                         Ðèñ. 5.18

   Ìûñëåííî ðàçîáúåì ìíîæåñòâî âñåõ öèêëîâ íà äâà íåïå-
ðåñåêàþùèõñÿ ïîäìíîæåñòâà, èñïîëüçóÿ â êà÷åñòâå êðèòåðèÿ
âõîæäåíèå â öèêë íåêîòîðîé äóãè, íàïðèìåð (v1 , v2 ). Ïóñòü
S1  ïîäìíîæåñòâî ãàìèëüòîíîâûõ öèêëîâ, ñîäåðæàùèõ äó-
ãó (v1 , v2 ), à S2  ïîäìíîæåñòâî öèêëîâ, íå ñîäåðæàùèõ ýòó
äóãó. Äëÿ êàæäîãî ïîäìíîæåñòâà íàõîäèì íèæíþþ ãðàíèöó
äëèíû ìèíèìàëüíîãî öèêëà. Ïóñòü ýòî áóäóò L1 è L2 ñî-
îòâåòñòâåííî, ïðè÷åì L1

Страницы