Задача

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

Множество путей является непересекающимся по ребрам, если их множества ре- бер не пересекаются, то есть никакие два пути не содержат ни одного общего ребра, даже если они проходят через некоторые общие узлы. Для заданного направленно- го графа G = (V, E) с двумя выделенными узлами s, t Vзадача непересекающихся по направленным ребрам путей заключается в нахождении максимального количе- ства путей s-t, непересекающихся по направленным ребрам. Задача непересекаю- щихся по ненаправленным ребрам путей заключается в нахождении максимального количества путей s-t в ненаправленном графе G. Родственный вопрос нахождения путей, непересекающихся не только ребрам, но и по узлам (разумеется, кроме узлов s и t), будет рассматриваться в упражнениях этой главы.

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

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

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