Циркуляция потока - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:19:07Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:28, 1 сентября 2022

2022-09-01T05:28:35Z

178.70.136.5: убрал багнутый тег

2020-12-10T18:19:10Z

убрал багнутый тег

188.170.77.62: wikitex removal

2020-01-11T17:44:39Z

wikitex removal

Vitalik: /* Решение */ опечатка

2017-04-07T14:44:49Z

‎Решение: опечатка

Дмитрий Мурзин: ё

2017-01-22T17:13:09Z

93.175.2.64: Исправление опечатки

2017-01-22T15:36:30Z

Исправление опечатки

Lehanyich: /* Псевдокод */

2016-01-07T15:26:02Z

‎Псевдокод

Lehanyich в 15:08, 7 января 2016

2016-01-07T15:08:13Z

Shersh: /* Псевдокод */

2016-01-07T14:43:01Z

‎Псевдокод

← Предыдущая		Версия 16:19, 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 Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 05:28, 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 Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 8: / Строка 8: @@
 ==Решение==
-<wikitex>Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим рёбра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
+Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим рёбра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
 [[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]]
@@ Строка 20: / Строка 20: @@
 Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра из истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.
 ==Псевдокод==

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
@@ Строка 7: / Строка 6: @@
 Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все  $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать рёбра с положительной нижней пропускной способностью.
 ==Решение==

@@ Строка 21: / Строка 21: @@
 Значит, этот поток и есть циркуляция.
-Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.
+Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра из истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.
 </wikitex>

@@ Строка 6: / Строка 6: @@
 [[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]
-Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все  $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительной нижней пропускной способностью.
+Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все  $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать рёбра с положительной нижней пропускной способностью.
 </wikitex>
 ==Решение==
-<wikitex>Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим ребра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
+<wikitex>Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим рёбра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
-[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]
+[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]]
-Каждое ребро изначального графа заменяется на три новых. Если по ребру $e_i = (v_{from}, v_{to})$ в исходной сети протекает поток $l_i \leqslant f_i \leqslant c_i$, то в новой сети по ребру $(s, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который вытекает из $v_{from}$ по ребру в $G$, заменяется на поток, который протекает по ребрам $(v_{from}, v_{to})$ и $(v_{from}, t)$ (поскольку сумма их пропускных способностей в полученном графе равна $c_i$). Аналогично, для вершины $v_{to}$ суммарный входящий поток не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами в полученном графе. Заметим, что в сети $G'$ все $l_i = 0$, то есть мы имеем обыкновенную сеть.
+Каждое ребро изначального графа заменяется на три новых. Если по ребру $e_i = (v_{from}, v_{to})$ в исходной сети протекает поток $l_i \leqslant f_i \leqslant c_i$, то в новой сети по ребру $(s, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который вытекает из $v_{from}$ по ребру в $G$, заменяется на поток, который протекает по рёбрам $(v_{from}, v_{to})$ и $(v_{from}, t)$ (поскольку сумма их пропускных способностей в полученном графе равна $c_i$). Аналогично, для вершины $v_{to}$ суммарный входящий поток не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя рёбрами в полученном графе. Заметим, что в сети $G'$ все $l_i = 0$, то есть мы имеем обыкновенную сеть.
-Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:
+Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит рёбра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:
 * $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;
 * В $G': f_i \leqslant c_i - l_i \Rightarrow 0 \leqslant f_i \leqslant c_i - l_i \Rightarrow l_i \leqslant f_i + l_i \leqslant c_i$, что удовлетворяет всем ограничениям.
 Значит, этот поток и есть циркуляция.
-Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.
+Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.
 </wikitex>

@@ Строка 28: / Строка 28: @@
 * <tex>\mathtt{from}</tex> {{---}} вершина начала ребра
 * <tex>\mathtt{to}</tex> {{---}} вершина конца ребра
-* <tex>\mathtt{cap}</tex> {{---}} минимальная пропускная способность ребра
+* <tex>\mathtt{minCap}</tex> {{---}} минимальная пропускная способность ребра
-* <tex>\mathtt{mincap}</tex> {{---}} максимальная пропускная способность ребра
+* <tex>\mathtt{maxCap}</tex> {{---}} максимальная пропускная способность ребра
   '''function''' circulation(<tex>V,E</tex>):
-      <tex>G'= {V,s,t}</tex>                                      <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font>
+      <tex>G'=</tex> (<tex>V \cup s \cup t</tex>, <tex>\varnothing</tex>)                                 <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font>
       '''for''' <tex>e : e\in E</tex>
-          <tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.mincap)
+          <tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.minCap)
-          <tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap - <tex>e</tex>.mincap)
+          <tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.maxCap - <tex>e</tex>.minCap)
-          <tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minсap)
+          <tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minCap)
-          <tex>G' = G' \cup {g,h,k}</tex>
+          <tex>G'=G' \cup </tex>(<tex>\varnothing</tex>, <tex>g \cup h \cup k</tex>)
-      maxFlow = getMaxFlow(<tex>G'</tex>)                         <font color=green>// наибольший поток в графе G'</font>
+      maxFlow = getMaxFlow(<tex>G'</tex>)                             <font color=green>// наибольший поток в графе G'</font>
       '''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>.from <tex>=s</tex>
-          '''if''' <tex>f</tex>(<tex>e</tex>)<tex> < e</tex>.cap                              <font color=green>// если для текущего ребра flow < cap</font>
+          '''if''' <tex>f</tex>(<tex>e</tex>) <tex> < e</tex>.maxCap                              <font color=green>// если для текущего ребра flow < cap</font>
               '''return''' false
       '''return''' true

@@ Строка 26: / Строка 26: @@
 ==Псевдокод==
   '''function''' circulation(<tex>V,E</tex>)
-      <tex>G=\varnothing</tex>                                               <font color=green>// пустой граф, вершины s и t - исток и сток</font>
+      <tex>G=\varnothing</tex>                                              <font color=green>// пустой граф, вершины s и t - исток и сток</font>
       '''for''' <tex>e : e\in E</tex>                                        <font color=green>// конструктор ребра принимает 4 параметра: две инцидентные ребру вершины, величину потока через это ребро и пропускную способность</font>
           <tex>t</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap)