Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | {{Теорема | | {{Теорема |
| | |statement= | | |statement= |
Текущая версия на 19:12, 4 сентября 2022
| Теорема: |
Если [math] f [/math] — некоторый поток в сети [math] G = (V, E) [/math] с источником [math]s[/math] и стоком [math]t[/math], то следующие утверждения эквивалентны:
- Поток [math] f [/math] максимален.
- В [math] G_f [/math] не существует пути [math]s \leadsto t. [/math]
- [math] |f| = c(S, T) [/math] для некоторого разреза [math] (S, T) [/math] сети [math] G. [/math]
|
| Доказательство: |
| [math]\triangleright[/math] |
|
[math] (1)\Rightarrow (2)[/math]
Докажем от противного. Предположим, что в [math] G_f [/math] существует какой-нибудь путь [math]p = s \leadsto t[/math].
Тогда рассмотрим [math] f + f_p [/math]. По лемме о сумме потоков [math] f + f_p [/math] тоже является потоком в сети [math] G [/math],
и причем [math] |f + f_p| = |f| + |f_p| \gt |f| [/math], что приводит нас к противоречию, что [math] f [/math] максимальный поток.
[math] (2) \Rightarrow (3) [/math]
Рассмотрим множество [math] S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace [/math] и [math] T = V \setminus S[/math].
Разбиение [math] \langle S, T \rangle[/math] является разрезом, так как по [math] (2) [/math] в [math] G_f [/math] не существует [math] s \leadsto t[/math].
По лемме о потоке через разрез [math] f(S, T) = |f| [/math]. Также [math] \forall u \in S, v \in T[/math] известно, что [math]f(u, v) = c(u, v) [/math], так как иначе вершина [math] v [/math]
должна была бы принадлежать множеству [math] S [/math]. Поэтому [math] c(S, T) = f(S, T) = |f| [/math].
[math] (3) \Rightarrow (1) [/math]
Так как существует разрез, такой что [math] |f| = c(S, T) [/math], то согласно следствию леммы о слабой двойственности потока и разреза [math] |f| \leqslant c(S, T)[/math], поэтому [math] f [/math] максимален. |
| [math]\triangleleft[/math] |
См. также
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
