Рассмотрим ориентированный граф с двумя выделенными узлами s и t. Припишем каждому ребру целочисленную пропускную способность. Можно построить максимальный поток из s в t, многократно находя путь из s в t и увеличивая поток вдоль него до максимума, разрешаемого пропускными способностями его ребер. Покажите, что задача нахождения наименьшего множества путей на которых следует увеличить поток NP-полна.
Данную задачу необходимо свести к задаче о ранцах(Показать что если бы имеем n целых чисел и одно число k мы можем выбрать такое подмножество из числе из n что его сумма равна k) Данная задача NP-полна но как к ней свести вышеуказанную задача я не понял, нужна помощь
|