http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=217.66.156.45&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-19T06:43:36ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE%D0%B1_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%B1%D1%8B%D1%82%D1%8C_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_%D0%BE%D1%82%D1%81%D1%83%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B8_%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2_%D0%B2_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B5%D1%82%D0%B8&diff=58989Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети2017-01-06T20:39:59Z<p>217.66.156.45: /* Литература */</p>
<hr />
<div>{{Лемма<br />
|about=<br />
о разности потоков<br />
|statement=<br />
Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки равной величины в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f </tex> и нескольких циклов в остаточной сети <tex> G_f </tex>, т.е. <tex>g = f + \sum_{i} C_i </tex>.<br />
|proof= <br />
Рассмотрим разность потоков <tex> g - f </tex>, <tex> |g - f| = 0 </tex>. Построим ее [[теорема о декомпозиции|декомпозицию]]. В декомпозиции могут быть только циклы, т.к. наличие путей <tex> s \leadsto t</tex> противоречило бы нулевой величине потока. Таким образом, получили разбиение разности потоков на циклы. Заметим, что <tex> g(u,v) - f(u,v) \leqslant c(u, v) - f(u, v) = c_f(u, v)</tex>, т.е. все циклы принадлежат <tex>G_f</tex>. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети<br />
|statement=<br />
Поток <tex> f </tex> {{---}} минимальной стоимости среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательной стоимости.<br />
|proof= <br />
*<tex>\Rightarrow </tex><br />
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательной стоимости в <tex> G_f </tex>,<br />
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.<br />
<br />
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. <br />
Так как сумма стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v) \in E} p(u,v) \cdot f_+(u,v) < 0</tex> <br />
<br />
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.<br />
*<tex>\Leftarrow </tex><br />
Рассмотрим поток <tex> f </tex>, такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> {{---}} поток величины <tex> |f| </tex> и минимальной стоимости, т. е. <tex> p(f') \leqslant p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \geqslant p(f) \Rightarrow p(f') = p(f)</tex>.<br />
}}<br />
<br />
== Источники информации ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>217.66.156.45http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE%D0%B1_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%B1%D1%8B%D1%82%D1%8C_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_%D0%BE%D1%82%D1%81%D1%83%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B8_%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2_%D0%B2_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B5%D1%82%D0%B8&diff=58988Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети2017-01-06T20:37:19Z<p>217.66.156.45: </p>
<hr />
<div>{{Лемма<br />
|about=<br />
о разности потоков<br />
|statement=<br />
Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки равной величины в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f </tex> и нескольких циклов в остаточной сети <tex> G_f </tex>, т.е. <tex>g = f + \sum_{i} C_i </tex>.<br />
|proof= <br />
Рассмотрим разность потоков <tex> g - f </tex>, <tex> |g - f| = 0 </tex>. Построим ее [[теорема о декомпозиции|декомпозицию]]. В декомпозиции могут быть только циклы, т.к. наличие путей <tex> s \leadsto t</tex> противоречило бы нулевой величине потока. Таким образом, получили разбиение разности потоков на циклы. Заметим, что <tex> g(u,v) - f(u,v) \leqslant c(u, v) - f(u, v) = c_f(u, v)</tex>, т.е. все циклы принадлежат <tex>G_f</tex>. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети<br />
|statement=<br />
Поток <tex> f </tex> {{---}} минимальной стоимости среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательной стоимости.<br />
|proof= <br />
*<tex>\Rightarrow </tex><br />
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательной стоимости в <tex> G_f </tex>,<br />
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.<br />
<br />
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. <br />
Так как сумма стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v) \in E} p(u,v) \cdot f_+(u,v) < 0</tex> <br />
<br />
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.<br />
*<tex>\Leftarrow </tex><br />
Рассмотрим поток <tex> f </tex>, такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> {{---}} поток величины <tex> |f| </tex> и минимальной стоимости, т. е. <tex> p(f') \leqslant p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \geqslant p(f) \Rightarrow p(f') = p(f)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>217.66.156.45http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE%D0%B1_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%B1%D1%8B%D1%82%D1%8C_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_%D0%BE%D1%82%D1%81%D1%83%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B8_%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2_%D0%B2_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B5%D1%82%D0%B8&diff=58987Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети2017-01-06T20:36:37Z<p>217.66.156.45: </p>
<hr />
<div>{{Лемма<br />
|about=<br />
о разности потоков<br />
|statement=<br />
Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки равной величины в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f </tex> и нескольких циклов в остаточной сети <tex> G_f </tex>, т.е. <tex>g = f + \sum_{i} C_i </tex>.<br />
|proof= <br />
Рассмотрим разность потоков <tex> g - f </tex>, <tex> |g - f| = 0 </tex>. Построим ее [[теорема о декомпозиции|декомпозицию]]. В декомпозиции могут быть только циклы, т.к. наличие путей <tex> s \leadsto t</tex> противоречило бы нулевой величине потока. Таким образом, получили разбиение разности потоков на циклы. Заметим, что <tex> g(u,v) - f(u,v) \leqslant c(u, v) - f(u, v) = c_f(u, v)</tex>, т.е. все циклы принадлежат <tex>G_f</tex>. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети<br />
|statement=<br />
Поток <tex> f </tex> {{---}} минимальной стоимости среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательной стоимости.<br />
|proof= <br />
*<tex>\Rightarrow </tex><br />
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательной стоимости в <tex> G_f </tex>,<br />
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.<br />
<br />
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. <br />
Так как сумма стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v) \in E} p(u,v) \cdot f_+(u,v) < 0</tex> <br />
<br />
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.<br />
*<tex>\Leftarrow </tex><br />
Рассмотрим поток <tex> f </tex>, такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> {{---}} поток величины <tex> |f| </tex> и минимальной стоимости, т. е. <tex> p(f') \leqslant p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \geq p(f) \Rightarrow p(f') = p(f)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>217.66.156.45http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE%D0%B1_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%B1%D1%8B%D1%82%D1%8C_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_%D0%BE%D1%82%D1%81%D1%83%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B8_%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2_%D0%B2_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B5%D1%82%D0%B8&diff=58986Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети2017-01-06T20:23:20Z<p>217.66.156.45: </p>
<hr />
<div>{{Лемма<br />
|about=<br />
о разности потоков<br />
|statement=<br />
Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки равной величины в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f </tex> и нескольких циклов в остаточной сети <tex> G_f </tex>, т.е. <tex>g = f + \sum_{i} C_i </tex>.<br />
|proof= <br />
Рассмотрим разность потоков <tex> g - f </tex>, <tex> |g - f| = 0 </tex>. Построим ее [[теорема о декомпозиции|декомпозицию]]. В декомпозиции могут быть только циклы, т.к. наличие путей <tex> s \leadsto t</tex> противоречило бы нулевой величине потока. Таким образом, получили разбиение разности потоков на циклы. Заметим, что <tex> g(u,v) - f(u,v) \le c(u, v) - f(u, v) = c_f(u, v)</tex>, т.е. все циклы принадлежат <tex>G_f</tex>. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети<br />
|statement=<br />
Поток <tex> f </tex> {{---}} минимальной стоимости среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательной стоимости.<br />
|proof= <br />
*<tex>\Rightarrow </tex><br />
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательной стоимости в <tex> G_f </tex>,<br />
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.<br />
<br />
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. <br />
Так как сумма стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v) \in E} p(u,v) \cdot f_+(u,v) < 0</tex> <br />
<br />
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.<br />
*<tex>\Leftarrow </tex><br />
Рассмотрим поток <tex> f </tex>, такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> {{---}} поток величины <tex> |f| </tex> и минимальной стоимости, т. е. <tex> p(f') \leq p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \geq p(f) \Rightarrow p(f') = p(f)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>217.66.156.45http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE%D0%B1_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0_%D0%B1%D1%8B%D1%82%D1%8C_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B8_%D0%BE%D1%82%D1%81%D1%83%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B8_%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2_%D0%B2_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D0%B5%D1%82%D0%B8&diff=58985Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети2017-01-06T20:22:49Z<p>217.66.156.45: </p>
<hr />
<div>{{Лемма<br />
|about=<br />
о разности потоков<br />
|statement=<br />
Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки равной величины в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f </tex> и нескольких циклов в остаточной сети <tex> G_f </tex>, т.е. <tex>g = f + \sum_{i} C_i </tex>.<br />
|proof= <br />
Рассмотрим разность потоков <tex> g - f </tex>, <tex> |g - f| = 0 </tex>. Построим ее [[декомпозицию|теорема о декомпозиции]]. В декомпозиции могут быть только циклы, т.к. наличие путей <tex> s \leadsto t</tex> противоречило бы нулевой величине потока. Таким образом, получили разбиение разности потоков на циклы. Заметим, что <tex> g(u,v) - f(u,v) \le c(u, v) - f(u, v) = c_f(u, v)</tex>, т.е. все циклы принадлежат <tex>G_f</tex>. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети<br />
|statement=<br />
Поток <tex> f </tex> {{---}} минимальной стоимости среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательной стоимости.<br />
|proof= <br />
*<tex>\Rightarrow </tex><br />
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательной стоимости в <tex> G_f </tex>,<br />
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.<br />
<br />
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. <br />
Так как сумма стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v) \in E} p(u,v) \cdot f_+(u,v) < 0</tex> <br />
<br />
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.<br />
*<tex>\Leftarrow </tex><br />
Рассмотрим поток <tex> f </tex>, такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> {{---}} поток величины <tex> |f| </tex> и минимальной стоимости, т. е. <tex> p(f') \leq p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \geq p(f) \Rightarrow p(f') = p(f)</tex>.<br />
}}<br />
<br />
== Литература ==<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>217.66.156.45