Циркуляция потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 8 участников)
Строка 1: Строка 1:
<wikitex>==Определение задачи==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 6: Строка 5:
 
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]
 
[[Файл:Циркул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).
+
Для решения этой задачи заменим исходную сеть $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'$, то есть для всех исходных вершин;
 
* $\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': 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>
 
  
 
==Псевдокод==
 
==Псевдокод==
  <tex>G=\varnothing</tex>                                           <font color=green>// пустой граф, вершины 0 и n + 1 - исток и сток, в исходном графе n вершин и m рёбер</font>
+
Конструктор ребра принимает следующие аргументы:
'''for''' <tex>e : e\in E</tex>                                      <font color=green>// ребро с полями (from, to, min_cap, cap)</font>
+
* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра
    edge <tex>t</tex>(<tex>0</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap)
+
* <tex>\mathtt{to}</tex> {{---}} вершина конца ребра
    edge <tex>g</tex>(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap <tex>-e</tex>.min_cap)
+
* <tex>\mathtt{minCap}</tex> {{---}} минимальная пропускная способность ребра
    edge <tex>h</tex>(<tex>e</tex>.from, <tex>n+1</tex>, <tex>0</tex>, <tex>e</tex>.min_cap)
+
* <tex>\mathtt{maxCap}</tex> {{---}} максимальная пропускная способность ребра
    <tex>G = G \cup {t,g,h}</tex>
+
  '''function''' circulation(<tex>V,E</tex>):
max_flow = getmaxflow(<tex>G</tex>)                         <font color=green>// наибольший поток в графе G</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> '''and''' <tex>e</tex>.from <tex>=s</tex>
+
    '''for''' <tex>e : e\in E</tex>
    '''if''' <tex>f</tex>(<tex>e</tex>)<tex>< e</tex>.cap                              <font color=green>// если для текущего ребра flow < cap</font>
+
        <tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.minCap)
        '''return''' false
+
        <tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.maxCap - <tex>e</tex>.minCap)
'''return''' true
+
        <tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minCap)
 +
        <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
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 19:19, 4 сентября 2022

Определение:
Поток нулевой величины в сети $G(V, E)$ называется циркуляцией (англ. circulation problem). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ — минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер.
Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)

Иначе говоря, закон сохранения потока [math]\sum\limits_v f(u,v)=0[/math] должен выполняться для всех вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать рёбра с положительной нижней пропускной способностью.

Решение

Для решения этой задачи заменим исходную сеть $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).

Рисунок 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$, то есть мы имеем обыкновенную сеть.

Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство [math]\sum\limits_v f(u,v) = 0[/math] для всех вершин графа. Это равносильно существованию потока между вершинами $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'$ соответствующие значения минимальной пропускной способности.

Псевдокод

Конструктор ребра принимает следующие аргументы:

  • [math]\mathtt{from}[/math] — вершина начала ребра
  • [math]\mathtt{to}[/math] — вершина конца ребра
  • [math]\mathtt{minCap}[/math] — минимальная пропускная способность ребра
  • [math]\mathtt{maxCap}[/math] — максимальная пропускная способность ребра
function circulation([math]V,E[/math]):
    [math]G'=[/math] ([math]V \cup s \cup t[/math], [math]\varnothing[/math])                                 // создаём новый граф с исходными вершинами и добавлением s и t — исток и сток
    for [math]e : e\in E[/math]
        [math]g[/math] = Edge([math]s[/math], [math]e[/math].to, [math]0[/math], [math]e[/math].minCap)
        [math]h[/math] = Edge([math]e[/math].from, [math]e[/math].to, [math]0[/math], [math]e[/math].maxCap - [math]e[/math].minCap)
        [math]k[/math] = Edge([math]e[/math].from, [math]t[/math], [math]0[/math], [math]e[/math].minCap)
        [math]G'=G' \cup [/math]([math]\varnothing[/math], [math]g \cup h \cup k[/math])
    maxFlow = getMaxFlow([math]G'[/math])                             // наибольший поток в графе G'
    for [math]e : e\in E'[/math] and [math]e[/math].from [math]=s[/math]
        if [math]f[/math]([math]e[/math]) [math] \lt  e[/math].maxCap                              // если для текущего ребра flow < cap
            return false
    return true

Источники информации