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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le c_{2}V^2</tex>, существует [[Определение сети, потока|сеть]] <tex>G</tex> с <tex>V</tex> вершинами и <tex>E</tex> ребрами. При этом для любого максимального потока <tex>f</tex> в <tex>G</tex>, любая его остаточная декомпозиция должна содержать <tex>\Omega (E)</tex> слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину <tex>\Omega (V)</tex>.
 
Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le c_{2}V^2</tex>, существует [[Определение сети, потока|сеть]] <tex>G</tex> с <tex>V</tex> вершинами и <tex>E</tex> ребрами. При этом для любого максимального потока <tex>f</tex> в <tex>G</tex>, любая его остаточная декомпозиция должна содержать <tex>\Omega (E)</tex> слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину <tex>\Omega (V)</tex>.
 
|proof=
 
|proof=
[[Файл:example.png|300px|thumb|right|Пример для <tex>V = 16</tex>, в который надо добавить нужное количество ребер]]
+
[[Файл:example.png|200px|thumb|right|Пример для <tex>V = 16</tex>, в который надо добавить нужное количество ребер]]
Используются <tex>c_{1} = 1</tex> и <tex>c_{2} = \frac{1}{9}</tex>. Чтобы получить искомую сеть, строится сеть, изображенный на рисунке, после чего добавляются недостающие ребра (из <tex>A</tex> в <tex>B</tex>). Пропускные способности ребер из <tex>A</tex> в <tex>B</tex> равны <tex>1</tex>, остальных — <tex>+\infty</tex> (или просто достаточно большое число, например, <tex>V^2</tex>).
+
<div>Используются <tex>c_{1} = 1</tex> и <tex>c_{2} = \frac{1}{9}</tex> (<tex>V \le E \le \frac{V^2}{9}</tex>). Чтобы получить искомую сеть, строится сеть, изображенный на рисунке, после чего добавляются недостающие ребра (из <tex>A</tex> в <tex>B</tex>). Пропускные способности ребер из <tex>A</tex> в <tex>B</tex> равны <tex>1</tex>, остальных — <tex>+\infty</tex> (или просто достаточно большое число, например, <tex>V^2</tex>).</div>
 +
Теперь докажем саму теорему:
 +
* Максимальный поток по модулю равен потоку через разрез, который разделяет <tex>A</tex> и <tex>B</tex> (т.е. пересекает все ребра с пропускной способностью <tex>1</tex>). Поток по каждому пути в декомпозиции не превышает 1, а значит, этих путей не меньше, чем ребер между <tex>A</tex> и <tex>B</tex>, а их <tex>\Omega (E)</tex>.
 +
* По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>(n-2[\frac{n-1}{3}]+1)</tex> ребер, что является <tex>\Omega (V)</tex>.
 
}}
 
}}

Версия 20:44, 20 декабря 2010

Теорема (о декомпозиционном барьере):
Существуют положительные вещественные числа [math]c_{1}[/math] и [math]c_{2}[/math], такие что для любых натуральных [math]V[/math] и [math]E[/math], удовлетворяющих неравенствам [math]c_{1}V \le E \le c_{2}V^2[/math], существует сеть [math]G[/math] с [math]V[/math] вершинами и [math]E[/math] ребрами. При этом для любого максимального потока [math]f[/math] в [math]G[/math], любая его остаточная декомпозиция должна содержать [math]\Omega (E)[/math] слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину [math]\Omega (V)[/math].
Доказательство:
[math]\triangleright[/math]
Пример для [math]V = 16[/math], в который надо добавить нужное количество ребер
Используются [math]c_{1} = 1[/math] и [math]c_{2} = \frac{1}{9}[/math] ([math]V \le E \le \frac{V^2}{9}[/math]). Чтобы получить искомую сеть, строится сеть, изображенный на рисунке, после чего добавляются недостающие ребра (из [math]A[/math] в [math]B[/math]). Пропускные способности ребер из [math]A[/math] в [math]B[/math] равны [math]1[/math], остальных — [math]+\infty[/math] (или просто достаточно большое число, например, [math]V^2[/math]).

Теперь докажем саму теорему:

  • Максимальный поток по модулю равен потоку через разрез, который разделяет [math]A[/math] и [math]B[/math] (т.е. пересекает все ребра с пропускной способностью [math]1[/math]). Поток по каждому пути в декомпозиции не превышает 1, а значит, этих путей не меньше, чем ребер между [math]A[/math] и [math]B[/math], а их [math]\Omega (E)[/math].
  • По построению сети, любой путь из [math]s[/math] в [math]t[/math] содержит хотя бы [math](n-2[\frac{n-1}{3}]+1)[/math] ребер, что является [math]\Omega (V)[/math].
[math]\triangleleft[/math]