Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети — различия между версиями
(Новая страница: «{{Лемма |about= об эквивалентности свойства потока быть минимальной стоимости и отсутствии о…») |
|||
| Строка 6: | Строка 6: | ||
* <math> f </math> - поток минимальной стоимости. | * <math> f </math> - поток минимальной стоимости. | ||
* В остаточной сети <math> G_f </math> нет циклов отрицательного веса. | * В остаточной сети <math> G_f </math> нет циклов отрицательного веса. | ||
| − | |proof= | + | |proof= |
| + | *<math>\Rightarrow </math> | ||
| + | От противного. Пусть существует <math> C </math> {{---}} цикл отрицательного веса в <math> G_f </math>, | ||
| + | <math> c_m </math> {{---}} наименьшая остаточная пропускная способность среди рёбер <math> C </math>. | ||
| + | Пустим по <math> C </math> поток <math> f_+ = c_m </math>. | ||
| + | Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <math> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</math> | ||
| + | |||
| + | <math>\Rightarrow </math> <math>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</math> <math>\Rightarrow f </math> {{---}} не минимальный. Противоречие. | ||
}} | }} | ||
Версия 01:10, 16 января 2011
| Лемма (об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети): |
Следующие два утверждения эквивалентны:
|
| Доказательство: |
|
От противного. Пусть существует — цикл отрицательного веса в , — наименьшая остаточная пропускная способность среди рёбер . Пустим по поток . Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то — не минимальный. Противоречие. |
