Анализ алгоритма (7.53)

В графе G', построенном описанным способом, действительная циркуляция существует в том и только в том случае, если существует действительный вариант планирования опроса.

Доказательство. Приведенное описание подсказывает способ преобразования плана опроса в соответствующий поток.

Ребро (i, j) передает одну единицу потока, если клиенту i задается вопрос о продукте j в опросе, и не передает поток в про- тивном случае. Поток в ребрах (5, i) представляет количество вопросов, заданных клиенту i, поток в ребре (j, t) — количество клиентов, которым заданы вопросы

0 продукте j, и, наконец, поток в ребре (t, 5) — общее количество заданных вопросов. Такой поток соответствует 0 потреблению, то есть в каждом узле происходит сохра- нение потока. Если опрос удовлетворяет этим правилам, то для соответствующего потока выполняются пропускные способности и нижние границы.

И наоборот, если задача циркуляции имеет действительное решение, то со- гласно (7.52) существует действительная целочисленная циркуляция, у которой имеется естественное соответствие в виде действительного плана опроса. Клиенту

1 будут заданы вопросы о продукте j в том и только том случае, если ребро (i, j) передает единицу потока.

7.9.

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

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

  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. Принципы анализа происшествия.