小编Lar*_*rry的帖子

我正在寻找一种算法来检查给定的图是否是另一个给定图的子图.

我没有什么条件让这个NP完全问题更可行.

• 图表有大约<20个顶点.
• 图是DAG.
• 所有顶点都是非唯一标注的,主图和子图中的相应顶点应具有相同的标签.我不知道我是否使用了正确的术语(因为我没有采用图论理论课程......).它将是这样的:

线图A-B是A-B-A的子图,但A-A不是A-B-A的子图.

任何建议都没问题.这不是一个功课问题顺便说一下.:d

是否有一种算法或一组算法可以让您找到距离任意起始节点最短的步行距离,以便每个节点都能在权重无向图中被访问？这不是旅行推销员,因为我不在乎是否多次访问一个节点.(如果你把它重新开始也没关系 - 只要它是访问所有节点所需的最后一个节点,walker就可以在一些遥远的节点结束.)它不是最小的生成树,因为它可能是A - > B - > C - > A - > D是访问A,B,C和D的(非唯一的)最短路径.我的直觉说这不是'这是一个NP问题,因为它没有限制使NP问题如此棘手.当然,我完全错了.