0

假设我们有一个G带有N顶点和M边的完全连接的有向图。

图有多少条边？是M = N^2吗？

如果我们取一个顶点并开始以“深度优先搜索”的方式访问它的邻居并避免循环，我们将获得多少非循环简单路径？

例如，如果我们从 4 个顶点的图中的顶点 1 开始，则路径如下：

- 1
- 1,2
- 1,3
- 1,4
- 1,2,3
- 1,2,4
- 1,3,2
- 1,3,4
- 1,4,2
- 1,4,3

N!带有顶点的图是它还是更多N？我找不到一种方法来概括这一点并推导出一个可用的公式。

4

1 回答 1

1

如果您的图表已满，则n!每个顶点都有简单的路径，因此n*n!图表中有简单的路径。

设一个起始顶点为v_1。
接下来有|V|可能做什么：移动到其中一个V\{v_1}，或停止。
接下来你有|V|-1可能：移动到每个V\{v_1,v_2}[其中 v_2 是选择为第二个的节点] 之一或停止。
... [在这里进行归纳以正式证明它]
在您拥有n节点路径之后，只有一种可能性：停止。
为您n*(n-1)*...*1 = n!提供每个顶点n*n!可能的简单路径总数，以及图中可能的简单路径总数

于 2011-12-10T16:11:16.533 回答