Отказ от предположения о различной стоимости всех ребер

До настоящего момента предполагалось, что все стоимости ребер различны; такое предположение упростило анализ в ряде мест. Но предположим, имеется экзем- пляр задачи минимального остовного дерева, которого некоторые ребра имеют одинаковую стоимость, — как убедиться в том, что рассмотренные алгоритмы по- прежнему обеспечивают оптимальные решения?

Оказывается, существует простой способ: нужно взять граф и изменить все сто- имости ребер на разные, очень малые величины, чтобы все они стали различными. Теперь любые две стоимости, которые различались изначально, будут находиться в том же относительном порядке, поскольку отклонения очень малы; а раз все наши алгоритмы базируются на простом сравнении стоимости ребер, отклонения позволят разрешить конфликты при сравнении ребер со стоимостями, которые до этого были одинаковыми.

Более того, можно утверждать, что любое минимальное остовное дерево T для нового, измененного экземпляра также должно являться минимальным остовным деревом для исходного экземпляра. Убедиться в этом несложно: если стоимость T больше стоимости некоторого дерева T* в исходном экземпляре, то для достаточно малых отклонений изменение стоимости T не может быть достаточным, чтобы оно стало лучше T* с новыми стоимостями. Таким образом, при выполнении любого из наших алгоритмов минимального остовного дерева с измененными стоимостями для сравнения ребер будет получено минимальное остовное дерево T, которое также является оптимальным для исходного экземпляра.

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

Еще по теме Отказ от предположения о различной стоимости всех ребер:

  1. Стоимость
  2. 2.2.2. Налог на добавленную стоимость
  3. 1.5.2. Налог на добавленную стоимость
  4. § 54 Исполнители завещания. – Общие и отдельные отказы. – Законная мера отказа. – Вступление в силу отдельного отказа. – Отмена завещания. – Открытие, оглашение и явка. – Истолкование завещания. – Законная доля. – Лишение наследства. – Завещательное наследство в прибалтийских губерниях. – Мусульманское завещание.
  5. § 8. Право получения ликвидационной стоимости (п. 2258-2260)
  6. Статья 385. Отказ свидетеля от дачи показаний или отказ эксперта или переводчика от исполнения возложенных на них обязанностей
  7. § 37 История вотчинной записки в России. – Явка актов в приказах. – Справка. – Юридическое и финансовое ее значение. – Аналогия нашей формы с западными. – Изменение старой формы при Петре I. – Новый крепостной порядок и новое значение справки и отказа. – Форма нового отказа и ввода во владение
  8. Статья 1208. Увеличение размера возмещения вреда в связи с повышением стоимости жизни и увеличением размера минимальной заработной платы
  9. § 16 Понятие о законном рождении и законных детях. – Удостоверение законности рождения. – Римское предположение о законности детей, рожденных в браке. – Постановление русского закона о сем предмете. – Право отца и родных оспаривать законность. – Отличия в иностранных законодательствах.
  10. «Журнал для всех»
  11. МЕДИТАЦИЯ «ПРОЩЕНИЕ ВСЕХ И КАЖДОГО».
  12. 5. Учитывайте в бюджете пожелания всех членов семьи.
  13. Медитация действует на всех
  14. У всех ли есть сценарий?
  15. 6. Гармония – единство различного
  16. Рождение в различных планах
  17. 2. Равенство различных форм собственности