Задача

Имеется множество точек V = {vp v2, ..., vn}; требуется построить для них коммуника- ционную сеть. Сеть должна быть связной (то есть в ней должен существовать путь между любой парой узлов), но при соблюдении этого требования сеть должна быть построена с минимальными затратами.

Для некоторых пар (v., v) можно построить прямой канал с определенными затратами c(v., v) > 0. Таким образом, множество всех возможных каналов пред- ставляется графом G = (V, E), в котором с каждым ребром e = (v., v) связывается положительная стоимость с . Задача заключается в нахождении такого подмно- жества ребер T Έ E, чтобы граф (V, T) был связным, а общая стоимость была как можно меньшей. (Предполагается, что полный граф G является связным; в противном случае решение невозможно.)

Ниже приведено базовое наблюдение.

(4.16) Пусть T — решение описанной выше задачи проектирования сети с ми- нимальной стоимостью. В этом случае (V, T) является деревом.

Доказательство. По определению граф (V, T) должен быть связным; мы по- кажем, что он также не содержит циклов. Предположим, граф содержит цикл C, а e — любое ребро C. Утверждается, что граф (V, T- {e}) остается связным, потому что любой путь, который использовал ребро e, теперь может воспользоваться «обходным путем» по оставшейся части цикла C. Из этого следует, что (V, T- {e}) также является действительным решением задачи, и при этом оно имеет меньшую стоимость, — обнаружено противоречие. ■

Если допустить, что некоторые ребра могут иметь нулевую стоимость (то есть предполагается лишь то, что значения ce не отрицательны), то решение задачи проектирования сети с минимальной стоимостью может содержать лишние ре- бра — такие ребра имеют нулевую стоимость и при желании могут быть удалены.

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

Подмножество T !Ξ E будет называться остовным деревом графа G, если (V, T) является деревом. Утверждение (4.16) указывает на то, что цель задачи проек- тирования сети можно переформулировать как задачу поиска остовного дерева графа с минимальной стоимостью; по этой причине эта задача обычно называется задачей нахождения минимального остовного дерева. Во всех графах G, кроме очень простых, количество разных остовных деревьев растет по экспоненциальному закону, а их структуры могут сильно отличаться друг от друга. Совершенно непо- нятно, как эффективно найти дерево с минимальной стоимостью среди всех этих вариантов.

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача