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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
2
, v
5
, v
1
, v
4
, v
6
, v
3
, v
2
),
L
11
=104.
H
Hj
(v
6
, v
3
)
(v
4
, v
6
)
(v
2
, v
1
).
@
@R
±°
²¯
Q
Q
Q
Q
L
0
=81
±°
²¯
Q
Q
Q
Q
L
1
=81
±°
²¯
`
`
`
`
`
`
`
`
`
`
`
`
L
3
=81
±°
²¯
Q
Q
Q
Q
L
5
=84
±°
²¯
L
7
=104
(1; 4)(4; 6)(6; 3)(3; 5)(5; 2)(2; 1)
±°
²¯
6;3 L
2
=129
±°
²¯
4;6 L
4
=113
±°
²¯
1;4 L
8
=112
L
6
=101
±°
²¯
Q
Q
Q
Q
2;1
±°
²¯
Q
Q
Q
Q
L
9
=103
±°
²¯
L
11
=104
(1; 4)(4; 6)(6; 3)(3; 2)(2; 5)(5; 1)
±°
²¯
5;1 L
10
=127
±°
²¯
1;4 L
12
=114
öåïü â ãàìèëüòîíîâ öèêë (v2 , v5 , v1 , v4 , v6 , v3 , v2 ), äëèíà ïîñëåä-
íåãî ðàâíà L11 =104.
   Áèíàðíîå äåðåâî, îòðàæàþùåå âñå âûïîëíÿâøèåñÿ ðàçáèå-
íèÿ ìíîæåñòâà ãàìèëüòîíîâûõ öèêëîâ ðàññìàòðèâàåìîãî ãðà-
ôà, èçîáðàæåíî íà ðèñ. 5.25. Äâå êîíöåâûå âåðøèíû äåðåâà,
         Âñå ãàìèëüòîíîâû öèêëû
                  Hj²¯
                   H
              L0 =81
                       ±°
                           Q
                       ²¯     Q ²¯
                                 Q                   Ãàìèëüòîíîâû öèêëû,
              L1 =81 6;3             6;3 L2 =129
                       ±° ±°                         ñîäåðæàùèå äóãè (v6 , v3 ) è
                           Q
                       ²¯     Q ²¯                   (v4 , v6 ) , íî íå ñîäåðæàùèå
                                 Q
              L3 =81 4;6             4;6 L4 =113     äóãó (v2 , v1 ).
                       ±°  ```±°
                                     ```
                                             ``` @@    R    L6 =101
                       ²¯                           ``  `²¯
              L5 =84 2;1                                    2;1
                       ±°                                  ±°
                           Q                                    Q
                       ²¯ Q²¯ Q                            ²¯      Q ²¯
                                                                     Q
             L7 =104 1;4             1;4 L8 =112 L9 =103 5;1            5;1 L10 =127
                       ±° ±°                               ±° ±°
       z                }|                {
                                                                Q
                                                           ²¯      Q ²¯
       (1; 4)(4; 6)(6; 3)(3; 5)(5; 2)(2; 1)                          Q
                                                 L11 =104 1;4           1;4 L12 =114
                                                           ±° ±°
                                          z                }|                {
                                          (1; 4)(4; 6)(6; 3)(3; 2)(2; 5)(5; 1)

                  Êðàò÷àéøèå ãàìèëüòîíîâû öèêëû

                                  Ðèñ. 5.25
èìåþùèå íàèìåíüøåå çíà÷åíèå íèæíåé ãðàíèöû, îïðåäåëÿþò
îïòèìàëüíîå ðåøåíèå çàäà÷è.  äàííîì ãðàôå ñóùåñòâóþò äâà
êðàò÷àéøèõ ãàìèëüòîíîâûõ öèêëà, äëèíà êîòîðûõ ðàâíà 104.




                                        138

Страницы