Характеристика выбывания команды

Представленная схема построения сетевого потока также может использоваться для доказательства (7.59). Идея заключается в том, что теорема о максимальном потоке и минимальном разрезе дает удобную характеристику вида «в том и толь- ко в том случае» для существования потока; интерпретируя эту характеристику в контексте приложения, мы получим столь же удобную характеристику.
Тем самым демонстрируется общий подход к построению теорем характеризации для задач, сводимых к потоку в сети.

Доказательство (7.59). Предположим, команда z выбыла из борьбы за первое место. В этом случае максимальный поток s-t в G имеет величину g' < g*; сле- довательно, существует разрез s-t (A, B) с пропускной способностью g', и (A, B) является минимальным разрезом. Пусть T — множество команд x, для которых vx A. Теперь докажем, что T может использоваться как «усредняющий аргу- мент» в (7.59).

Сначала рассмотрим узел uxy и предположим, что х или y не входит в T, но

u ^ A. Тогда ребро (u , v ) переходит из A в B, а следовательно, разрез (A, B) об-

xy xy x

ладает бесконечной пропускной способностью. Это противоречит предположению о том, что (A, B) является минимальным разрезом с пропускной способностью менее g*. Итак, если одна из команд х или у не входит в T, то uy B. С другой

стороны, предположим, что х и у принадлежат T, но uxy B. Рассмотрим разрез (A', B'), который был бы получен добавлением uxy в множество A и удалением его из множества B. Пропускная способность (A', B') просто равна пропускной спо- собности (A, B) за вычетом пропускной способности gxy ребра (s, uxy) — потому что ребро (s, uxy) прежде переходило от A к B, а теперь не переходит от A' к B'.

Но так как gxy > 0, это означает, (A', B') обладает меньшей пропускной способностью, чем (A, B), что снова противоречит предположению о минимальности разреза (A, B). Итак, если x иy принадлежат T, то обе команды uxy A.

Таким образом, мы пришли к следующему заключению на основании того фак- та, что (A, B) является минимальным разрезом: uxy A в том и только в том случае, если обе команды x, y T.

А теперь остается лишь найти пропускную способность минимального разреза с(A, B) в контексте пропускных способностей составляющих ребер. Из вывода пре- дыдущего абзаца мы знаем, что ребра, переходящие из A в B, должны иметь одну из следующих двух форм:

♦ ребра в форме (vx, t), где x T, и

♦ ребра в форме (s, u), где по крайней мере один из узлов x или y не принадлежит T (другими словами, {x, y} - ) + ∑ fζ„ =r и>|Гj-∑щ +⅛* - ^ gv).

jгеГ ijr,>hiГ jrt=Г jгjεГ

Так как мы знаем, что c(A,B) = g' < g* из последнего неравенства вытекает


Например, применяя аргумент из доказательства (7.59) к экземпляру на рис. 7.21, мы видим, что узлы Нью-Йорка и Торонто расположены на стороне ис- точника относительно минимального разреза, и как было показано ранее, эти две команды действительно доказывают, что Бостон выбыл из борьбы за первое место.

7.13.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Характеристика выбывания команды:

  1. Пример настройки и реабилитации в футбольной команде
  2. Определение команды.
  3. § 4.5. Деятельность команд в организации
  4. Признаки команды.
  5. Работа с другими командами
  6. Четыре шага по созданию эффективной команды
  7. ШЕСТЬ СТУПЕНЕЙ НА ПУТИ СОЗДАНИЯ КОМАНДЫ.
  8. Кто становится лидером команды
  9. Создание деловой команды «Вероятно, я не лучший советчик в этом вопросе».
  10. Эд САЛЛИВАН. ВРЕМЯ — ДЕНЬГИ Создание команды разработчиков, программного обеспечения, 2001
  11. Методика «Характеристика ученика» Общая характеристика методики
  12. 4.1. Общая характеристика
  13. 3.1. ОБЩИЕ ХАРАКТЕРИСТИКИ
  14. § 4.4. Характеристики социальных групп