2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group