我找不到一种方法来推广它并推导出一个可用的公式。
假设我们有一个完全连通的有向图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顶点的图?
如果你的图是满的，每个顶点有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!个可能的简单路径总数