Изменения

Перейти к: навигация, поиск
Доказательство второй леммы
Пусть <tex> N </tex> {{---}} сеть, а <tex>f</tex> {{---}} допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>G_f</tex> равен общему потенциалу <tex>N</tex>.
|proof=
Пусть По [[Теорема_о_декомпозиции | теореме о декомпозиции]] поток можно разбить на множество простых путей из <tex>c_fs</tex> {{---}} функция пропускных способностей в <tex>G_ft</tex>, а <tex>p_f(v), in_fи циклов. Рассмотрим каждый путь (vцикл)и убедимся, out_f(v)</tex> {{---}} потенциалчто, множество входящих ребер и множество выходящих ребер вершины пуская по нему поток <tex>v</tex> из <tex>G_ff_i</tex>, потенциал вершины не изменится.  Достаточно доказатьДействительно, рассмотрим вершину v, что поток <tex>p_f(v) = p(v)f_i</tex>. Ребру в нее течет по ребру <tex>euv</tex> , а из нее по ребру <tex>in(v)vw</tex> соответствуют ребро . Пусть <tex>e_1c_{f_i}</tex> из {{---}} функция пропускных способностей в остаточной сети после пропускания потока по <tex>in_f(v)i</tex> с пропускной способностью <tex>c(e) - fому пути (eциклу). Рассмотрим </tex>, и ребро <tex>e_2</tex> из <tex>outc^+_{f_1}(v)</tex> с пропускной способностью <tex>f= c_{f_1}(euv)</tex>. Аналогично, ребру <tex>e</tex> из <tex>out+ c_{f_1}(vwv)</tex> соответствуют ребра из . <tex>out_fc_{f_1}(vuv)</tex> с пропускной способностью <tex>= c(vuv) - f (v)f_i</tex> и , а <tex>in_fc_{f_1}(vwv)</tex> с пропускной способностью <tex>f= c(ewv)+ f_i</tex>. Используя закон сохранения потока, нетрудно проверитьсложив эти два значения, получим, что <tex>\displaystyle\sum_{e\in in_fc^+(v)} c_f(e) = \sum_{e\in in(v)}c(e)</tex> и остается неизменной. Применив такое же рассуждение для <tex>\displaystyle\sum_{e\in out_fc^-(v)} c_f(e) = \sum_{e\in out(v)}c(e)</tex> , получим, что и требовалось доказатьпотенциал каждой вершины остается неизменным.
}}
{{Теорема
50
правок

Навигация