Gra*_*ddy 6 algorithm graph-algorithm
给定图G(V,E)和顶点v,我如何找到长度正好为k的简单路径(路径上没有顶点重复)可到达的所有顶点.
邻接矩阵的幂给出了顶点之间的路径数,但它包括非简单路径.
这个问题在多项式时间内是否可以解决？如果没有,是否有任何已知的近似算法.任何文学指针都会很棒.
Evg*_*uev 1
我只回答第一个问题：“它可以在多项式时间内解决吗？”。
假设它可以在多项式时间内求解。然后解决它k=|V|-1并选择任何生成的顶点。删除这个顶点并解决 的这个问题k=|V|-2。生成的一组顶点应至少包含一个连接到最后删除的顶点的顶点。删除该顶点并继续处理，直到k=|V|-i保留单个起始顶点。您刚刚使用多项式时间算法找到了原始图的哈密顿路径。
k=|V|-1
k=|V|-2
k=|V|-i
由于哈密顿路径问题是 NP 完全问题，因此 OP 中的问题也不太可能在多项式时间内求解。
归档时间：
13 年，3 月 前
查看次数：
157 次
最近记录：