作者neversay (子不语)
看板CSSE
标题Re: [问题] NP-Complete
时间Tue Jan 23 16:42:37 2007
※ 引述《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