Циркуляция потока — различия между версиями
Smolcoder (обсуждение | вклад) (→Решение=) |
Smolcoder (обсуждение | вклад) (→Постановка задачи) |
||
| Строка 9: | Строка 9: | ||
</wikitex> | </wikitex> | ||
==Постановка задачи== | ==Постановка задачи== | ||
| − | <wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям на пропускные способности. | + | <wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности. |
Если рассматривать тривиальный случай, когда все $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. | Если рассматривать тривиальный случай, когда все $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. | ||
Версия 04:15, 17 декабря 2011
<wikitex>==Определение==
| Определение: |
| Циркуляцией называется поток в сети $G(V, E)$ величины ноль. |
То есть закон сохранения потока должен выполняться для всех без исключения вершин графа. Фактически, нет нужды в истоке и стоке. </wikitex>
Постановка задачи
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ — минимальная пропускная способность и $c_i$ — максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
Если рассматривать тривиальный случай, когда все $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. </wikitex>
Решение
<wikitex>фывафываф </wikitex>
