一个关于simple cycle with zero weight的问题# Programming - 葵花宝典
d*g
1 楼
要求证明是np-complete.
怎样从subset sum 问题 转化到这个问题。
Subset sum:
Given a set U of natural numbers {a1,a2....an) and a W, is there any subset
of U whose sum is equal to W.
Assume we know this problem is NP-COMPLETE
a directed graphG==(V,E),there is a weight w(e) for every edege e, which
would be positive or negative. Zero-weight-cycle problem is to decide if
there is a simple cycle in G so that sum of the edges weight is 0.
怎样从subset sum 问题 转化到这个问题。
Subset sum:
Given a set U of natural numbers {a1,a2....an) and a W, is there any subset
of U whose sum is equal to W.
Assume we know this problem is NP-COMPLETE
a directed graphG==(V,E),there is a weight w(e) for every edege e, which
would be positive or negative. Zero-weight-cycle problem is to decide if
there is a simple cycle in G so that sum of the edges weight is 0.
