Алгоритм Эдмондса-Карпа - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:38Z

rollbackEdits.php mass rollback

103.251.167.21 в 05:03, 1 сентября 2022

2022-09-01T05:03:24Z

93.175.2.31: Отмена правки 64925, сделанной 93.175.2.31 (обсуждение)

2018-04-15T18:40:41Z

Отмена правки 64925, сделанной 93.175.2.31 (обсуждение)

93.175.2.31: /* Сложность */

2018-04-15T18:36:20Z

‎Сложность

I am dark black: /* См. также */

2018-03-17T17:17:56Z

‎См. также

I am dark black: /* См. также */

2018-03-17T17:17:23Z

‎См. также

I am dark black в 15:15, 4 марта 2018

2018-03-04T15:15:33Z

I am dark black в 15:13, 4 марта 2018

2018-03-04T15:13:26Z

I am dark black: /* Пример графа на котором алгоритм дает плохую асимптотику */

2018-03-04T15:10:25Z

‎Пример графа на котором алгоритм дает плохую асимптотику

I am dark black: /* Пример графа на котором алгоритм дает плохую асимптотику */

2018-03-04T15:04:03Z

‎Пример графа на котором алгоритм дает плохую асимптотику

← Предыдущая		Версия 16:25, 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 Майкл Наки].
−	\|}
−
	== Алгоритм ==		== Алгоритм ==

← Предыдущая		Версия 05:03, 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 Майкл Наки].
		+	\|}
		+
	== Алгоритм ==		== Алгоритм ==

@@ Строка 12: / Строка 12: @@
 ## Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
 # Возвращаемся на шаг 2.
 == Псевдокод ==

@@ Строка 12: / Строка 12: @@
 ## Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
 # Возвращаемся на шаг 2.
 == Псевдокод ==

@@ Строка 117: / Строка 117: @@
 == См. также ==
 *[[Обход в ширину]]
 *[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]

← Предыдущая		Версия 17:17, 17 марта 2018
Строка 117:		Строка 117:

	== См. также ==		== См. также ==
		+	*[[Обход в ширину]]
		+	*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину\|Алгоритм Форда-Фалкерсона]]
		+
	==Примечания==		==Примечания==

← Предыдущая		Версия 15:15, 4 марта 2018
Строка 116:		Строка 116:


		+	== См. также ==
	==Примечания==		==Примечания==

@@ Строка 86: / Строка 86: @@
 [[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
 [[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
 ==Примечания==

@@ Строка 65: / Строка 65: @@
 Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.
-== Пример графа на котором алгоритм дает плохую асимптотику ==
+== Пример графа, на котором алгоритм дает плохую асимптотику ==
 [[Файл:MaxFlowWorstCase.png|365px|thumb|right|«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]]

@@ Строка 83: / Строка 83: @@
 Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
-[[Файл:InGraph.png|600px|thumb|left| Изначальный граф, нулевой поток]]
+[[Файл:InGraph.png|300px|thumb|left| Изначальный граф, нулевой поток]]
-[[Файл:SecondStage.png|600px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
+[[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
-[[Файл:ThirdStageEdmunds karp.png|600px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
+[[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
 ==Примечания==