693
правки
Изменения
→См. также
Attention!
Можно привести доказательство теоремы об обратной функции для дзета-функции Римана <!---лол, это была не я. (МК)//узковат кругозор у Вас, мужик, неприятненько было убирать за Вами :с --->
==Свойства производящих функций Дирихле== <!-------xz как назвать, потом придумаю)))------->
{{Теорема
|statement =
Функция Мёбиуса имеет вид:
<tex>M(s) = \dfrac{1}{\zeta(s)} = \sum_{k=1}^{\infty} \dfrac{\mu_n}{n^s}</tex>, где
<tex>\mu_n = \begin{cases}
(-1)^t_n \\
0
\end{cases}</tex> <!------ !!! how to make po-russki ??? ----->
|proof =
Для доказательства покажем, что перед каждой проверкой условия в цикле while <tex> f </tex> является предпотоком.
Перед началом цикла, после завершения операции <tex> \mathrm{initializePreflow}</tex>, <tex> f </tex> является предпотоком.
Внутри цикла выполняются лишь операции проталкивания и подъёма. Операция подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъёма не зависит, будет ли <tex> f </tex> предпотоком. Операция <tex> \mathrm{push}</tex><tex>(u, v)</tex> применяется, если <tex> e(u) > 0 </tex>, увеличивая поток через ребро <tex> (u, v) </tex> на величину, не превышающую избыточный поток вершины <tex> u </tex> и остаточную пропускную способность ребра <tex> (u, v) </tex>. Следовательно, если перед выполнением операции проталкивания <tex> f </tex> являлся предпотоком, то и после выполнения проталкивания <tex> f </tex> останется предпотоком.
После завершения алгоритма для каждой вершины <tex> u \in V \setminus \{s, t\} </tex> справедливо, что <tex> e(u) = 0 </tex>, что следует непосредственно из [[#Лемма1|леммы (<tex>1</tex>)]], [[#Лемма2|леммы (<tex>2</tex>)]] и того, что перед выполнением операций проталкивания или подъёма <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.
Поскольку из [[#Лемма1|леммы (<tex>1</tex>)]] следует, что <tex> h </tex> является функцией высоты и после завершения алгоритма, то по [[#Лемма3|лемме (<tex>3</tex>)]] в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>. Но тогда по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] <tex> f </tex> {{---}} максимальный поток.
}}
==См. также==
