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

Способ организации всех полетов с использованием не более к самолетов существует в том и только в том случае, если в сети G существует действительная циркуляция.

Доказательство. Сначала предположим, что все рейсы могут быть выполнены с использованием к' < к самолетов.

Множество рейсов, выполняемых каждым отдельным самолетом, определяет путь P в сети G; по каждому такому пути P передается одна единица потока. Чтобы удовлетворить полные требования S и t, мы отправляем по ребру (5, t) к - к' единиц потока. Полученная циркуляция удовлетворяет все ограничения по уровню по- требления, пропускной способности и нижним границам.

И наоборот, рассмотрим действительную циркуляцию в сети G. Из (7.52) мы знаем, что в сети существует действительная циркуляция с целочисленными величинами потока. Предположим, что к' единиц потока передаются по ребрам, отличным от (5, t). Так как у каждого ребра пропускная способность ограничена значением 1, а циркуляция является целочисленной, каждое ребро, передающее поток, несет ровно одну единицу потока.

Преобразуем результат в расписание по схеме, похожей на приведенную в до- казательстве (7.42), где поток преобразовывался в множество пар. На самом деле в данном случае ситуация проще, потому что граф не содержит циклов. Рассмотрим ребро (5, и.), по которому передается одна единица потока. Из ограничения со- хранения потока следует, что (и., v) передает одну единицу потока, и из v выходит единственное ребро, несущее одну единицу потока. Продолжая таким образом, мы строим путь P от 5 к t, в котором каждое ребро передает одну единицу потока. Про- цесс применяется к каждому ребру в форме (5, и), передающему одну единицу по- тока; таким образом будут получены к' путей от 5 к t, каждый из которых состоит из ребер, передающих одну единицу потока. С каждым путем P, построенным по этой схеме, связывается один самолет, который может выполнять все рейсы этого пути. ■

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

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

  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. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов
  17. МЕТОД АНАЛИЗА ЖИЗНИ
  18. АНАЛИЗ ДИСПЕРСИОННЫЙ
  19. Анализ линий
  20. 4.2. Анализ одномерных распределений