Редактирование: Алгоритм Эдмондса-Карпа

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Алгоритм ==
 
== Алгоритм ==
  
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]], в которой в качестве дополняющего пути выбирается [[Обход в ширину |кратчайший по рёбрам путь]] в остаточной сети (длины всех рёбер равны <tex>1</tex>).
+
Для заданной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса-Карпа находит поток максимальной величины из заданного истока <tex>s</tex> в заданный сток <tex>t</tex> за <tex>O(V E^2)</tex>.
 
 
=== Описание ===
 
 
 
# Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.
 
# В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.
 
# Пускаем через найденный путь (он называется '''увеличивающим путём''' или '''увеличивающей цепью''') максимально возможный поток:
 
## На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью <tex>\mathrm{c_{min}}</tex>.
 
## Для каждого ребра на найденном пути увеличиваем поток на <tex>\mathrm{c_{min}}</tex>, а в противоположном ему — уменьшаем на <tex>\mathrm{c_{min}}</tex>.
 
## Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
 
# Возвращаемся на шаг 2.
 
 
 
===Сложность===
 
Сложность алгоритма Эдмондса-Карпа равна <tex>O(VE^2)</tex>.
 
  
 
== Псевдокод ==
 
== Псевдокод ==
  
  '''function''' EdmondsKarp(G, s, t):
+
  '''Edmonds_Karp''' (G, s, t)
 
     '''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
 
     '''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
         <tex>f[u,v] \leftarrow 0</tex>
+
         '''do''' <tex>f[u,v] \leftarrow 0</tex>
        <tex>f[v,u] \leftarrow 0</tex>
+
            <tex>f[v,u] \leftarrow 0</tex>
 
     '''while''' существует ''кратчайший'' путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> в остаточной сети <tex>G_f</tex>
 
     '''while''' существует ''кратчайший'' путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> в остаточной сети <tex>G_f</tex>
         <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex>
+
         '''do''' <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex>
        '''for''' <tex>(u,v) \in p</tex>
+
            '''for''' (для) каждого ребра <tex>(u,v) \in p</tex>
            <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex>
+
                '''do''' <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex>
            <tex>f[v,u] \leftarrow -f[u,v]</tex>
+
                    <tex>f[v,u] \leftarrow -f[u,v]</tex>
  
 
== Корректность алгоритма Эдмондса-Карпа ==
 
== Корректность алгоритма Эдмондса-Карпа ==
  
На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
+
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
  
 
== Оценка быстродействия ==
 
== Оценка быстродействия ==
Строка 37: Строка 24:
 
|id=lemma1
 
|id=lemma1
 
|statement=
 
|statement=
Если в сети <tex>G(V,E)</tex> с истоком <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.
+
Если в сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.
 
|proof=
 
|proof=
 
Предположим противное, пусть существует вершина <tex>v \in V \backslash\{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.
 
Предположим противное, пусть существует вершина <tex>v \in V \backslash\{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.
  
По выбору <tex>v</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \geqslant\delta_f(s,u)</tex>.
+
По выбору <tex>v</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \ge \delta_f(s,u)</tex>.
  
 
Предположим <tex>(u, v) \in E_f</tex>, тогда <tex>\delta_f(s,v) \leqslant \delta_f(s, u) + 1 \leqslant \delta'_f(s,u) + 1 = \delta'_f(s, v)</tex>. Это противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>.
 
Предположим <tex>(u, v) \in E_f</tex>, тогда <tex>\delta_f(s,v) \leqslant \delta_f(s, u) + 1 \leqslant \delta'_f(s,u) + 1 = \delta'_f(s, v)</tex>. Это противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>.
Строка 54: Строка 41:
 
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла <tex>\mathrm {while}</tex>  составляет <tex>O(V E)</tex>.
 
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла <tex>\mathrm {while}</tex>  составляет <tex>O(V E)</tex>.
 
|proof=
 
|proof=
Рассмотрим множество рёбер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные рёбра критическими. Покажем, что каждое из <tex>|E|</tex> рёбер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические рёбра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.
+
Рассмотрим множество ребер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра критическими. Покажем, что каждое из <tex>|E|</tex> ребер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические ребра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.
  
Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшено по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \leqslant \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.
+
Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \le \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \ge \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.
  
Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>\dfrac{(|V| -2)}{2} = \dfrac{|V|}{2} - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать рёбра в остаточной сети, то общее количество критических рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.  
+
Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>(|V| -2)/2 = |V|/2 - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.  
  
 
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла <tex>\mathrm {while}</tex>  рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла <tex>\mathrm {while}</tex>  также составляет <tex>O(V E)</tex>.
 
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла <tex>\mathrm {while}</tex>  рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла <tex>\mathrm {while}</tex>  также составляет <tex>O(V E)</tex>.
 
}}
 
}}
  
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.  
+
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть  "грибок"<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com  ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.
 
 
== Пример графа, на котором алгоритм дает плохую асимптотику ==
 
[[Файл:MaxFlowWorstCase.png|365px|thumb|right|«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]]
 
 
 
Заметим также, что существует ''сеть  грибок''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com  ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>. Рассмотрим этот случай более подробно. Норман Заде (англ. ''Norman Zadeh'') описал примеры, которые позволяют добиться асимптотики <tex>\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.
 
Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex>) на подмножества:
 
*<tex>S={s_1,\ldots,s_k}</tex> — множество вершин, в которые входят рёбра из <tex>s</tex> с пропускной способностью <tex>k</tex>,
 
*<tex>T={t_1,\ldots,t_k}</tex> — множество вершин, из которых исходят рёбра в <tex>t</tex> с пропускной способностью <tex>k</tex>,
 
*<tex>U={u_1,\ldots,u_{2p}}</tex> — множество вершин, достижимых из <tex>s</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра),
 
*<tex>V={v_1,\ldots,v_{2p}}</tex> — множество вершин, из которых можно достигнуть <tex>t</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра).
 
 
 
<tex>S</tex> и <tex>T</tex> содержат <tex>k</tex> вершин, <tex>U</tex> и <tex>V</tex> содержат <tex>2p</tex> вершин. Где <tex>k</tex> и <tex>p</tex> фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества <tex>S</tex> и <tex>T</tex>), имеет единичную пропускную способность; пунктирные рёбра имеют бесконечную пропускную способность; остальные рёбра(в форме дуги) имеют пропускную способность <tex>k</tex>.
 
В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные рёбра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u_1, u_2, T, S, v_2, v_1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)</tex> длины <tex>11</tex> и так далее.
 
:Число вершин в сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>.
 
:Число рёбер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>.
 
 
 
Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>.
 
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
 
 
 
[[Файл:InGraph.png|300px|thumb|left| Изначальный граф, нулевой поток]]
 
[[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
 
[[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
== См. также ==
 
*[[Определение сети, потока]]
 
*[[Обход в ширину]]
 
*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]
 
  
 
==Примечания==
 
==Примечания==
Строка 125: Строка 56:
 
<references />
 
<references />
  
== Источники информации ==
+
== Литература ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алгоритм Эдмондса-Карпа]
 
* [https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm Википедия: Алгоритм Эдмондса-Карпа (англ.)]
 
*[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Статья на TopCoder.com]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке]]
 
[[Категория: Задача о максимальном потоке]]

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

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

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

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