Изменения

Перейти к: навигация, поиск

Разрез, лемма о потоке через разрез

523 байта добавлено, 11:35, 21 декабря 2010
Поток через разрез
Пусть <tex><S,T></tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
|proof =
скоро появится<tex>f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(S\setminus s,V)+f(s,V)=f(s,V)=|f|</tex> 1-е равенство выполняется, так как суммы не пересекаются (<tex>f(S,V)=f(S,S)+f(S,T)</tex>); 2-е равенство выполняется из-за антисимметричности (<tex>f(S,S)=-f(S,S)=0</tex>); 3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм; 4-е равенство выполняется из-за сохранения потока.
}}
141
правка

Навигация