http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=LehanyichВикиконспекты - Вклад участника [ru]2026-05-19T16:38:17ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=50821Циркуляция потока2016-01-07T15:26:02Z<p>Lehanyich: /* Псевдокод */</p>
<hr />
<div><wikitex><br />
{{Определение<br />
|definition=<br />
Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ называется '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер. <br />
}}<br />
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]<br />
<br />
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.<br />
</wikitex><br />
<br />
==Решение==<br />
<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).<br />
<br />
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]<br />
<br />
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то есть мы имеем обыкновенную сеть.<br />
<br />
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:<br />
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;<br />
* В $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$, что удовлетворяет всем ограничениям.<br />
Значит, этот поток и есть циркуляция. <br />
<br />
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.<br />
</wikitex><br />
<br />
==Псевдокод==<br />
Конструктор ребра принимает следующие аргументы:<br />
* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра<br />
* <tex>\mathtt{to}</tex> {{---}} вершина конца ребра<br />
* <tex>\mathtt{minCap}</tex> {{---}} минимальная пропускная способность ребра<br />
* <tex>\mathtt{maxCap}</tex> {{---}} максимальная пропускная способность ребра<br />
'''function''' circulation(<tex>V,E</tex>):<br />
<tex>G'=</tex> (<tex>V \cup s \cup t</tex>, <tex>\varnothing</tex>) <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font><br />
'''for''' <tex>e : e\in E</tex><br />
<tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.minCap)<br />
<tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.maxCap - <tex>e</tex>.minCap)<br />
<tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minCap)<br />
<tex>G'=G' \cup </tex>(<tex>\varnothing</tex>, <tex>g \cup h \cup k</tex>)<br />
maxFlow = getMaxFlow(<tex>G'</tex>) <font color=green>// наибольший поток в графе G'</font><br />
'''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>.from <tex>=s</tex><br />
'''if''' <tex>f</tex>(<tex>e</tex>) <tex> < e</tex>.maxCap <font color=green>// если для текущего ребра flow < cap</font><br />
'''return''' false<br />
'''return''' true<br />
<br />
==Источники информации==<br />
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']<br />
* [http://e-maxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]<br />
* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Задача о максимальном потоке]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=50819Циркуляция потока2016-01-07T15:08:13Z<p>Lehanyich: </p>
<hr />
<div><wikitex><br />
{{Определение<br />
|definition=<br />
Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ называется '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер. <br />
}}<br />
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]<br />
<br />
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.<br />
</wikitex><br />
<br />
==Решение==<br />
<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).<br />
<br />
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]<br />
<br />
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то есть мы имеем обыкновенную сеть.<br />
<br />
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:<br />
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;<br />
* В $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$, что удовлетворяет всем ограничениям.<br />
Значит, этот поток и есть циркуляция. <br />
<br />
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.<br />
</wikitex><br />
<br />
==Псевдокод==<br />
Конструктор ребра принимает следующие аргументы:<br />
* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра<br />
* <tex>\mathtt{to}</tex> {{---}} вершина конца ребра<br />
* <tex>\mathtt{cap}</tex> {{---}} минимальная пропускная способность ребра<br />
* <tex>\mathtt{mincap}</tex> {{---}} максимальная пропускная способность ребра<br />
'''function''' circulation(<tex>V,E</tex>):<br />
<tex>G'= {V,s,t}</tex> <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font><br />
'''for''' <tex>e : e\in E</tex><br />
<tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.mincap)<br />
<tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap - <tex>e</tex>.mincap)<br />
<tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minсap)<br />
<tex>G' = G' \cup {g,h,k}</tex><br />
maxFlow = getMaxFlow(<tex>G'</tex>) <font color=green>// наибольший поток в графе G'</font><br />
'''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>.from <tex>=s</tex><br />
'''if''' <tex>f</tex>(<tex>e</tex>)<tex> < e</tex>.cap <font color=green>// если для текущего ребра flow < cap</font><br />
'''return''' false<br />
'''return''' true<br />
<br />
==Источники информации==<br />
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']<br />
* [http://e-maxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]<br />
* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Задача о максимальном потоке]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B8&diff=50818Теорема о декомпозиции2016-01-07T14:47:58Z<p>Lehanyich: </p>
<hr />
<div>==Теорема==<br />
{{Теорема<br />
|about=<br />
о декомпозиции<br />
|statement=<br />
Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|поток]] в <tex>G</tex>. Тогда <tex>|f|</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов: <tex>|f| = \sum\limits_{i=1}^{}c_{i}\cdot f(p_{i}) + \sum\limits_{j=1}^{}d_{j}\cdot f(k_{j})</tex>, где <tex>p_{i}</tex> — путь из <tex>s</tex> в <tex>t</tex>, <tex>k_{j}</tex> — цикл, <tex>c_{i}</tex> и <tex>d_{j}</tex> — константы.<br />
|proof=<br />
Пусть <tex>s</tex> — исток, <tex>t</tex> — сток сети <tex>G</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь <tex>p_{i}</tex> из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл <tex>k_{j}</tex>). Данный путь (цикл) будет иметь положительный поток <tex>f</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.<br />
}}<br />
<br />
==Алгоритм==<br />
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):<br />
<br />
===Псевдокод===<br />
'''function''' simpleDecomposition(<tex>s</tex>):<br />
<tex> Q = \varnothing</tex> <font color=green>// множество пройденных рёбер</font><br />
<tex> P = \varnothing </tex> <font color=green>// множество посещённых вершин</font><br />
<tex>v = s</tex><br />
'''while''' <tex> v \notin P </tex><br />
'''if''' <tex> v = t </tex><br />
'''break'''<br />
edge <tex>e = \varnothing</tex><br />
'''for''' <tex>u : (v,u) \in E</tex><br />
'''if''' <tex> f(v,u)>0 </tex><br />
<tex>e = (v,u)</tex><br />
'''break'''<br />
'''if''' <tex>e = \varnothing</tex><br />
'''return''' <tex>\varnothing</tex><br />
<tex> Q</tex>.push_back(<tex>e</tex>)<br />
<tex> P = P \cup \{v\}</tex><br />
<tex> v = u </tex><br />
'''if''' <tex>v \in P </tex> <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все ребра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font><br />
'''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>)<br />
<tex>Q</tex>.pop_front()<br />
<tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{(u,v) \in Q}f(u,v) </tex><br />
'''return''' <tex>(f, Q)</tex><br />
<br />
'''function''' fullDecomposition():<br />
<tex> d = \varnothing </tex> <font color=green>// собственно, декомпозиция графа: совокупность подмножеств, которые являются путями/циклами, и их поток</font><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>) <font color=green>// один из путей/циклов в графе и его поток</font><br />
'''while''' (<tex>p \neq \varnothing</tex>)<br />
<tex> d = d \cup p </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''for''' <tex> u \in V </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''while''' (<tex>p \neq \varnothing</tex>)<br />
<tex> d = d \cup \{p\} </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''return''' <tex>d</tex><br />
<br />
===Анализ работы алгоритма===<br />
{{Утверждение<br />
|statement=<br />
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.<br />
|proof=<br />
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}<br />
<br />
==Источники==<br />
* ''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о максимальном потоке ]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=50815Циркуляция потока2016-01-07T14:17:44Z<p>Lehanyich: </p>
<hr />
<div><wikitex><br />
{{Определение<br />
|definition=<br />
Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ называется '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер. <br />
}}<br />
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]<br />
<br />
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.<br />
</wikitex><br />
<br />
==Решение==<br />
<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).<br />
<br />
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]<br />
<br />
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то есть мы имеем обыкновенную сеть.<br />
<br />
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:<br />
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;<br />
* В $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$, что удовлетворяет всем ограничениям.<br />
Значит, этот поток и есть циркуляция. <br />
<br />
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.<br />
</wikitex><br />
<br />
==Псевдокод==<br />
'''function''' circulation(<tex>V,E</tex>)<br />
<tex>G=\varnothing</tex> <font color=green>// пустой граф, вершины s и t - исток и сток</font><br />
'''for''' <tex>e : e\in E</tex> <font color=green>// конструктор ребра принимает 4 параметра: две инцидентные ребру вершины, величину потока через это ребро и пропускную способность</font><br />
<tex>t</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
<tex>g</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap - <tex>e</tex>.min_cap)<br />
<tex>h</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
<tex>G = G \cup {t,g,h}</tex><br />
maxFlow = getMaxFlow(<tex>G</tex>) <font color=green>// наибольший поток в графе G</font><br />
'''for''' <tex>e : e\in E</tex> '''and''' <tex>e</tex>.from <tex>=s</tex><br />
'''if''' <tex>f</tex>(<tex>e</tex>)<tex> < e</tex>.cap <font color=green>// если для текущего ребра flow < cap</font><br />
'''return''' false<br />
'''return''' true<br />
<br />
==Источники информации==<br />
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']<br />
* [http://e-maxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]<br />
* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Задача о максимальном потоке]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B8&diff=50814Теорема о декомпозиции2016-01-07T13:53:40Z<p>Lehanyich: </p>
<hr />
<div>==Теорема==<br />
{{Теорема<br />
|about=<br />
о декомпозиции<br />
|statement=<br />
Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|поток]] в <tex>G</tex>. Тогда <tex>|f|</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов: <tex>|f| = \sum\limits_{i=1}^{}c_{i}\cdot f(p_{i}) + \sum\limits_{j=1}^{}d_{j}\cdot f(k_{j})</tex>, где <tex>p_{i}</tex> — путь из <tex>s</tex> в <tex>t</tex>, <tex>k_{j}</tex> — цикл, <tex>c_{i}</tex> и <tex>d_{j}</tex> — константы.<br />
|proof=<br />
Пусть <tex>s</tex> — исток, <tex>t</tex> — сток сети <tex>G</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь <tex>p_{i}</tex> из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл <tex>k_{j}</tex>). Данный путь (цикл) будет иметь положительный поток <tex>f</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.<br />
}}<br />
<br />
==Алгоритм==<br />
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):<br />
<br />
===Псевдокод===<br />
'''function''' simpleDecomposition(<tex>s</tex>)<br />
<tex> Q = \varnothing</tex> <font color=green>// множество пройденных рёбер</font><br />
<tex> P = \varnothing </tex> <font color=green>// множество посещённых вершин</font><br />
<tex>v = s</tex><br />
'''while''' <tex> v \notin P </tex><br />
'''if''' <tex> v = t </tex><br />
'''break'''<br />
edge <tex>e = \varnothing</tex><br />
'''for''' <tex>u : (v,u) \in E</tex><br />
'''if''' <tex> f(v,u)>0 </tex><br />
<tex>e = (v,u)</tex><br />
'''break'''<br />
'''if''' <tex>e = \varnothing</tex><br />
'''return''' <tex>\varnothing</tex><br />
<tex> Q</tex>.push_back(<tex>e</tex>)<br />
<tex> P = P \cup \{v\}</tex><br />
<tex> v = u </tex><br />
'''if''' <tex>v \in P </tex> <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все ребра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font><br />
'''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>)<br />
<tex>Q</tex>.pop_front()<br />
<tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{(u,v) \in Q}f(u,v) </tex><br />
'''return''' <tex>(f, Q)</tex><br />
<br />
'''function''' fullDecomposition()<br />
<tex> d = \varnothing </tex> <font color=green>// собственно, декомпозиция графа: совокупность подмножеств, которые являются путями/циклами, и их поток</font><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>) <font color=green>// один из путей/циклов в графе и его поток</font><br />
'''while''' (<tex>p \neq \varnothing</tex>)<br />
<tex> d = d \cup p </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''for''' <tex> u \in V </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''while''' (<tex>p \neq \varnothing</tex>)<br />
<tex> d = d \cup \{p\} </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''return''' <tex>d</tex><br />
<br />
===Анализ работы алгоритма===<br />
{{Утверждение<br />
|statement=<br />
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.<br />
|proof=<br />
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}<br />
<br />
==Источники==<br />
* ''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о максимальном потоке ]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B3%D1%80%D0%B0%D1%84%D0%B0&diff=50813Двойственный граф планарного графа2016-01-07T13:09:25Z<p>Lehanyich: </p>
<hr />
<div>{{Определение<br />
|neat=neat<br />
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:<br />
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>.<br />
# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро.<br />
}}<br />
[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]<br />
<div style='clear:left;'></div><br />
<br />
<br />
Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.<br />
<br />
Например, существуют графы, двойственные себе: — <tex>K_1</tex> и <tex>K_4</tex>. Далее мы убедимся, что среди полных графов только они обладают таким свойством.<br />
<br />
<br />
<br />
== Свойства ==<br />
[[Файл:Treenflower new.png|250px|thumb|right|Дерево и двойственный к нему «цветок».]]<br />
* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex>.<br />
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).<br />
* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4</ref>, у него должен быть единственный ''двойственный граф''.<br />
* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост. Частный случай: полный граф <tex>K_2</tex><br />
* Мультиграф, ''двойственный'' к дереву, — цветок.<br />
<br />
<br />
== Самодвойственные графы ==<br />
{{Определение<br />
|definition=Планарный граф называется '''самодвойственным''' (англ. ''self-dual graph''), если он изоморфен своему двойственному графу.<br />
}}<br />
<div style='clear:left;'></div><br />
<br />
<br />
{|align="center"<br />
|-valign="top"<br />
|[[Файл:Wheel8_new2.png|500px|thumb|left|Колесо и двойственный ему граф {{---}} тоже колесо.]]<br />
|[[Файл:K4_new.png|250px|thumb|right|<tex>K_4</tex> (он же колесо).]]<br />
|}<br />
<br />
<br />
<br />
{{Утверждение<br />
|neat=neat<br />
|statement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет.<br />
|proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \dfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \dfrac{V \cdot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.<br />
}}<br />
<br />
<div style='clear: both;'><br/></div><br />
{{Утверждение<br />
|neat=neat<br />
|statement=Все колёса самодвойственны.<br />
|proof=Это утверждение очевидно.<br/>Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.<br />
}}<br />
<br />
<div style="clear:both;"></div><br />
<br />
== См. также ==<br />
*[[Формула Эйлера]]<br />
*[[Укладка графа на плоскости]]<br />
*[[Гамма-алгоритм]]<br />
<br />
== Примечания ==<br />
<references /><br />
<br />
== Источники информации==<br />
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Двойственный граф]<br />
* [https://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Планарный граф]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Укладки графов]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B3%D1%80%D0%B0%D1%84%D0%B0&diff=50325Двойственный граф планарного графа2015-12-20T17:46:28Z<p>Lehanyich: </p>
<hr />
<div>{{Определение<br />
|neat=neat<br />
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:<br />
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>.<br />
# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро.<br />
}}<br />
[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]<br />
<div style='clear:left;'></div><br />
<br />
<br />
Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.<br />
<br />
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''.<br />
<br />
<br />
<br />
== Свойства ==<br />
[[Файл:Treenflower new.png|250px|thumb|right|Дерево и двойственный к нему «цветок».]]<br />
* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex>.<br />
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).<br />
* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4</ref>, у него должен быть единственный ''двойственный граф''.<br />
* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост.<br />
* Мультиграф, ''двойственный'' к дереву, — цветок.<br />
<br />
<br />
== Самодвойственные графы ==<br />
{{Определение<br />
|definition=Планарный граф называется '''самодвойственным''' (англ. ''self-dual graph''), если он изоморфен своему двойственному графу.<br />
}}<br />
<div style='clear:left;'></div><br />
<br />
<br />
{|align="center"<br />
|-valign="top"<br />
|[[Файл:Wheel8_new2.png|500px|thumb|left|Колесо и двойственный ему граф {{---}} тоже колесо.]]<br />
|[[Файл:K4_new.png|250px|thumb|right|<tex>K_4</tex> (он же колесо).]]<br />
|}<br />
<br />
<br />
<br />
{{Утверждение<br />
|neat=neat<br />
|statement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет.<br />
|proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \dfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \dfrac{V \cdot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.<br />
}}<br />
<br />
<div style='clear: both;'><br/></div><br />
{{Утверждение<br />
|neat=neat<br />
|statement=Все колёса самодвойственны.<br />
|proof=Это утверждение очевидно.<br/>Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.<br />
}}<br />
<br />
<div style="clear:both;"></div><br />
<br />
== См. также ==<br />
*[[Формула Эйлера]]<br />
*[[Укладка графа на плоскости]]<br />
*[[Гамма-алгоритм]]<br />
<br />
== Примечания ==<br />
<references /><br />
<br />
== Источники информации==<br />
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Двойственный граф]<br />
* [https://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Планарный граф]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Укладки графов]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%BE%D0%B2%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0&diff=50312Алгоритм построения Эйлерова цикла2015-12-20T04:58:53Z<p>Lehanyich: </p>
<hr />
<div>== Алгоритм ==<br />
=== Описание алгоритма ===<br />
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br><br />
Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.<br />
<br />
=== Псевдокод ===<br />
<font size=2><br />
'''Код проверки графа на эйлеровость:'''<br />
'''boolean''' checkForEulerPath():<br />
'''int''' OddVertex <tex>= 0</tex><br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) '''mod''' <tex>2 == 1</tex><br />
OddVertex++<br />
'''if''' OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font><br />
'''return''' ''false''<br />
'''boolean''' visited(<tex>|V|</tex>, ''false'') <font color=darkgreen>// массив инициализируется значениями ''false''</font><br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex><br />
dfs(<tex>v</tex>, visited)<br />
'''break'''<br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex> '''and''' '''not''' visited[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font><br />
'''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font><br />
'''return''' ''true'' <font color=darkgreen>// граф является эйлеровым</font><br />
<br />
'''Код построения эйлерова пути:'''<br />
'''function''' findEulerPath(<tex>v</tex>): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font><br />
'''for''' <tex>u : u \in V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>u</tex>) '''mod''' <tex>2 == 1</tex><br />
<tex>v = u</tex><br />
'''break'''<br />
Stack <tex>S</tex><br />
<tex>S</tex>.push(<tex>v</tex>)<br />
'''while not''' <tex>S</tex>.empty()<br />
<tex>w = </tex> <tex>S</tex>.top()<br />
'''for''' <tex>u : u \in V</tex><br />
'''if''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font><br />
<tex>S</tex>.push(<tex>u</tex>) <font color=darkgreen> // добавили новую вершину в стек</font><br />
<tex>E</tex>.remove(<tex>w, u</tex>)<br />
'''break'''<br />
'''if''' <tex> w == S</tex>.top()<br />
<tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font><br />
print(<tex>w</tex>)<br />
</font><br />
<br />
=== Доказательство корректности ===<br />
{{Лемма<br />
|statement=Данный алгоритм проходит по каждому ребру, причем ровно один раз.<br />
|proof=Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не пройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека <tex>S</tex>, и он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз.<br />
Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может.<br><br />
}}<br />
Вершина <tex>v</tex>, с которой начат обход графа, будет последней помещена в путь <tex>P</tex>. Так как изначально стек пуст, и вершина <tex>v</tex> входит в стек первой, то после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается.<br><br />
{{Лемма<br />
|statement=Напечатанный путь <tex>P</tex> {{---}} корректный маршрут в графе, в котором каждые две соседние вершины <tex>u_i</tex> и <tex>u_{i+1}</tex> будут образовывать ребро <tex>(u_i, u_{i+1}) \in E</tex>.<br />
|proof=Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Рассмотрим случай, когда из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>u</tex>, а следующей в <tex>S</tex> лежит <tex>w</tex>. Возможны 2 варианта:<br />
*На следующем шаге для вершины <tex>w</tex> не найдётся инцидентного ребра, тогда <tex>w</tex> переместят в <tex>P</tex>, и ребро <tex>(w,u)</tex> будет представлено в <tex>P</tex>.<br />
*Иначе будет пройдена некоторая последовательность ребер <tex>{u_1, u_2, ..., u_k}</tex>, начинающаяся в вершине <tex>w</tex> и проходящая по ребру <tex>(w, u_1)</tex>. Докажем, что данный проход <tex>{u_1, u_2, ..., u_k}</tex> закончится в вершине <tex>w</tex>:<br />
#Ребро <tex>(u_{k-1}, u_k)</tex> не может быть инцидентно вершинам <tex>u_1, \dots , u_{k-2}</tex>, иначе степень вершины <tex>u_k</tex> окажется нечетной.<br />
#Предположим, что <tex>(u_{k-1}, u_k)</tex> инцидентно вершине, пройденной при обходе графа из вершины <tex>u</tex>. Но это неверно, так как тогда бы данные вершины пройдены ранее.<br />
Из этого следует, что мы закончим обход в вершине <tex>w</tex>. Следовательно, данная вершина первой поместится в <tex>P</tex> вслед за <tex>u</tex>, и ребро <tex>(w, u)</tex> будет представлено в <tex>P</tex>.<br />
}}<br />
{{Теорема<br />
|id=proof1<br />
|statement=Данный алгоритм находит корректный эйлеров путь.<br />
|proof=Из предыдущих лемм следует, что <tex>P</tex> {{---}} искомый эйлеров путь и алгоритм работает корректно.<br />
}}<br />
=== Рекурсивная реализация ===<br />
<font size=2><br />
'''function''' findEulerPath(<tex>v</tex> : Vertex):<br />
'''for''' <tex>(v,u)</tex> <tex>\in</tex> <tex>E</tex><br />
remove <tex>(v, u)</tex><br />
findEulerPath(<tex>u</tex>)<br />
print(<tex>v</tex>)<br />
</font><br />
=== Время работы ===<br />
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br><br />
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</tex> бинарного типа.<br />
<br />
== См. также ==<br />
* [[Гамильтоновы графы]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/Эйлеров_цикл Википедия {{---}} Эйлеров цикл]<br />
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]<br />
* [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]<br />
[[Категория: Эйлеровы графы]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%BE%D0%B2%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0&diff=50142Алгоритм построения Эйлерова цикла2015-12-06T07:35:05Z<p>Lehanyich: /* Псевдокод */</p>
<hr />
<div>== Алгоритм ==<br />
=== Описание алгоритма ===<br />
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью.<br><br />
Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в [[Стек | стеке]] <tex>S</tex>. Когда наступает такой момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.<br />
<br />
=== Псевдокод ===<br />
<font size=2><br />
'''Код проверки графа на эйлеровость:'''<br />
'''boolean''' checkForEulerPath():<br />
'''int''' OddVertex <tex>= 0</tex><br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) '''mod''' <tex>2 == 1</tex><br />
OddVertex++<br />
'''if''' OddVertex <tex> > 2 </tex><font color=darkgreen>// если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым</font><br />
'''return''' ''false''<br />
'''boolean''' visited(<tex>|V|</tex>, ''false'') <font color=darkgreen>// массив инициализируется значениями ''false''</font><br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex><br />
dfs(<tex>v</tex>, visited)<br />
'''break'''<br />
'''for''' <tex>v : v</tex> <tex>\in</tex> <tex>V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>v</tex>) <tex> > 0</tex> '''and''' '''not''' visited[<tex>v</tex>] <font color=darkgreen>// если количество компонент связности, содержащие ребра, больше одной,</font><br />
'''return''' ''false'' <font color=darkgreen> // то граф не является эйлеровым</font><br />
'''return''' ''true'' <font color=darkgreen>// граф является эйлеровым</font><br />
<br />
'''Код построения эйлерова пути:'''<br />
'''function''' findEulerPath(<tex>v</tex>): <font color=darkgreen> // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени </font><br />
'''for''' <tex>u : u \in V</tex><br />
'''if''' <tex>\operatorname{deg}</tex>(<tex>u</tex>) '''mod''' <tex>2 == 1</tex><br />
<tex>v = u</tex><br />
'''break'''<br />
Stack <tex>S</tex><br />
<tex>S</tex>.push(<tex>v</tex>)<br />
'''while not''' <tex>S</tex>.empty()<br />
<tex>w = </tex> <tex>S</tex>.top()<br />
'''for''' <tex>u : u \in V</tex><br />
'''if''' (<tex>w, u</tex>) <tex>\in E</tex> <font color=darkgreen> // нашли ребро, по которому ещё не прошли</font><br />
<tex>S</tex>.push(<tex>u</tex>) <font color=darkgreen> // добавили новую вершину в стек</font><br />
<tex>E</tex>.remove(<tex>w, u</tex>)<br />
'''break'''<br />
'''if''' <tex> w == S</tex>.top()<br />
<tex>S</tex>.pop() <font color=darkgreen> // не нашлось инцидентных вершине <tex>w</tex> рёбер, по которым ещё не прошли</font><br />
print(<tex>w</tex>)<br />
</font><br />
<br />
=== Доказательство корректности ===<br />
<br />
{{Теорема<br />
|id=proof1<br />
|statement=Данный алгоритм находит корректный эйлеров путь.<br />
|proof=<br />
{{TODO | t = Довести до ума}}<br><br />
Данный алгоритм проходит по каждому ребру, причем ровно один раз. Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым. Так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может.<br><br />
Вершина <tex>v</tex>, с которой начат обход графа, будет последней помещена в путь <tex>P</tex>. Так как изначально стек пуст, и вершина <tex>v</tex> входит в стек первой, то после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается.<br><br />
Напечатанный путь <tex>P</tex> {{---}} корректный маршрут в графе, в котором каждые две соседние вершины <tex>u_i</tex> и <tex>u_{i+1}</tex> будут образовывать ребро <tex>(u_i, u_{i+1})</tex>, принадлежащее <tex>E</tex>. Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Рассмотрим случай, когда из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>u</tex>, а следующей в <tex>S</tex> лежит <tex>w</tex>. Возможны 2 варианта:<br />
#На следующем шаге <tex>w</tex> перемещена в <tex>P</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.<br />
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>w</tex>, и проходящая по ребру <tex>(w, u_1)</tex>. Докажем, что данный проход <tex>T</tex> <tex>{u_1, u_2, ..., u_k}</tex> закончится в вершине <tex>w</tex>: ребро <tex>(u_{k-1}, u_k)</tex> не может быть инцидентно вершинам <tex>u_1, \dots , u_{k-2}</tex>. Иначе степень вершины <tex>u_k</tex> будет нечетной. Предположим, что <tex>(u_{k-1}, u_k)</tex> инцидентно вершине, пройденной при обходе графа из вершины <tex>u</tex>. Но это неверно, так как тогда бы данные вершины пройдены ранее. Из этого следует, что мы закончим обход в вершине <tex>w</tex>. Следовательно, данная вершина первой поместится в <tex>P</tex> вслед за <tex>u</tex>, и ребро <tex>(w, u)</tex> будет представлено в <tex>P</tex>.<br />
Из этого следует, что <tex>P</tex> {{---}} искомый эйлеров путь.<br />
}}<br />
=== Рекурсивная реализация ===<br />
<font size=2><br />
'''function''' findEulerPath(<tex>v</tex> : Vertex):<br />
'''for''' <tex>(v,u)</tex> <tex>\in</tex> <tex>E</tex><br />
remove <tex>(v, u)</tex><br />
findEulerPath(<tex>u</tex>)<br />
print(<tex>v</tex>)<br />
</font><br />
=== Время работы ===<br />
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.<br><br />
Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство <tex>\mathtt{deleted}</tex> бинарного типа.<br />
<br />
== См. также ==<br />
* [[Гамильтоновы графы]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/Эйлеров_цикл Википедия {{---}} Эйлеров цикл]<br />
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]<br />
* [http://ивтб.рф/exams/саод/36.htm Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=50041Циркуляция потока2015-11-29T14:48:32Z<p>Lehanyich: </p>
<hr />
<div><wikitex>==Определение задачи==<br />
{{Определение<br />
|definition=<br />
Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ называется '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер. <br />
}}<br />
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]<br />
<br />
Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. <br />
</wikitex><br />
<br />
==Решение==<br />
<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).<br />
<br />
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]<br />
<br />
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то есть мы имеем обыкновенную сеть.<br />
<br />
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:<br />
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;<br />
* В $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$, что удовлетворяет всем ограничениям.<br />
Значит, этот поток и есть циркуляция. <br />
<br />
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.<br />
</wikitex><br />
<br />
==Псевдокод==<br />
<tex>G=\varnothing</tex> <font color=green>// пустой граф, вершины 0 и n + 1 - исток и сток, в исходном графе n вершин и m рёбер</font><br />
'''for''' <tex>e : e\in E</tex> <font color=green>// ребро с полями (from, to, min_cap, cap)</font><br />
edge <tex>t</tex>(<tex>0</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
edge <tex>g</tex>(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap <tex>-e</tex>.min_cap)<br />
edge <tex>h</tex>(<tex>e</tex>.from, <tex>n+1</tex>, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
<tex>G = G \cup {t,g,h}</tex><br />
max_flow = getmaxflow(<tex>G</tex>) <font color=green>// наибольший поток в графе G</font><br />
'''for''' <tex>e : e\in E</tex> '''and''' <tex>e</tex>.from <tex>=s</tex><br />
'''if''' <tex>f</tex>(<tex>e</tex>)<tex>< e</tex>.cap <font color=green>// если для текущего ребра flow < cap</font><br />
'''return''' false<br />
'''return''' true<br />
<br />
==Источники информации==<br />
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']<br />
* [http://e-maxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]<br />
* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Задача о максимальном потоке]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B8%D1%80%D0%BA%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=50036Циркуляция потока2015-11-24T16:36:49Z<p>Lehanyich: /* Псевдокод */</p>
<hr />
<div><wikitex>==Определение==<br />
{{Определение<br />
|definition=<br />
'''Циркуляцией''' называется поток в [[Определение сети, потока|сети]] $G(V, E)$ нулевой величины (см. рисунок 1).<br />
}}<br />
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]<br />
<br />
То есть [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке.<br />
</wikitex><br />
==Постановка задачи==<br />
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности. <br />
<br />
Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью. <br />
</wikitex><br />
==Решение==<br />
<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).<br />
<br />
[[Файл:Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.]]<br />
<br />
Каждое ребро изначального графа заменяется на три новых. Если по ребру $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$, то есть мы имеем обыкновенную сеть.<br />
<br />
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:<br />
* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, v \in V'$, то есть для всех исходных вершин;<br />
* В $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$, что удовлетворяет всем ограничениям.<br />
Значит, этот поток и есть циркуляция. <br />
<br />
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети $G'$ соответствующие значения минимальной пропускной способности.<br />
</wikitex><br />
<br />
==Псевдокод==<br />
<tex>G=\varnothing</tex> <font color=green>// пустой граф, вершины 0 и n + 1 - исток и сток, в исходном графе n вершин и m рёбер</font><br />
'''for''' <tex>e : e\in E</tex> <font color=green>// ребро с полями (from, to, min_cap, cap)</font><br />
edge <tex>t</tex>(<tex>0</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
edge <tex>g</tex>(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap <tex>-e</tex>.min_cap)<br />
edge <tex>h</tex>(<tex>e</tex>.from, <tex>n+1</tex>, <tex>0</tex>, <tex>e</tex>.min_cap)<br />
<tex>G = G \cup {t,g,h}</tex><br />
max_flow = getmaxflow(<tex>G</tex>) <font color=green>// наибольший поток в графе G</font><br />
'''for''' <tex>e : e\in E</tex> '''and''' <tex>e</tex>.from <tex>=s</tex><br />
'''if''' <tex>f</tex>(<tex>e</tex>)<tex>< e</tex>.cap <font color=green>// если для текущего ребра flow < cap</font><br />
'''return''' false<br />
'''return''' true<br />
<br />
==Источники==<br />
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']<br />
* [http://e-maxx.ru/algo/flow_with_limits e-maxx]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Задача о максимальном потоке]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B8&diff=50035Теорема о декомпозиции2015-11-24T15:06:45Z<p>Lehanyich: </p>
<hr />
<div>==Теорема==<br />
{{Теорема<br />
|about=<br />
о декомпозиции<br />
|statement=<br />
Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|поток]] в <tex>G</tex>. Тогда <tex>f</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов, при этом все пути и циклы будут иметь положительный поток.<br />
|proof=<br />
Пусть <tex>s</tex> — исток, <tex>t</tex> — сток сети <tex>G</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.<br />
}}<br />
<br />
==Алгоритм==<br />
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):<br />
<br />
===Псевдокод===<br />
'''simpleDecomposition(<tex>s</tex>)'''<br />
<tex> Q = \varnothing</tex><br />
<tex> P = \varnothing </tex><br />
<tex>v = s</tex><br />
'''while''' <tex> v \notin P </tex><br />
'''if''' <tex> v = t </tex><br />
'''break'''<br />
edge <tex>e =</tex> NULL<br />
'''for''' <tex>u : (vu) \in E</tex><br />
'''if''' <tex> f(vu)>0 </tex><br />
<tex>e = (vu)</tex><br />
'''break'''<br />
'''if''' <tex>e =</tex> NULL<br />
'''return''' NULL<br />
<tex> Q</tex>.push_back(<tex>e</tex>)<br />
<tex> P = P \cup \{v\}</tex><br />
<tex> v = u </tex><br />
'''if''' <tex>v \in P </tex> <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все ребра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font><br />
'''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>)<br />
<tex>Q</tex>.pop_front()<br />
<tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{uv \in Q}f(uv) </tex><br />
'''return''' <tex>(f, Q)</tex><br />
<br />
'''fullDecomposition()'''<br />
<tex> d = \varnothing </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex> d = d \cup p </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''for''' <tex> u \in V </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex> d = d \cup \{p\} </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''return''' <tex>d</tex><br />
<br />
===Анализ работы алгоритма===<br />
{{Утверждение<br />
|statement=<br />
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.<br />
|proof=<br />
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}<br />
<br />
==Источники==<br />
* ''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о максимальном потоке ]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B8&diff=50034Теорема о декомпозиции2015-11-24T15:01:11Z<p>Lehanyich: /* Псевдокод */</p>
<hr />
<div>==Теорема==<br />
{{Теорема<br />
|about=<br />
о декомпозиции<br />
|statement=<br />
Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|поток]] в <tex>G</tex>. Тогда <tex>f</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов, при этом все пути и циклы имеют положительный поток.<br />
|proof=<br />
Пусть <tex>s</tex> — исток, <tex>t</tex> — сток сети <tex>G</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.<br />
}}<br />
<br />
==Алгоритм==<br />
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):<br />
<br />
===Псевдокод===<br />
'''simpleDecomposition(<tex>s</tex>)'''<br />
<tex> Q = \varnothing</tex><br />
<tex> P = \varnothing </tex><br />
<tex>v = s</tex><br />
'''while''' <tex> v \notin P </tex><br />
'''if''' <tex> v = t </tex><br />
'''break'''<br />
edge <tex>e =</tex> NULL<br />
'''for''' <tex>u : (vu) \in E</tex><br />
'''if''' <tex> f(vu)>0 </tex><br />
<tex>e = (vu)</tex><br />
'''break'''<br />
'''if''' <tex>e =</tex> NULL<br />
'''return''' NULL<br />
<tex> Q</tex>.push_back(<tex>e</tex>)<br />
<tex> P = P \cup \{v\}</tex><br />
<tex> v = u </tex><br />
'''if''' <tex>v \in P </tex> <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все ребра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font><br />
'''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>)<br />
<tex>Q</tex>.pop_front()<br />
<tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{uv \in Q}f(uv) </tex><br />
'''return''' <tex>(f, Q)</tex><br />
<br />
'''fullDecomposition()'''<br />
<tex> d = \varnothing </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex> d = d \cup p </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
'''for''' <tex> u \in V </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex> d = d \cup \{p\} </tex><br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
'''return''' <tex>d</tex><br />
<br />
===Анализ работы алгоритма===<br />
{{Утверждение<br />
|statement=<br />
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.<br />
|proof=<br />
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}<br />
<br />
==Источники==<br />
''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о максимальном потоке ]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%B4%D0%B5%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B8&diff=50032Теорема о декомпозиции2015-11-22T19:18:59Z<p>Lehanyich: </p>
<hr />
<div>==Теорема==<br />
{{Теорема<br />
|about=<br />
о декомпозиции<br />
|statement=<br />
Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|поток]] в <tex>G</tex>. Тогда <tex>f</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов, при этом все пути и циклы имеют положительный поток.<br />
|proof=<br />
Пусть <tex>s</tex> — исток, <tex>t</tex> — сток сети <tex>G</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.<br />
}}<br />
<br />
==Алгоритм==<br />
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):<br />
<br />
===Псевдокод===<br />
'''simpleDecomposition(<tex>s</tex>)'''<br />
<tex> Q = \varnothing</tex><br />
<tex> P = \varnothing </tex><br />
<tex>v = s</tex><br />
'''while''' <tex> v \notin P </tex><br />
'''if''' <tex> v = t </tex><br />
'''break'''<br />
edge <tex>e =</tex> NULL<br />
'''for''' <tex>u : (vu) \in E</tex><br />
'''if''' <tex> f(vu)>0 </tex><br />
<tex>e = (vu)</tex><br />
'''break'''<br />
'''if''' <tex>e =</tex> NULL<br />
'''return''' NULL<br />
<tex> Q = Q \cup \{e\}</tex><br />
<tex> P = P \cup \{v\}</tex><br />
<tex> v = u </tex><br />
'''if''' <tex>v \in P </tex><br />
удаляем из <tex>Q</tex> все ребра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex><br />
<tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{uv \in Q}f(uv) </tex><br />
'''return''' <tex>(f, Q)</tex><br />
<br />
'''fullDecomposition()'''<br />
<tex> d = \varnothing </tex><br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex>p = </tex> simpleDecomposition(<tex>s</tex>)<br />
<tex> d = d \cup p </tex><br />
'''for''' <tex> u \in V </tex><br />
'''while''' (<tex>p \neq </tex> NULL)<br />
<tex>p = </tex> simpleDecomposition(<tex>u</tex>)<br />
<tex> d = d \cup \{p\} </tex><br />
'''return''' <tex>d</tex><br />
<br />
===Анализ работы алгоритма===<br />
{{Утверждение<br />
|statement=<br />
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.<br />
|proof=<br />
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}<br />
<br />
==Источники==<br />
''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Задача о максимальном потоке ]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B3%D1%80%D0%B0%D1%84%D0%B0&diff=50014Двойственный граф планарного графа2015-11-21T18:51:12Z<p>Lehanyich: </p>
<hr />
<div>{{Определение<br />
|neat=neat<br />
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:<br />
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex><br />
# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро<br />
}}<br />
[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]<br />
<div style='clear:left;'></div><br />
<br />
<br />
Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.<br />
<br />
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''.<br />
<br />
<br />
<br />
== Свойства ==<br />
[[Файл:Treenflower new.png|250px|thumb|right|Дерево и двойственный к нему «цветок».]]<br />
* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex><br />
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку)<br />
* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4</ref>, у него должен быть единственный ''двойственный граф''<br />
* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост<br />
* Мультиграф, ''двойственный'' к дереву, — цветок<br />
<br />
<br />
== Самодвойственные графы ==<br />
{{Определение<br />
|definition=Планарный граф называется '''самодвойственным''', если он изоморфен своему двойственному графу.<br />
}}<br />
<div style='clear:left;'></div><br />
<br />
<br />
{|align="center"<br />
|-valign="top"<br />
|[[Файл:Wheel8_new2.png|500px|thumb|left|Колесо и двойственный ему граф {{---}} тоже колесо.]]<br />
|[[Файл:K4_new.png|250px|thumb|right|<tex>K_4</tex> (он же колесо).]]<br />
|}<br />
<br />
<br />
<br />
{{Утверждение<br />
|neat=neat<br />
|statement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет.<br />
|proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \dfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \dfrac{V \cdot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.<br />
}}<br />
<br />
<div style='clear: both;'><br/></div><br />
{{Утверждение<br />
|neat=neat<br />
|statement=Все колёса самодвойственны.<br />
|proof=Это утверждение очевидно.<br/>Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.<br />
}}<br />
<br />
<div style="clear:both;"></div><br />
<br />
== См. также ==<br />
*[[Формула Эйлера]]<br />
*[[Укладка графа на плоскости]]<br />
*[[Гамма-алгоритм]]<br />
<br />
== Примечания ==<br />
<references /><br />
<br />
== Источники информации==<br />
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Двойственный граф]<br />
* [https://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Планарный граф]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Укладки графов]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49882Алгоритм Левита2015-11-13T18:24:19Z<p>Lehanyich: /* Сложность */</p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
Для хранения вершин используем следующие структуры данных:<br />
* <tex>M_0</tex> {{---}} [[Хеш-таблица|хеш-таблица]],<br />
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],<br />
* <tex>M_2</tex> {{---}} [[Хеш-таблица|хеш-таблица]].<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.<br />
<br />
В плохих случаях алгоритм Левита работает за <tex>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с <tex>n</tex> вершинами и такими <tex>m</tex> рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:<br />
* для всех вершин <tex>1 < i < j \leqslant n</tex> вес ребра <tex>(i,j) = j - i - 1</tex>, т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex>w_{i,i+1}=0</tex>,<br />
* ребро <tex>(1,n)</tex> веса <tex>0</tex>,<br />
* для всех вершин <tex>1 < i < n</tex> вес ребра <tex>(1,i) = w_{1,i+1} + i - 1</tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\sum\limits_{k=i-1}^{n-2}k</tex>.<br />
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм при подсчёте вершины <tex>i</tex> будет пересчитывать все вершины до неё (кроме первой). На <tex>1</tex> шаге в очередь положат вершины от <tex>2</tex> до <tex>n</tex>, причём вершину <tex>1</tex> из <tex>M_0</tex> больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше <tex>2</tex> уже в очереди. На <tex>3</tex> шаге алгоритм улучшит расстояние до вершины <tex>2</tex> на <tex>1</tex> (что видно из веса рёбер <tex>(1,2)</tex> и <tex>(1,3)</tex>, равных <tex>\sum\limits_{k=1}^{n-2}k</tex> и <tex>\sum\limits_{k=2}^{n-2}k</tex> соответственно), так что её добавят в <tex>M_1{''}</tex> и обработают на <tex>4</tex> шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину <tex>4</tex>, расстояние до неё, равное <tex>\sum\limits_{k=3}^{n-2}k</tex>, на <tex>2</tex> меньше, чем расстояние до <tex>2</tex> и <tex>3</tex> вершин. Их добавят в срочную очередь, но так как <tex>w_{24}-1=w_{34}</tex>, то после подсчёта вершины <tex>3</tex> вершину <tex>2</tex> снова добавят в <tex>M_1{''}</tex>. Затем дойдёт очередь до вершины <tex>5</tex>, что вызовет релаксацию предыдущих вершин <tex>2,3,4</tex>, затем прорелаксируют вершины <tex>2,3</tex>, и после вершина <tex>2</tex>. Аналогично будут происходить релаксации всех вершин при обработке вершины <tex>i</tex> из очереди <tex>M_0</tex>. Таким образом, вершину <tex>i</tex> будут добавлять в срочную очередь <tex>n-i</tex> раз (добавление вершин из очереди <tex>M_2</tex> с номером больше <tex>i</tex>) <tex>+</tex> количество добавлений "старшей" вершины <tex>i+1</tex>. Количество добавлений вершины <tex>i</tex> составит <tex>1 + \sum\limits_{k=1}^{n-i}k</tex>, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт оценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49881Алгоритм Левита2015-11-13T18:15:49Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
Для хранения вершин используем следующие структуры данных:<br />
* <tex>M_0</tex> {{---}} [[Хеш-таблица|хеш-таблица]],<br />
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],<br />
* <tex>M_2</tex> {{---}} [[Хеш-таблица|хеш-таблица]].<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.<br />
<br />
В плохих случаях алгоритм Левита работает за <tex>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с такими рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:<br />
* для все вершин <tex>1 < i < j \leqslant n</tex> вес ребра <tex>(i,j) = j - i - 1</tex>, т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex>w_{i,i+1}=0</tex>,<br />
* ребро <tex>(1,n)</tex> веса <tex>0</tex>,<br />
* для всех вершин <tex>1 < i < n</tex> вес ребра <tex>(1,i) = w_{1,i+1} + i - 1</tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\sum\limits_{k=i-1}^{n-2}k</tex>.<br />
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм при подсчёте вершины <tex>i</tex> будет пересчитывать все вершины до неё (кроме первой). На <tex>1</tex> шаге в очередь положат вершины от <tex>2</tex> до <tex>n</tex>, причём вершину <tex>1</tex> из <tex>M_0</tex> больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше <tex>2</tex> уже в очереди. На <tex>3</tex> шаге алгоритм улучшит расстояние до вершины <tex>2</tex> на <tex>1</tex> (что видно из веса рёбер <tex>(1,2)</tex> и <tex>(1,3)</tex>, равных <tex>\sum\limits_{k=1}^{n-2}k</tex> и <tex>\sum\limits_{k=2}^{n-2}k</tex> соответственно), так что её добавят в <tex>M_1{''}</tex> и обработают на <tex>4</tex> шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину <tex>4</tex>, расстояние до неё, равное <tex>\sum\limits_{k=3}^{n-2}k</tex>, на <tex>2</tex> меньше, чем расстояние до <tex>2</tex> и <tex>3</tex> вершин. Их добавят в срочную очередь, но так как <tex>w_{24}-1=w_{34}</tex>, то после подсчёта вершины <tex>3</tex> вершину <tex>2</tex> снова добавят в <tex>M_1{''}</tex>. Затем дойдёт очередь до вершины <tex>5</tex>, что вызовет релаксацию предыдущих вершин <tex>2,3,4</tex>, затем прорелаксируют вершины <tex>2,3</tex>, и после вершина <tex>2</tex>. Аналогично будут происходить релаксации всех вершин при обработке вершины <tex>i</tex> из очереди <tex>M_0</tex>. Таким образом, вершину <tex>i</tex> будут добавлять в срочную очередь <tex>n-i</tex> раз (добавление вершин из очереди <tex>M_2</tex> с номером больше <tex>i</tex>) <tex>+</tex> количество добавлений "старшей" вершины <tex>i+1</tex>. Количество добавлений вершины <tex>i</tex> составит <tex>1 + \sum\limits_{k=1}^{n-i}k</tex>, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт оценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49880Алгоритм Левита2015-11-12T19:41:19Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
Для хранения вершин используем следующие структуры данных:<br />
* <tex>M_0</tex> {{---}} [[Хеш-таблица|хеш-таблица]],<br />
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],<br />
* <tex>M_2</tex> {{---}} [[Хеш-таблица|хеш-таблица]].<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:<br />
* ребро <tex>(1,</tex> <tex>2n + 1)</tex> веса <tex>2^{n/2}</tex>,<br />
* для нечётных вершин <tex>i</tex> : <tex>2n+1 \leqslant i \leqslant 3n</tex> идёт ребро <tex>(i,i+2)</tex> веса <tex>2^{(3n-i)/2}</tex>,<br />
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.<br />
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером <tex>2</tex> (после нескольких шагов вершинам от <tex>2</tex> до <tex>2n + 1</tex> алгоритм сделает веса равными <tex>0</tex>) и с номером <tex>2n + 1</tex> (через такое же число шагов вершинам от <tex>2n + 2</tex> до <tex>3n</tex> будет задан вес <tex>2^{n/2}</tex>). Оставшиеся <tex>n-2</tex> вершины, находящиеся в очереди <tex>M_0</tex>, образуют последовательность маленьких циклов длины <tex>3</tex>, в которых два ребра нулевого веса. Каждый такой цикл увеличит количество добавлений следующих двух вершин в <tex>M_1{''}</tex> на <tex>1</tex>. Алгоритм будет часто пересчитывать расстояние до последних вершин, так как их часто добавляли в <tex>M_1{''}</tex>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49879Алгоритм Левита2015-11-12T19:28:47Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
Для хранения вершин используем следующие структуры данных:<br />
* <tex>M_0</tex> {{---}} хэш-сет,<br />
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],<br />
* <tex>M_2</tex> {{---}} хэш-сет.<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:<br />
* ребро <tex>(1,</tex> <tex>2n + 1)</tex> веса <tex>2^{n/2}</tex>,<br />
* для нечётных вершин <tex>i</tex> : <tex>2n+1 \leqslant i \leqslant 3n</tex> идёт ребро <tex>(i,i+2)</tex> веса <tex>2^{(3n-i)/2}</tex>,<br />
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.<br />
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером <tex>2</tex> (после нескольких шагов вершинам от <tex>2</tex> до <tex>2n + 1</tex> алгоритм сделает веса равными <tex>0</tex>) и с номером <tex>2n + 1</tex> (через такое же число шагов вершинам от <tex>2n + 2</tex> до <tex>3n</tex> будет задан вес <tex>2^{n/2}</tex>). Оставшиеся <tex>n-2</tex> вершины, находящиеся в очереди <tex>M_0</tex>, образуют последовательность маленьких циклов длины <tex>3</tex>, в которых два ребра нулевого веса. Каждый такой цикл увеличит количество добавлений следующих двух вершин в <tex>M_1{''}</tex> на <tex>1</tex>. Алгоритм будет часто пересчитывать расстояние до последних вершин, так как их часто добавляли в <tex>M_1{''}</tex>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49796Алгоритм Левита2015-11-08T14:10:31Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Для хранения вершин используем следующие структуры данных:<br />
* <tex>M_0</tex> {{---}} хэш-сет,<br />
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],<br />
* <tex>M_2</tex> {{---}} хэш-сет.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:<br />
* ребро <tex>(1,</tex> <tex>2n + 1)</tex> веса <tex>2^{n/2}</tex>,<br />
* для нечётных вершин <tex>i</tex> : <tex>2 \cdot n+1 \leqslant i \leqslant 3n</tex> идёт ребро <tex>(i,i+2)</tex> веса <tex>2^{(3n-i)/2}</tex>,<br />
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.<br />
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером <tex>2</tex> (после нескольких шагов вершинам от <tex>2</tex> до <tex>2n + 1</tex> алгоритм сделает веса равными <tex>0</tex>) и с номером <tex>2n + 1</tex> (через такое же число шагов вершинам от <tex>2n + 2</tex> до <tex>3n</tex> будет задан вес <tex>2^{n/2}</tex>). Оставшиеся <tex>n-2</tex> вершины находятся в очереди <tex>M_0</tex>, алгоритм начнёт часто пересчитывать их вес, что приведёт к их многократному добавлению в <tex>M_1{''}</tex>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49789Алгоритм Левита2015-11-08T11:04:15Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3\cdot n</tex> вершинами и такими рёбрами: от вершины <tex>1</tex> до <tex>n</tex> ребро веса <tex>2^n</tex>, цепь <tex>n-1</tex> рёбер через одну вершину (<tex>n</tex>, <tex>n+2</tex> <tex>...</tex> <tex>3 \cdot n</tex>; вес <tex>i</tex>-ого звена <tex>2^{n-i}</tex>), а также цепь рёбер от <tex>1</tex> до <tex>3 \cdot n</tex> (вес каждого звена <tex>0</tex>). Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет постепенно улучшать расстояние до последней вершины, пересчитывая его огромное число раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49781Алгоритм Левита2015-11-07T18:21:02Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.add(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex><br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v</tex> <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.add(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает очень долго. Например, в полном графе <tex>K_n</tex> с достаточно большим <tex>n</tex> и весами <tex>w_{uv} =<br />
\begin{cases}<br />
v - u - 1, & u > 1\\<br />
w_{un}\cdot2, & u = 1, v = n - 1 \\<br />
n-2, & u = 1, v = n\\<br />
w_{uv+1} + v - u, & u = 1, v < n-1<br />
\end{cases}</tex>, рёбра идут в [[Лексикографический порядок|лексикографическом порядке]]. Добавление вершины <tex>i</tex> в очередь и последующая её обработка влекут добавление из <tex>M_0</tex> в <tex>M_1{''}</tex> всех её предыдущих вершин, начиная со <tex>2</tex>-ой; дойдя до вершины <tex>i-1</tex>, в <tex>M_1{''}</tex> снова добавятся вершины меньше <tex>i-1</tex> (кроме первой). Таким образом, вершину <tex>i</tex> добавят в <tex>M_1{''}</tex> <tex dpi="130">\sum\limits_{k=1}^{n-i}k = \dfrac 12\cdot(n-i)\cdot(n-i+1)</tex> раз, всего в <tex>M_1{''}</tex> будет <tex>\dfrac 16\cdot n\cdot(n^2-3n+2)</tex> добавлений. В очень плохих случаях вершина <tex>i</tex> может помещаться в очередь <tex>M_1{''}</tex> до <tex>2^{n-i}</tex> раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники информации==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49778Алгоритм Левита2015-11-07T15:52:18Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь,<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь;<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,<br />
* <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.push(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''int''' <tex>u</tex><br />
'''if''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u = M_1^{''}</tex>.pop()<br />
'''else'''<br />
<tex>u = M_1{'}</tex>.pop()<br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' v <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.push(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В плохих случаях алгоритм Левита работает очень долго. Например, в полном графе <tex>K_n</tex> с достаточно большим <tex>n</tex> и весами <tex>w_{uv} =<br />
\begin{cases}<br />
v - u - 1, & u > 1\\<br />
w_{un}\cdot2, & u = 1, v = n - 1 \\<br />
n-2, & u = 1, v = n\\<br />
w_{uv+1} + v - u, & u = 1, v < n-1<br />
\end{cases}</tex>, рёбра идут в [[Лексикографический порядок|лексикографическом порядке]]. Добавление вершины <tex>i</tex> в очередь и последующая её обработка влекут добавление из <tex>M_0</tex> в <tex>M_1{''}</tex> всех её предыдущих вершин, начиная со <tex>2</tex>-ой; дойдя до вершины <tex>i-1</tex>, в <tex>M_1{''}</tex> снова добавятся вершины меньше <tex>i-1</tex> (кроме первой). Таким образом, вершину <tex>i</tex> добавят в <tex>M_1{''}</tex> <tex dpi="130">\sum\limits_{k=1}^{n-i}k = \dfrac 12\cdot(n-i)\cdot(n-i+1)</tex> раз, всего в <tex>M_1{''}</tex> будет <tex>\dfrac 16\cdot n\cdot(n^2-3n+2)</tex> добавлений. В очень плохих случаях вершина <tex>i</tex> может помещаться в очередь <tex>M_1{''}</tex> до <tex>2^{n-i}</tex> раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники ==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm e-maxx — Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49765Алгоритм Левита2015-11-06T19:44:16Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно)<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:<br />
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>)<br />
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex><br />
* <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>.<br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex><br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' <tex>u : u \in V</tex><br />
<tex>d[u] = \infty</tex><br />
<tex>d[s] = 0</tex><br />
<tex>M_1^{'}</tex>.push(<tex>s</tex>)<br />
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex><br />
<tex>M_2</tex>.push(<tex>u</tex>)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''int''' <tex>u</tex><br />
'''if''' <tex>M_1^{''} \neq \varnothing</tex><br />
<tex>u = M_1^{''}</tex>.pop()<br />
'''else'''<br />
<tex>u = M_1{'}</tex>.pop()<br />
'''for''' <tex>v : uv \in E</tex><br />
'''if''' <tex>v \in M_2</tex><br />
<tex>M_1^{'}</tex>.push(<tex>v</tex>)<br />
<tex>M_2</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' v <tex>\in M_1</tex><br />
<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)<br />
'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(<tex>v</tex>)<br />
<tex>M_0</tex>.remove(<tex>v</tex>)<br />
<tex>d[v] = d[u] + w_{uv}</tex><br />
<tex>M_0</tex>.push(<tex>u</tex>)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В худшем случае алгоритм Левита работает за экспоненциальное время. Например, в полном графе <tex>K_n</tex> с достаточно большим n и весами <tex>w_{uv} =<br />
\begin{cases}<br />
v - u - 1, & u > 1; u = 1 и v = n\\<br />
w_{un}*2, & u = 1, v = n - 1 \\<br />
w_{uv+1} + v - u, & u = 1, v < n-1<br />
\end{cases}</tex>, рёбра идут в [[Лексикографический порядок|лексикографическом порядке]]. Добавление <tex>i</tex>-ой вершины в очередь и последующая её обработка влекут добавление из <tex>M_0</tex> в <tex>M_1{''}</tex> всех её предыдущих вершин, начиная со <tex>2</tex>-ой; дойдя до вершины <tex>i-1</tex>, в <tex>M_1{''}</tex> снова добавятся вершины меньше <tex>i-1</tex>-ой (кроме первой). Таким образом, количество добавлений <tex>i</tex>-ой вершины в <tex>M_1{''}</tex> составит <tex dpi="130">\sum\limits_{k=1}^{n-i} k</tex> раз. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
==См. также==<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Обход в ширину]]<br />
<br />
== Источники ==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]<br />
* [http://e-maxx.ru/algo/levit_algorithm e-maxx — Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49735Алгоритм Левита2015-11-06T08:59:51Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно)<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две очереди:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:<br />
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>)<br />
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex><br />
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex><br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' u : u <tex>\in V</tex><br />
d[v] <tex>\leftarrow \infty</tex><br />
d[s] <tex>\leftarrow 0</tex><br />
<tex>M_1^{'}</tex>.push(s)<br />
'''for''' u : u <tex>\neq</tex> s '''and''' uv <tex>\in V</tex><br />
<tex>M_2</tex>.push(u)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''if''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''int''' u <tex>=</tex> <tex>M_1^{''}</tex>.pop()<br />
'''else :'''<br />
'''int''' u <tex>=</tex> <tex>M_1{'}</tex>.pop()<br />
'''for''' v : uv <tex>\in E</tex><br />
'''if''' v <tex>\in M_2</tex><br />
<tex>M_1^{'}</tex>.push(v)<br />
<tex>M_2</tex>.remove(v)<br />
d[v] <tex>=</tex> min(d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_1</tex><br />
d[v] = min(d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_0</tex> '''and''' d[v] <tex>></tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(v)<br />
<tex>M_0</tex>.remove(v)<br />
d[v] <tex>=</tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_0</tex>.push(u)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В худшем случае алгоритм Левита работает за экспоненциальное время, например в полном графе <tex>K_n</tex> с достаточно большим n и весами <tex>w_{uv} =<br />
\begin{cases}<br />
0, & u > 1 \\<br />
n - v + 1, & u = 1 \\<br />
\end{cases}</tex> при обработке <tex>i</tex>-ой вершины из множества <tex>M_2</tex> будет происходить релаксация <tex>i-1</tex> рёбер и их добавление в срочную <tex>M_1{''}</tex> очередь.Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
== Источники ==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия]<br />
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49734Алгоритм Левита2015-11-05T19:54:06Z<p>Lehanyich: /* Псевдокод */</p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно)<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две очереди:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:<br />
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>)<br />
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex><br />
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex><br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' u : u <tex>\in V</tex><br />
d[v] <tex>\leftarrow \infty</tex><br />
d[s] <tex>\leftarrow 0</tex><br />
<tex>M_1^{'}</tex>.push(s)<br />
'''for''' u : u <tex>\neq</tex> s '''and''' uv <tex>\in V</tex><br />
<tex>M_2</tex>.push(u)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''if''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''int''' u <tex>=</tex> <tex>M_1^{''}</tex>.pop()<br />
'''else :'''<br />
'''int''' u <tex>=</tex> <tex>M_1{'}</tex>.pop()<br />
'''for''' v : uv <tex>\in E</tex><br />
'''if''' v <tex>\in M_2</tex><br />
<tex>M_1^{'}</tex>.push(v)<br />
<tex>M_2</tex>.remove(v)<br />
d[v] <tex>=</tex> min(d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_1</tex><br />
d[v] = min(d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_0</tex> '''and''' d[v] <tex>></tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(v)<br />
<tex>M_0</tex>.remove(v)<br />
d[v] <tex>=</tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_0</tex>.push(u)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В худшем случае алгоритм Левита работает за экспоненциальное время. Достаточно рассмотреть полный граф <tex>K_n</tex> с достаточно большим n и такими весами, что: <tex>w_{uv} = 0</tex>, если <tex>u \neq 1</tex> и <tex>w_{uv} = n - v + 2</tex>, если <tex>u = 1</tex>.Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
== Источники ==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия]<br />
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyichhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0&diff=49733Алгоритм Левита2015-11-05T19:51:05Z<p>Lehanyich: </p>
<hr />
<div>'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.<br />
<br />
== Алгоритм ==<br />
<br />
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.<br />
<br />
Разделим вершины на три множества:<br />
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно)<br />
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две очереди:<br />
# <tex>M_1^{'}</tex> {{---}} основная очередь<br />
# <tex>M_1^{''}</tex> {{---}} срочная очередь<br />
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено<br />
<br />
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).<br />
<br />
<br />
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:<br />
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>)<br />
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex><br />
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex><br />
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.<br />
<br />
<br />
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.<br />
<br />
== Псевдокод ==<br />
<br />
'''for''' u : u <tex>\in V</tex><br />
d[v] <tex>\leftarrow \infty</tex><br />
d[s] <tex>\leftarrow 0</tex><br />
<tex>M_1^{'}</tex>.push(s)<br />
'''for''' u : u <tex>\neq</tex> s '''and''' uv <tex>\in V</tex><br />
<tex>M_2</tex>.push(u)<br />
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''if''' <tex>M_1^{''} \neq \varnothing</tex><br />
'''int''' u <tex>=</tex> <tex>M_1^{''}</tex>.pop()<br />
'''else :'''<br />
'''int''' u <tex>=</tex> <tex>M_1{'}</tex>.pop()<br />
'''for''' v : uv <tex>\in E</tex><br />
'''if''' v <tex>\in M_2</tex><br />
<tex>M_1^{'}</tex>.push(v)<br />
<tex>M_2</tex>.remove(v)<br />
d[v] <tex>=</tex> min(d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_1</tex><br />
d[v] = min(d[v], d[u] + <tex>w_{uv}</tex>)<br />
'''if''' v <tex>\in M_0</tex> '''and''' d[v] <tex>></tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_1^{''}</tex>.push(v)<br />
<tex>M_0</tex>.remove(v)<br />
d[v] <tex>=</tex> d[u] <tex>+</tex> <tex>w_{uv}</tex><br />
<tex>M_0</tex>.push(u)<br />
<br />
== Доказательство ==<br />
<br />
{{Лемма<br />
|statement= Алгоритм отработает за конечное время<br />
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной<br />
|proof= Предположим обратное. Тогда рассмотрим 2 случая:<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть<br />
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст<br />
Противоречие.<br />
}}<br />
<br />
<br />
Из двух предыдущих лемм напрямую следует корректность алгоритма.<br />
<br />
== Сложность ==<br />
<br />
В худшем случае алгоритм Левита работает за экспоненциальное время. Достаточно рассмотреть полный граф <tex>K_n</tex> с достаточно большим n и такими весами, что: <tex>w_{uv} = 0</tex>, если <tex>u \neq 1</tex> и <tex>w_{uv} = n - v + 2</tex>, если <tex>u = 1</tex>.Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].<br />
<br />
== Источники ==<br />
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия]<br />
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита]<br />
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Кратчайшие пути в графах]]</div>Lehanyich