Теорема Форда-Фалкерсона - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:12:45Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:58, 1 сентября 2022

2022-09-01T05:58:21Z

Lytr777: правки

2016-01-23T11:22:41Z

правки

Lytr777: правки

2016-01-15T07:29:27Z

правки

192.168.0.2 в 20:48, 25 сентября 2011

2011-09-25T20:48:15Z

Niyaz.nigmatullin в 07:49, 22 декабря 2010

2010-12-22T07:49:25Z

Niyaz.nigmatullin в 07:47, 22 декабря 2010

2010-12-22T07:47:32Z

Niyaz.nigmatullin в 07:45, 22 декабря 2010

2010-12-22T07:45:07Z

Niyaz.nigmatullin в 07:42, 22 декабря 2010

2010-12-22T07:42:54Z

Niyaz.nigmatullin в 20:15, 21 декабря 2010

2010-12-21T20:15:25Z

← Предыдущая		Версия 16:12, 4 сентября 2022
Строка 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=

← Предыдущая		Версия 05:58, 1 сентября 2022
Строка 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=

@@ Строка 2: / Строка 2: @@
 |statement=
 Если <tex> f </tex> {{---}} некоторый [[Определение_сети,_потока|поток]] в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
-# Поток <tex> f </tex> максимален
+# Поток <tex> f </tex> максимален.
-# В <tex> G_f </tex> не существует пути <tex>s \leadsto t</tex>
+# В <tex> G_f </tex> не существует пути <tex>s \leadsto t. </tex>
-# <tex> |f| = c(S, T) </tex> для некоторого разреза <tex> (S, T) </tex> сети <tex> G </tex>
+# <tex> |f| = c(S, T) </tex> для некоторого разреза <tex> (S, T) </tex> сети <tex> G. </tex>
 |proof=
 <tex> (1)\Rightarrow (2)</tex>
@@ Строка 21: / Строка 21: @@
 <tex> (3) \Rightarrow (1) </tex>
-Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \leqslant c(S, T)</tex>, поэтому <tex> f </tex> максимален
+Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \leqslant c(S, T)</tex>, поэтому <tex> f </tex> максимален.
 }}
 == См. также ==
 * [[Определение_сети,_потока|Определение сети, потока]]
 * [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Задача о максимальном потоке ]]

@@ Строка 21: / Строка 21: @@
 <tex> (3) \Rightarrow (1) </tex>
-Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \le c(S, T)</tex>, поэтому <tex> f </tex> максимален
+Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \leqslant c(S, T)</tex>, поэтому <tex> f </tex> максимален
 }}
-== Литература ==
+== Источники информации ==
-* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
+* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е изд. — М.:Издательский дом "Вильямс", 2010. — 1296 C.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 == См. также ==

@@ Строка 1: / Строка 1: @@
 {{Теорема
 |statement=
-Если <tex> f </tex> {{---}} некоторый поток в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
+Если <tex> f </tex> {{---}} некоторый [[Определение_сети,_потока|поток]] в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
 # Поток <tex> f </tex> максимален
 # В <tex> G_f </tex> не существует пути <tex>s \leadsto t</tex>

← Предыдущая		Версия 07:47, 22 декабря 2010
Строка 30:		Строка 30:
	== См. также ==		== См. также ==
	* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину\|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]		* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину\|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
		+
		+	[[Категория: Алгоритмы и структуры данных]]
		+	[[Категория: Задача о максимальном потоке ]]

@@ Строка 15: / Строка 15: @@
 Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.
-Разбиение <tex> \langle S, T \rangle</tex> является разрезом, так как не существует <tex> s \leadsto t</tex>.
+Разбиение <tex> \langle S, T \rangle</tex> является разрезом, так как по <tex> (2) </tex> в <tex> G_f </tex> не существует <tex> s \leadsto t</tex>.
 По [[Разрез,_лемма_о_потоке_через_разрез|лемме о потоке через разрез]] <tex> f(S, T) = |f| </tex>. Также <tex> \forall u \in S, v \in T</tex> известно, что <tex>f(u, v) = c(u, v) </tex>, так как иначе вершина <tex> v </tex>
 должна была бы принадлежать множеству <tex> S </tex>. Поэтому <tex> c(S, T) = f(S, T) = |f| </tex>.

@@ Строка 7: / Строка 7: @@
 |proof=
 <tex> (1)\Rightarrow (2)</tex>
 Докажем от противного. Предположим, что в <tex> G_f </tex> существует какой-нибудь путь <tex>p = s \leadsto t</tex>.
 Тогда рассмотрим <tex> f + f_p </tex>. По [[Лемма_о_сложении_потоков|лемме о сумме потоков]] <tex> f + f_p </tex> тоже является потоком в сети <tex> G </tex>,
@@ Строка 12: / Строка 13: @@
 <tex> (2) \Rightarrow (3) </tex>
 Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.
 Разбиение <tex> S </tex> и <tex> T </tex> является разрезом, так как не существует <tex> s \leadsto t</tex>.
@@ Строка 18: / Строка 20: @@
 <tex> (3) \Rightarrow (1) </tex>
 Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \le c(S, T)</tex>, поэтому <tex> f </tex> максимален
 }}