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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

φ
6,3
(v
6
, v
3
).
S(v
6
, v
3
) S(v
6
, v
3
)
v
1
v
2
v
4
v
5
v
6
v
1
∞ 0 2 30 6
v
2
0 ∞ 30 17 12
v
3
29 1 12 0
12
∞
v
4
32 83 ∞ 49 0
v
5
3 21 0 ∞ 0
L
1
=L
0
+∆=81
v
1
v
2
v
4
v
5
v
6
α
i
A
j
v
1
∞ 0 2 30 6 0 2
v
2
0 ∞ 30 17 12 0 12
v
3
29 1 12 0 ∞ 0 1
v
4
32 83 ∞ 49 0 32
v
5
3 21 0 ∞ 0 0 0
β
j
0 0 0 0 0 0
B
j
3 1 2 17 0 32
v
1
v
2
v
3
v
4
v
5
v
6
v
1
∞ 0 75 2 30 6
v
2
0 ∞ 58 30 17 12
v
3
29 1 ∞ 12 0 12
v
4
32 83 58 ∞ 49 0
v
5
3 21 48 0 ∞ 0
v
6
0 85 ∞ 35 89 ∞
L
2
=L
0
+φ
6,3
=129
L
1
S(v
6
, v
3
),
∆=
P
α
i
+
P
β
j
=0
S(v
6
, v
3
)
S(v
6
, v
3
)
φ
4,6
=32
(v
4
, v
6
). S(v
6
, v
3
)
S(v
4
, v
6
)
(v
4
, v
6
), S(v
4
, v
6
)
v
4
v
6
(v
4
, v
6
),
(v
4
, v
6
, v
3
).
ñ íàéäåííîé íèæíåé ãðàíèöåé äëèíû âñåõ öèêëîâ âîçðàñòàåò
íà âåëè÷èíó φ6,3 êàê "ïëàòà" çà íåèñïîëüçîâàíèå äóãè (v6 , v3 ).

           S(v6 , v3 )                                                             S(v6 , v3 )
      v1   v2   v4   v5   v6        v1   v2   v4   v5   v6   αi   Aj         v1   v2   v3   v4   v5   v6
v1    ∞     0    2   30   6    v1   ∞     0    2   30    6   0     2   v1    ∞     0   75    2   30   6
v2     0   ∞    30   17   12   v2    0   ∞    30   17   12   0    12   v2     0   ∞    58   30   17   12
                          12
v3    29    1   12    0   ∞    v3   29    1   12    0   ∞    0     1   v3    29    1   ∞    12    0   12
v4    32   83   ∞    49   0    v4   32   83   ∞    49    0   0    32   v4    32   83   58   ∞    49   0
v5     3   21    0   ∞    0    v5    3   21    0   ∞     0   0     0   v5     3   21   48    0   ∞    0
                               βj    0    0    0    0    0   0         v6     0   85   ∞    35   89   ∞
     L1 =L0 +∆=81
                               Bj    3    1    2   17    0        32
                                                                            L2 =L0 +φ6,3 =129
                à                                  á                                    â
                                         Ðèñ. 5.20
    ×òîáû îïðåäåëèòü L1  íèæíþþ ãðàíèöó äëèíû öèêëîâ
ïîäìíîæåñòâà S(v6 , v3 ), íåîáõîäèìî ïðîâåñòè ðåäóêöèþ ìàò-
ðèöû, ïðåäñòàâëåííîé íà ðèñ. 5.20,à. Ëþáàÿ ñòðîêà è ñòîë-
áåö ýòîé ìàòðèöû ñîäåðæàò íóëåâîå çíà÷åíèå, ñëåäîâàòåëüíî,
ðåäóöèðîâàííàÿ
      P     P     ìàòðèöà èäåíòè÷íà èñõîäíîé.  ýòîì ñëó÷àå
∆= αi + βj =0 (ñì. ðèñ. 5.20,á ). Ïîýòîìó íèæíÿÿ ãðàíèöà
äëÿ ïîäìíîæåñòâà S(v6 , v3 ) ñîâïàäàåò ñ ðàíåå íàéäåííîé íèæ-
íåé ãðàíèöåé äëÿ âñåãî ìíîæåñòâà ãàìèëüòîíîâûõ öèêëîâ,
ò. å. ðàâíà 81. Ñðàâíèâàÿ íèæíèå ãðàíèöû îáîèõ ïîäìíîæåñòâ,
óáåæäàåìñÿ, ÷òî äëÿ S(v6 , v3 ) îíà íèæå. Çíà÷èò, ðàçáèåíèþ
ïîäëåæèò èìåííî ýòî ïîäìíîæåñòâî. Ðåçóëüòàòû ïîèñêà äó-
ãè, ïî êîòîðîé ñëåäóåò ïðîèçâîäèòü ðàçáèåíèå, ïðåäñòàâëåíû
íà ðèñ. 5.20,á. Ìàêñèìàëüíîå çíà÷åíèå øòðàôà φ4,6 =32 óêà-
çûâàåò íà äóãó (v4 , v6 ). Ïîýòîìó ðàçáèâàåì S(v6 , v3 ) íà äâà
ïîäìíîæåñòâà, îäíî èç êîòîðûõ  S(v4 , v6 ) ñîñòîèò èç öèê-
ëîâ, ñîäåðæàùèõ äóãó (v4 , v6 ), öèêëû äðóãîãî  S(v4 , v6 ) ýòîé
äóãè íå ñîäåðæàò. Íàçâàííûì ïîäìíîæåñòâàì ñîîòâåòñòâóþò
ìàòðèöû íà ðèñ. 5.21,à,â. Ïåðâàÿ ïîëó÷àåòñÿ, åñëè óäàëèòü
ñòðîêó v4 è ñòîëáåö v6 ìàòðèöû íà ðèñ. 5.20. Ýòî ñîîòâåò-
ñòâóåò âêëþ÷åíèþ â öèêë äóãè (v4 , v6 ), â ðåçóëüòàòå ÷åãî ôîð-
ìèðóåòñÿ îðöåïü (v4 , v6 , v3 ). ×òîáû íå äîïóñòèòü îáðàçîâàíèÿ



                                               133

Страницы