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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

S(v
2
, v
1
)
v
1
v
2
v
4
v
5
v
1
∞ 0 2 30
v
2
∞ ∞ 30 17
v
3
29 1 ∞ 0
v
5
3 21 0 ∞
L
6
=L
3
+∆=101
v
1
v
2
v
4
v
5
α
i
A
v
1
∞ 0 2 30 0 2
v
2
∞ ∞ 13 0 17 13
v
3
26 1 ∞ 0 0 1
¡
¡ª
@
@R
-
v
5
21 0 ∞ 0 0
β
j
3 0 0 0 20
B 26 1 2 0 26
S(v
5
, v
1
) S(v
5
, v
1
)
v
2
v
4
v
5
v
1
0 2
30
∞
v
2
∞ 13 0
v
3
1 ∞ 0
L
9
=L
6
+∆=103
v
2
v
4
v
5
α
i
A
v
1
0 ∞ 0 0
v
2
∞ 11 0 0 11
¡
¡ª
@
@R
-
v
3
1 ∞ 0 0 1
β
j
0 2 0 2
B 1 11 0 11
v
1
v
2
v
4
v
5
v
1
∞ 0 2 30
v
2
∞ ∞ 13 0
v
3
26 1 ∞ 0
v
5
∞ 21 0 ∞
L
10
=L
6
+φ
5,1
=127
S(v
1
, v
4
) S(v
1
, v
4
)
v
2
v
5
v
2
∞ 0
v
3
1
0
∞
L
11
=L
9
+∆=104
v
2
v
5
α
i
A
v
2
∞ 0 ∞
-
v
3
0 ∞ 1 ∞
β
j
0 0 1
B ∞ ∞ ∞
v
2
v
4
v
5
v
1
0 ∞ ∞
v
2
∞ 11 0
v
3
1 ∞ 0
L
12
=L
9
+φ
1,4
=114
S(v
2
, v
1
),
S(v
1
, v
4
)
L
11
=104, (v
6
, v
3
), (v
4
, v
6
), (v
5
, v
1
),
(v
1
, v
4
), (v
5
, v
1
, v
4
, v
6
,
v
3
). S(v
1
, v
4
)
(v
2
, v
5
) (v
3
, v
2
),
          S(v2 , v1 )
          v1    v2   v4   v5         v1   v2   v4   v5   αi   A
     v1   ∞      0    2   30      v1 ∞     0    2   30    0    2
     v2   ∞     ∞    30   17      v2 ∞    ∞    13    0   17   13
     v3   29     1   ∞     0    - v3 26    1   ∞     0    0    1
     v5    3    21    0   ∞       v5 0    21    0   ∞     0    0
                                  βj 3     0    0    0   20
    L6 =L3 +∆=101                 B 26     1    2    0        26

              S(v5 , v1 )       ¡                                  @         S(v5 , v1 )
                               ¡
                               ª                                    @
                                                                    R
              v2   v4 v5             v2 v4 v5 αi A                           v1 v2 v4      v5
         v1   0     2 30
                      ∞  v1          0     0   ∞     0 0                v1   ∞ 0 2         30
         v2   ∞    13 0- v2          ∞    11   0     0 11               v2   ∞ ∞ 13        0
         v3   1    ∞ 0   v3          1    ∞    0     0 1                v3   26 1 ∞        0
                         βj          0     2   0     2                  v5   ∞ 21 0        ∞
         L9 =L6 +∆=103
                         B           1    11   0       11
                                                                        L10 =L6 +φ5,1 =127

                               ¡¡                                  @
            S(v1 , v4 )        ª                                   @R S(v1 , v4 )
             v2 v5                   v2 v5 αi A                         v2 v4 v5
          v2 ∞ 0       - v2          ∞    0 0 ∞                      v1 0 ∞ ∞
                   0
          v3 1 ∞         v3          0    ∞ 1 ∞                      v2 ∞ 11 0
                         βj          0    0 1                        v3 1 ∞ 0
          L11 =L9 +∆=104
                         B           ∞    ∞   ∞
                                                                     L12 =L9 +φ1,4 =114

                                    Ðèñ. 5.24

íèÿ, íà÷èíàÿ ñ ìíîæåñòâà S(v2 , v1 ), êàê ïîêàçàíî íà ðèñ. 5.24.
Ðåçóëüòàòû ïðîäåëàííûõ îïåðàöèé ñâèäåòåëüñòâóþò î íàëè-
÷èè ìíîæåñòâà ãàìèëüòîíîâûõ öèêëîâ28 S(v1 , v4 ) ñ íèæíåé
ãðàíèöåé L11 =104, âêëþ÷àþùèõ äóãè (v6 , v3 ), (v4 , v6 ), (v5 , v1 ),
(v1 , v4 ), êîòîðûå â ñîâîêóïíîñòè îáðàçóþò îðöåïü (v5 , v1 , v4 , v6 ,
v3 ). Ïîñêîëüêó ðåäóöèðîâàííàÿ ìàòðèöà äëÿ S(v1 , v4 ) ñîäåð-
æèò äâå "íóëåâûõ" äóãè (v2 , v5 ) è (v3 , v2 ), çàìûêàþùèõ ýòó
  28    äàííîì ñëó÷àå ýòî ìíîæåñòâî ñîñòîèò ëèøü èç îäíîãî öèêëà.



                                          137

Страницы