Разработка алгоритма

Как направленная, так и ненаправленная версия задачи исключительно есте- ственно решаются с использованием потоков. Начнем с направленной задачи. Для графа G = (V, E) с двумя выделенными узлами s и t мы определим потоковую сеть, в которой s и t — источник и сток соответственно, а каждое ребро имеет про- пускную способность 1.
Предположим, существуют к путей s-t, непересекающихся по ребрам. Мы можем сделать так, чтобы по каждому из таких путей передавалась одна единица потока: в каждом пути одному ребру e назначается f (e) = 1, а всем остальным ребрам — f (e’) = 0; так определяется допустимый поток с величиной к.

(7.41) Если в направленном графе G от s к t существуют к путей, непересекаю- щихся по ребрам, то величина максимального потока s-t в G не меньше к.

Предположим, мы также сможем продемонстрировать утверждение, обратное

(7.41) : если существует поток с величиной к, то существуют к путей s-t, непересе- кающихся по ребрам. Тогда мы просто сможем вычислить максимальный поток s-t в G, и объявить (обоснованно) это значение максимальным количеством непере- секающихся по ребрам путей s-t.

Начнем с доказательства этого обратного утверждения, которое позволит убе- диться в том, что метод с потоком действительно дает правильный ответ. В ходе анализа также будет получен способ извлечения к путей, непересекающихся по ребрам, из целочисленного потока, передающего к единиц из s в t. Следовательно, вычисление максимального потока в G даст не только максимальное количество путей, непересекающихся по ребрам, но и сами пути.

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

Еще по теме Разработка алгоритма:

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