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

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

10
называют пропускной способностью разреза
-
U
А
.
Например для сети на рисунке 4 с(
-
U
А
)=8+2+5+6+9+5+8+8=51.
Насыщенные дуги.
Дугу u
∈
U называют насыщенной, если
ϕ
(u)=c(u).
Пример потока в сети дан на рисунке 5, на котором первое число, постав-
ленное в соответствие каждой дуге – ее пропускная способность, а второе – по-
ток по дуге. Жирными линиями выделены насыщенные дуги, т.е. те, поток по
которым равен их пропускной способности. Поток в этой сети не является мак-
симальным.
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)
Рисунок 4
1
2
3
4
5
6
И
с-
Сток
4,4
5,1
2,2
1,1
4,1
3,3
2,2
6,3
Рисунок 5
называют пропускной способностью разреза U -А .

       Например для сети на рисунке 4 с( U -А )=8+2+5+6+9+5+8+8=51.




                                                               (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

                                                             Рисунок 4
       Насыщенные дуги. Дугу u∈U называют насыщенной, если ϕ(u)=c(u).

       Пример потока в сети дан на рисунке 5, на котором первое число, постав-
ленное в соответствие каждой дуге – ее пропускная способность, а второе – по-
ток по дуге. Жирными линиями выделены насыщенные дуги, т.е. те, поток по
которым равен их пропускной способности. Поток в этой сети не является мак-
симальным.

                                                                     1,1                          4
                                             2

                                                                                                                      2,2
                   4,4
                                                                          4,1
         Ис-                                     2,2
            1
                                                                                                                                  6
                                                                                                                                        Сток

                    5,1                                                                                               6,3
                                             3                                                        5
                                                                      3,3

                                                             Рисунок 5
                                                                    10

Страницы