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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 18 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
==Теорема==
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
о декомпозиции потока
+
о декомпозиции
 
|statement=
 
|statement=
Любой поток <tex>f</tex> [[Определение сети, потока|транспортной сети]] <tex>G = (V, E)</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов. При этом все пути и циклы имеет положительный поток.
+
Пусть <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> — константы.
 
|proof=
 
|proof=
Пусть <tex>s</tex> - исток, <tex>t</tex> - сток потока <tex>f</tex>. Если поток ненулевой, то из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>s</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>v_j, j < i</tex> или <tex>s</tex> (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для всех вершин. Итак, поскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.
+
Пусть <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> таких операций.
 
}}
 
}}
 +
 +
==Алгоритм==
 +
Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть <tex>G = (V, E)</tex>):
 +
 +
===Псевдокод===
 +
'''function''' simpleDecomposition(<tex>s</tex>):
 +
    <tex> Q = \varnothing</tex>                      <font color=green>// множество пройденных рёбер</font>
 +
    <tex> P = \varnothing </tex>                      <font color=green>// множество посещённых вершин</font>
 +
    <tex>v = s</tex>
 +
    '''while''' <tex> v \notin P </tex>
 +
        '''if''' <tex> v = t </tex>
 +
            '''break'''
 +
        edge <tex>e = \varnothing</tex>
 +
        '''for''' <tex>u : (v,u) \in E</tex>
 +
            '''if''' <tex> f(v,u)>0 </tex>
 +
                <tex>e = (v,u)</tex>
 +
                '''break'''
 +
        '''if''' <tex>e = \varnothing</tex>
 +
            '''return''' <tex>\varnothing</tex>
 +
        <tex> Q</tex>.push_back(<tex>e</tex>)
 +
        <tex> P = P \cup \{v\}</tex>
 +
        <tex> v = u </tex>
 +
    '''if''' <tex>v \in P </tex>                    <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все рёбра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font>
 +
        '''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>)
 +
            <tex>Q</tex>.pop_front()
 +
    <tex>f(Q) = f(Q)</tex> - <tex>\min\limits_{(u,v) \in Q}f(u,v) </tex>
 +
    '''return''' <tex>(f, Q)</tex>
 +
 +
'''function''' fullDecomposition():
 +
    <tex> d = \varnothing </tex>                      <font color=green>// собственно, декомпозиция графа: совокупность подмножеств, которые являются путями/циклами, и их поток</font>
 +
    <tex>p = </tex> simpleDecomposition(<tex>s</tex>)  <font color=green>// один из путей/циклов в графе и его поток</font>
 +
    '''while''' (<tex>p \neq \varnothing</tex>)
 +
        <tex> d = d \cup p </tex>
 +
        <tex>p = </tex> simpleDecomposition(<tex>s</tex>)
 +
    '''for''' <tex> u \in V </tex>
 +
        <tex>p = </tex> simpleDecomposition(<tex>u</tex>)
 +
        '''while''' (<tex>p \neq \varnothing</tex>)
 +
            <tex> d = d \cup \{p\} </tex>
 +
            <tex>p = </tex> simpleDecomposition(<tex>u</tex>)
 +
  '''return''' <tex>d</tex>
 +
 +
===Анализ работы алгоритма===
 +
{{Утверждение
 +
|statement=
 +
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно <tex>O(VE)</tex>.
 +
|proof=
 +
Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно, поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}
 +
 +
==Источники==
 +
* ''Ravindra Ahuja, Thomas Magnanti, James Orlin'' — '''Network flows''' — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке ]]

Версия 17:50, 21 января 2017

Теорема

Теорема (о декомпозиции):
Пусть [math]G = (V, E)[/math]транспортная сеть, [math]f[/math]поток в [math]G[/math]. Тогда [math]|f|[/math] можно представить в виде совокупности [math]O(E)[/math] путей из истока в сток и циклов: [math]|f| = \sum\limits_{i=1}^{}c_{i}\cdot f(p_{i}) + \sum\limits_{j=1}^{}d_{j}\cdot f(k_{j})[/math], где [math]p_{i}[/math] — путь из [math]s[/math] в [math]t[/math], [math]k_{j}[/math] — цикл, [math]c_{i}[/math] и [math]d_{j}[/math] — константы.
Доказательство:
[math]\triangleright[/math]
Пусть [math]s[/math] — исток, [math]t[/math] — сток сети [math]G[/math]. Пусть из [math]s[/math] выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину [math]v_1[/math]. Если [math]v_1[/math] совпадает с [math]t[/math], то найденный путь является путем из [math]s[/math] в [math]t[/math], иначе по закону сохранения потока для вершины [math]v_1[/math] из неё должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину [math]v_2[/math]. Будем продолжать этот процесс до тех пор, пока [math]v_i[/math] не совпадет с [math]t[/math] (найден путь [math]p_{i}[/math] из [math]s[/math] в [math]t[/math]) либо с одной из ранее посещенных вершин (найден цикл [math]k_{j}[/math]). Данный путь (цикл) будет иметь положительный поток [math]f[/math]([math]p_{i}[/math]) или [math]f[/math]([math]k_{j}[/math]), равный минимальному среди потоков по всем рёбрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину [math]f[/math]([math]p_{i}[/math]) или [math]f[/math]([math]k_{j}[/math]), получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из [math]s[/math] не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем рёбрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из рёбер обнулится, следовательно, для полного представления потока потребуется не более [math]E[/math] таких операций.
[math]\triangleleft[/math]

Алгоритм

Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода (на вход подается сеть [math]G = (V, E)[/math]):

Псевдокод

function simpleDecomposition([math]s[/math]):
    [math] Q = \varnothing[/math]                      // множество пройденных рёбер
    [math] P = \varnothing [/math]                      // множество посещённых вершин
    [math]v = s[/math]
    while [math] v \notin P [/math]
        if [math] v = t [/math]
            break
        edge [math]e = \varnothing[/math]
        for [math]u : (v,u) \in E[/math]
            if [math] f(v,u)\gt 0 [/math]
                [math]e = (v,u)[/math]
                break
        if [math]e = \varnothing[/math]
            return [math]\varnothing[/math]
        [math] Q[/math].push_back([math]e[/math])
        [math] P = P \cup \{v\}[/math]
        [math] v = u [/math]
    if [math]v \in P [/math]                    // нашли цикл, удаляем из [math]Q[/math] все рёбра, найденные до того, как [math]v[/math] была включена в [math]P[/math]
        while ([math]Q[/math].begin.from [math]\neq[/math] [math]v[/math])
            [math]Q[/math].pop_front()
    [math]f(Q) = f(Q)[/math] - [math]\min\limits_{(u,v) \in Q}f(u,v) [/math]
    return [math](f, Q)[/math]

function fullDecomposition():
    [math] d = \varnothing [/math]                       // собственно, декомпозиция графа: совокупность подмножеств, которые являются путями/циклами, и их поток
    [math]p = [/math] simpleDecomposition([math]s[/math])  // один из путей/циклов в графе и его поток
    while ([math]p \neq \varnothing[/math])
        [math] d = d \cup p [/math]
        [math]p = [/math] simpleDecomposition([math]s[/math])
    for [math] u \in V [/math]
        [math]p = [/math] simpleDecomposition([math]u[/math])
        while ([math]p \neq \varnothing[/math])
            [math] d = d \cup \{p\} [/math]
            [math]p = [/math] simpleDecomposition([math]u[/math])
  return [math]d[/math]

Анализ работы алгоритма

Утверждение:
Время работы алгоритма поиска декомпозиции потока, описанного выше, равно [math]O(VE)[/math].
[math]\triangleright[/math]
Действительно, каждый путь (цикл) содержит не более [math]V[/math] вершин, следовательно, поиск пути (цикла) работает за [math]O(V)[/math]. Т. к. декомпозиция потока содержит [math]O(E)[/math] путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено [math]O(E)[/math] поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит [math]O(VE)[/math].
[math]\triangleleft[/math]

Источники

  • Ravindra Ahuja, Thomas Magnanti, James OrlinNetwork flows — Prentice-Hall, Inc. Upper Saddle River, New Jersey, 1993.