У меня есть невзвешенный, связный граф. Я хочу найти связанный подграф, который определенно включает определенный набор узлов и как можно меньше отдельно оплачиваемых предметов. Как это могло быть выполнено?
На всякий случай я вновь заявлю о вопросе с помощью более точного языка. Позвольте G (V, E) быть невзвешенным, неориентированным, связным графом. Позвольте N быть некоторым подмножеством V. Что лучший способ состоит в том, чтобы найти самый маленький связанный подграф G' (V', E') G (V, E) таким образом, что N является подмножеством V'?
Приближения прекрасны.