Задача

Одной из первоначальных целей для разработки алгоритма нахождения макси- мального потока было решение задачи о двудольном паросочетании; сейчас вы увидите, как это делается. Напомним, что двудольным графом G = (V, E) называется ненаправленный граф, множество узлов которого можно разбить на подмножества V=X U Y, обладающее тем свойством, что один конец каждого ребра e E принад- лежит X, а другой конец принадлежит Y.
Паросочетанием M в G называется такое подмножество ребер M !Ξ E, что каждый узел не более чем в одно ребро из M.

Задача о двудольном паросочетании заключается в нахождении в G паросоче- тания наибольшего возможного размера.

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

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

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