Редактирование: Циркуляция потока

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
{{Определение
+
==Определение==
 +
<wikitex>{{Определение
 
|definition=
 
|definition=
Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ называется '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер.  
+
'''Циркуляцией''' называется поток в [[Определение сети, потока|сети]] $G(V, E)$ нулевой величины.
 
}}
 
}}
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]
+
[[Файл:Циркул2.png|frame|справа|Пример графа и циркуляции в нем (поток/пропуск.способность)]]
  
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все  $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать рёбра с положительной нижней пропускной способностью.
+
То есть закон сохранения потока <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' без исключения вершин графа. Фактически, нет нужды в истоке и стоке.
 +
</wikitex>
 +
 
 +
==Постановка задачи==
 +
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
 +
 
 +
Рассмотрим тривиальный случай, когда все  $l_i = 0$, то достаточно пустить поток величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.  
 +
</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'$ следующим образом. Сначала добавим в граф вершины $x$ {{---}} новый исток и $y$ {{---}} новый сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим ребра $x \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} y$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$.
  
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]]
+
[[Файл:Циркул3.png]]
  
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то в новой сети по ребру $(x, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который раньше мог вытекать из $v_{from}$ по изначальному ребру, заменяется на поток, который может течь по ребрам $(v_{from}, v_{to})$ и $(v_{from}, y)$ (это ясно из того, что сумма их пропускных способностей в полученном графе равна $c_i$). Аналогично в вершине $v_{to}$, суммарный возможный входящий поток в которую не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами в полученном графе. Заметим, что в этом самом графе все $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> выполнено для всех вершин этого графа. Но это равносильно существованию потока между вершинами $x$ и $y$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, это значит, что этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, то и является нужным требованием. Если этот поток существует, то мы будем иметь:
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;
+
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{x,y\}, 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': f_i \leqslant c_i - l_i \Rightarrow 0 \leqslant f_i \leqslant c_i - l_i \Rightarrow l_i \leqslant f_i \leqslant c_i$, то есть все удовлетворяет ограничениям.
Значит, этот поток и есть циркуляция.  
+
то есть '''циркуляцию'''.  
  
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра из истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$ соответствующие значения минимальной пропускной способности.
+
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков по каждому ребру изначальной сети в случае, если циркуляция есть, достаточно просто прибавить к потокам в ребрах $e'_i$ величины $l_i$.
 +
</wikitex>
  
 
==Псевдокод==
 
==Псевдокод==
Конструктор ребра принимает следующие аргументы:
+
G    // пустой граф, вершины 0 и n + 1 - исток и сток
* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра
+
n, m; // вершин, ребер в исходном графе
* <tex>\mathtt{to}</tex> {{---}} вершина конца ребра
+
  edge  // ребро с полями (from, to, min_cap, cap)
* <tex>\mathtt{minCap}</tex> {{---}} минимальная пропускная способность ребра
+
Для i = 1 to m
* <tex>\mathtt{maxCap}</tex> {{---}} максимальная пропускная способность ребра
+
  считать ребро edge
  '''function''' circulation(<tex>V,E</tex>):
+
  добавить в граф G ребро (0, edge.to, 0, edge.min_cap)
    <tex>G'=</tex> (<tex>V \cup s \cup t</tex>, <tex>\varnothing</tex>)                                 <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font>
+
  добавить в граф G ребро (edge.from, edge.to, 0, edge.cap - edge.min_cap)
    '''for''' <tex>e : e\in E</tex>
+
  добавить в граф G ребро (edge.from, n + 1, 0, edge.min_cap)
        <tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.minCap)
+
max_flow = наибольший поток в графе G
        <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>.minCap)
+
  если для текущего ребра flow < cap  
        <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>
 
    '''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>.maxCap                              <font color=green>// если для текущего ребра flow < cap</font>
 
            '''return''' false
 
     '''return''' true
 
  
==Источники информации==
+
==Источники==
 
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']
 
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']
* [http://e-maxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]
+
* [http://e-maxx.ru/algo/flow_with_limits e-maxx]
* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]
 
 
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Задача о максимальном потоке]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: