Графы и сети. Харитонова Е.В. - 39 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

38
()
(
)
(
)
(
)()
z cdе b a
6 9,3 5,4 4,3 5,6 8,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
видим: если увеличить поток на 2 для стрелок, имеющих то же самое направле-
ние, что и цепь, и уменьшить поток на 2 для стрелок, имеющих противополож-
ное направление, то получим
()
(
)
(
)
(
)()
z, c d е b a
8 9,5 5,2 4,5 5,8 8,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что увеличивает поток на 2. Первый вопрос, который следовало бы задать:
«Почему выбираем 2?». Видно очевидно, что поток желательно увеличить как
можно больше. Но он не может превысить пропускную способность ни одного
из заданных ребер. Именно по этой причине мы ограничены величиной 2. Кро-
ме того, если ребро имеет направление, противоположное цепи, то
нельзя
уменьшить поток через это ребро более, чем на текущую величину потока через
него, иначе получим отрицательный поток. Поэтому, если бы не было других
ограничений, то
(
)
dе
4 4,
⎯
⎯
⎯
←
ограничило бы изменение потока до 4. Второй вопрос: «Как это влияет на со-
хранение потока?». Убедимся, что условие сохранения потока выполняется.
Рассмотрим, например, изменение
(
)
(
)
еb a
3 5,6 8,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
на
(
)
(
)
e.b а
5 5,8 8,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Поток выходящий из вершины b, увеличен на ту же самую величину, что и по-
ток, входящий в вершину
b. Поэтому чистый поток через b остается прежним.
При изменении
(
)
(
)
dе b
4 4,3 5,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
на
(
)
(
)
dе b
2 4,5 5,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
поток из вершины b в вершину e увеличен на ту же величину, на которую
уменьшен поток из вершины
d в вершину е, поэтому чистый поток в вершине е
остался тем же. Наконец, рассмотрим изменение

Страницы