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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
(60)
s
(79)
s
(93)
s
(45)
s
(32)
s
(19)
s
(44)
s
(21)
s
(21)
s
(5)
s
(14)
s
(10)
s
(0)
-
-
-
-
-
-
@
@
@
@I
@
@
@
@I
@
@
@
@I
¾
¾
¾
666
¾
¾
¾
¡
¡
¡
¡µ
¡
¡
¡
¡µ
¡
¡
¡
¡µ
-
6
@
@
@
@I
-
6
6
@
@
@
@I
6
-
6
6
¢
¢
¢
¢
¢
¢
¢
¢¸
¡
¡
¡
¡µ
@
@
@
@I
6
¾
z }| {
l(v
j
)= max
v
i
∈Γ
−
(v
j
)
[l(v
i
)+c
i,j
], j=2, 13
z }| {
v
1
−v
2
−v
6
−v
8
−v
9
−v
11
−v
12
−v
13
l(v
13
) =
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
1
5
∗
10
∗
19 7
v
2
14
∗
16
∗
9
∗
8
v
3
11
∗
26 30
v
4
18 21
v
5
3
v
6
11
∗
v
7
30
∗
v
8
13
∗
17
v
9
15
∗
v
10
8
v
11
19
∗
12
v
12
14
∗
v
13
âûïîëíåíèÿ ïðîåêòà ðàâíî ñàìîìó äëèííîìó ïóòè ìåæäó íà-
÷àëüíîé è êîíå÷íîé âåðøèíàìè. Ýòîò ïóòü íàçûâàþò êðèòè-
÷åñêèì. Ìåòîä îòûñêàíèÿ òàêîãî ïóòè òîò æå, ÷òî è â çàäà÷å
                              12
                               -
            (60)
              s              -(79)
                               s               -(93)
                                                 s
             6 @
               I        19       6@
                                  I      14      6
                @ 15              17@ 21          8
                  @                  @
                     @(45)s¾     s(32) @(19)
                                          s    - s(44)
                             13 6         6 18 6
  à            30     ¢¢̧ 63
                                  @
                                  I
                                  11@ 8 14        30
                    ¢                @
                 26¢ s(21)        (21) @s(5) - s(14)
                                 s¾
                  ¢ ¡
                    µ@     I     6 16¡¡µ     9
                 ¢ ¡11 @ 19 7          5
                ¢¡           @      ¡
             ¢¡
              s¾        10     @¡s
            (10)                (0)
        v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11               v12 v13
    v1   0 5∗ 10∗           19 7
                         ∗
    v2        5       14        16∗ 9∗ 8
    v3            10        11∗             26     30
    v4                 19                      18        21
    v5                      21               3
                                          ∗
    v6                          21     11
  á v7          Îñíîâíîå            14         30∗
    v8          ðàñ÷åòíîå              32 13∗            17
              ñîîòíîøåíèå
    v9  z            }|            {        45     15∗
    v10 l(vj ) = max [l(vi )+ci,j ], j=2, 13 44            8
               vi ∈Γ− (vj )                                ∗
    v11                                            60 19 12
    v12 z         Êðèòè÷åñêèé ïóòü                     79 14∗
                        }|              {
    v13 v1 −v2 −v6 −v8 −v9 −v11 −v12 −v13       l(v13 ) = 93

                           Ðèñ. 4.15
î êðàò÷àéøåì ïóòè, òîëüêî â îñíîâíîì ðàñ÷åòíîì ñîîòíîøå-
íèè âìåñòî ìèíèìóìà èùåòñÿ ìàêñèìóì. Íà ðèñ. 4.15,à,á ïðè-
âåäåíî ðåøåíèå çàäà÷è î êðèòè÷åñêîì ïóòè äëÿ ðàññìàòðèâà-
åìîãî ãðàôà. Êðèòè÷åñêèé ïóòü âûäåëåí æèðíûìè ëèíèÿìè.


                                     97

Страницы