276
правок
Изменения
→Корректность
:#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>H</tex> и после <tex>E</tex> отмен граф <tex>H</tex> пуст, что означает, что <tex>f</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon^{*}=0</tex>.
:#Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть <tex>C</tex> {{---}} первый из таких циклов. Для <tex>C</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум <tex>-\varepsilon</tex>, хотя бы одно из ребер <tex>C</tex> обладает неотрицательной приведенной стоимостью, количество ребер в <tex>C</tex> не превышает <tex>V</tex>. Тогда средний вес этого цикла <tex>\mu(C) = \mu^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon</tex>. Тогда непосредственно перед отменой <tex>C</tex>, <tex>-\mu^{*}=\varepsilon^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon</tex> (по [[#lemma3|лемме]]). Поскольку мы [[#lemma4|знаем]], что <tex>\varepsilon^{*}</tex> не увеличивается, доказываемое утверждение верно.}}
{{Определение
|definition='''<tex>\varepsilon</tex>-фиксированным''' (англ. ''<tex>\varepsilon</tex>-fixed'') будем называть ребро, поток через которое неизменен для любых <tex>\varepsilon</tex>-оптимальных потоков в сети.}}
{{Теорема
|id=theorem1
|statement=Пусть поток <tex>f</tex> является <tex>\varepsilon</tex>-оптимальным с функцией потенциалов <tex>\varphi</tex>. Также пусть для некоторого ребра <tex>uv \; \left|p_{\varphi}(uv)\right| \geqslant 2V\varepsilon</tex>. Тогда ребро <tex>uv</tex> <tex>\varepsilon</tex>-фиксировано.
|proof=
:По свойству антисимметричности, достаточно будет доказать теорему для случая <tex>p_{\varphi}(uv) \geqslant 2V\varepsilon</tex>.
:Рассмотрим такой поток <tex>f'</tex>, что <tex>f'(uv) \neq f(uv)</tex>. Поскольку <tex>p_{\varphi}(uv) > \varepsilon</tex>, поток по ребру <tex>uv</tex> должен быть как можно меньше, то есть <tex>-c(uv)</tex>, и тогда раз <tex>f'(uv) \neq f(uv)</tex>, то <tex>f'(uv) > f(uv)</tex>.
:Покажем теперь, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимальный.
:Обозначим за <tex>G_{>}</tex> подграф <tex>G</tex> такой, что <tex>G_{>}=(V, \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим какое-то ребро <tex>uv</tex> в <tex>G_{>}</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, в <tex>G_{>}</tex> должен содержаться простой цикл <tex>C</tex>, проходящий через <tex>uv</tex>. Поскольку все ребра в <tex>C</tex> {{---}} остаточные, стоимость <tex>C</tex> {{---}} как минимум <tex>p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon > V\varepsilon</tex>.
:Теперь рассмотрим цикл <tex>\overline{C}</tex>, который получен из <tex>C</tex> разворотом всех его ребер. Заметим, что <tex>\overline{C}</tex> является циклом в <tex>G_{<}=(V,\{uv \in E \;|\; f'(uv) < f(uv)\})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>-n\varepsilon</tex> и, таким образон, средний вес <tex>\overline{C}</tex> меньше чем <tex>-\varepsilon</tex>. Откуда, по [[#lemma3|лемме]] имеем, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимален.
}}
{{Лемма
