Алгоритмы на графах и их приложения. Дорофеева В.И. - 9 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

9
где
-
x
U
i
– множество дуг, заходящих в Х
i
;
+
i
x
U
– множество дуг, исходящих из Х
i
,
3. (∀u∈U)ϕ(u)≤0,
Поток уподобляется количеству вещества, протекающему по дуге.
В силу условия 2 из определения потока имеем
).((u) и (u)
N
0
N
0
xx
x
Uu
x
x
Uu
x
ii
ϕϕϕϕϕϕ
=⇒
==
∑∑
−
∈
+
∈
Разрез. Для подмножества А ⊂ Е такого, что Х
0
∉А, а Х
N
∈А, разрезом се-
ти G=(E,U) называют множество
-
U
А
дуг, заходящих в А.
Пропускная способность разреза. Число
с(
-
U
А
)=
∑
−
∈
А
Uu
с(u)
1
2
5
3
6
9
4
10
8
7
11
(5)
(3)
(11)
(8)
(3)
(2)
(4)
(7)
(9)
(3)
(5)
(5)
(8)
(8)
(4)
(4)
(0)
(6)
(8)
(5)
(9)
(2)
(1)
(4)
(6)
Рисунок 3 
      где U -x – множество дуг, заходящих в Хi;
              i

             +
         U      – множество дуг, исходящих из Хi,
             xi

      3. (∀u∈U)ϕ(u)≤0,
      Поток уподобляется количеству вещества, протекающему по дуге.

                                                    (9)                        5
                                2
                                                               (5)
                                              (7)                                                    (3)
          (5)                                                            (5)             (8)
                  (3)           (2)    (4)                 6
                                                                               (4)
          (11)                                                                                         (8)
  1                     3                                                                                          11
                                                                (0)                        9

                                             7                                     (6)
                 (8)
                                                                         (8)                   (4)           (4)
         (3)                                         (9)
                            4               (2)                (5)                         10


                                      (1)                                          (6)
                                                           8

                                                  Рисунок 3
      В силу условия 2 из определения потока имеем
                                                    
                                                    
                                                    
                  ϕ x 0 = ∑ ϕ (u) и ϕ x N = ∑ ϕ (u)  ⇒ (ϕ x 0 = ϕ x N ).
                 
                         u∈U +             u∈U −    
                                                     
                             x i               x i  


      Разрез. Для подмножества А ⊂ Е такого, что Х0∉А, а ХN∈А, разрезом се-

ти G=(E,U) называют множество U -А дуг, заходящих в А.

      Пропускная способность разреза. Число

                                        с( U -А )=         ∑ с(u)
                                                      u∈U −
                                                          А


                                                                     9

Страницы