在一个完全连通的有向图中，所有可能的非循环简单路径的数目是多少？

Question

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

这个图有多少条边？是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!还是更多？我找不到一种方法来推广这一点，并推导出一个有用的公式。

Answer 1

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

设起始顶点为v_1。

下一步做什么是有可能的:移动到每个V\{v_1}中的一个，或者停止。

接下来，您有了停止的可能性:移动到每个V\{v_1,v_2}中的一个，其中v_2是被选为第二个或停止的节点。

..。在这里进行归纳以正式证明它

有了n节点的路径后，只有一种可能:停止。

为您提供每个顶点的n*(n-1)*...*1 = n!个可能的简单路径总数，以及图中的n*n!个可能的简单路径总数