Правила форума
В этом разделе
нельзя создавать новые темы. Если Вы хотите задать новый вопрос, то
не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть
удалены без предупреждения.Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса
обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть
удалена или перемещена в
Карантин, а Вы так и не узнаете, почему.
|
Vlad1992 |
Доказательство, что задача NP-полна  28.11.2012, 17:20 |
|
08/05/11
55
|
|
Рассмотрим ориентированный граф с двумя выделенными узлами s и t. Припишем каждому ребру целочисленную пропускную способность. Можно построить максимальный поток из s в t, многократно находя путь из s в t и увеличивая поток вдоль него до максимума, разрешаемого пропускными способностями его ребер. Покажите, что задача нахождения наименьшего множества путей на которых следует увеличить поток NP-полна.
Данную задачу необходимо свести к задаче о ранцах(Показать что если бы имеем n целых чисел и одно число k мы можем выбрать такое подмножество из числе из n что его сумма равна k) Данная задача NP-полна но как к ней свести вышеуказанную задача я не понял, нужна помощь
|
|
|
|
 |
  |
Страница 1 из 1
|
[ 1 сообщение ] |
|
Модераторы: Модераторы Математики, Супермодераторы
