※ 引述《VSBSC (Trist)》之銘言：
: Steiner tree problem:
: given a graph G=(V,E), and some of vertices marked, find the minimum subtree
: of G that contains the marked vertices? the steiner tree problem is
: NP-complete even if all weight of each edge is equivalent.
: Steiner tree 如何從 Hamiltonian Path 變換 證明為 NP-complete problem??
連題目也抄錯 =.=
For every solvable Graph G in Hamiltonian Path Problem, there is a
function f which transform G to a solvable G' for Steiner tree by
marking every vertice.
然後要證明每一個Hamiltonian Path of G 也的確是minimum subtree of G'
這個應該不用講了吧.
--
逝去的愛，使生命更豐富。
LIFE has become richer by the love that has been lost.
--泰戈爾，漂鳥集.223。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.172.17