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

В основе анализа лежит идея о том, что целочисленные потоки G' достаточно про- зрачно кодируют паросочетания из G. Сначала предположим, что в G существует паросочетание, состоящее из к ребер (x,j>.
,(x „д ). Затем рассмотрим по- ток f отправляющий одну единицу потока по каждому пути в форме Х- , }\ — то

есть f(e) = 1 для каждого ребра на одном из этих путей. Легко убедиться в том, что ограничения пропускной способности и сохранения потока действительно выпол- няются, а f является потоком s-t с величиной к.

И наоборот, предположим, что в G' существует поток f' с величиной к. Соглас- но теореме целочисленности максимальных потоков известно, что существует целочисленный поток f с величиной к; а поскольку все пропускные способности равны 1, это означает, что для каждого ребра e значение f (e) равно 0 или 1. Теперь рассмотрим множество М' всех ребер в форме (x, y), для которых величина потока равна 1.

Множество M' обладает тремя простыми свойствами.

(7.34) M' состоит из к ребер.

Доказательство. Чтобы доказать это утверждение, рассмотрим разрез (A, B) в G' c A = {s} U X. Величина потока вычисляется как общий поток, выходящий из A, за вычетом общего потока, входящего в A. Первое из этих слагаемых попросту равно мощности M', так как ребра, выходящие из A, несут поток, причем каждое ребро не- сет ровно одну единицу потока. Второе слагаемое равно 0, так как в A нет входящих ребер. Из этого следует, что M' содержит к ребер. ■

(7.35) Каждый узел в X является начальным не более чем для одного ребра в M' . Доказательство. Чтобы доказать это утверждение, предположим, что x ^ X

является начальным узлом для минимум двух ребер в M'. Так как поток является целочисленным, это означает, что из x выходят как минимум две единицы потока. По ограничению сохранения потока в x должны входить минимум две единицы потока — но это невозможно, поскольку в x входит только одно ребро с пропускной способностью 1. А следовательно, x является начальным узлом не более чем для одного ребра в M'.

Рассуждая аналогичным образом, можно показать, что

(7.36) Каждый узел в Y является конечным не более чем для одного ребра в M'. Объединяя все эти свойства, мы видим, что при рассмотрении M' как множества

ребер в исходном двудольном графе G будет получено паросочетание с размером к. В итоге нам удалось доказать следующий факт.

(7.37) Размер максимального паросочетания в G равен величине максимально- го потока в G'; а ребрами такого паросочетания в G являются ребра, передающие поток от X к Y в G'.

Обратите внимание на важную роль, отведенную теореме целочисленности (7.14) в этом построении: мы должны были знать, существует ли в G' максималь- ный поток, состоящий только из величин 0 и 1.

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ