全连通有向图中所有可能的非循环简单路径的数量是多少？ [英] What is the number of all possible non-cyclic simple paths in a fully-connected directed graph?

问题描述

假设我们有一个完全连通的图 G ，其中 N 顶点并且 M 边缘。

Let's say we have a fully connected digraph G with N vertices and M edges.

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

How many edges does the graph have? Is it M = N^2?

如果我们取一个顶点并开始以深度访问其邻居首先搜索方式并避免循环，我们会得到多少个非循环简单路径？

If we take one vertex and start visiting its neighbors in a 'depth-first search' manner and avoiding loops, how many non-cyclic simple paths will we get?

例如，如果我们从包含4个顶点的图形中的顶点1开始，那么这里是路径：

For example, if we start from vertex 1 in a graph of 4 vertices, here are the paths:

- 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！或更多c $ c> N 顶点？我无法找到一种方法来推广这一点，并推导出一个可用的公式。

Is it N! or more for a graph with N vertices? I could not find a way to generalize this and to derive a usable formula.

推荐答案

如果图表已满， code> n！每个顶点的简单路径，所以总共 n * n！图中的简单路径。

If your graph is full, there are n! simple paths for each vertex, so total of n*n! simple paths in the graph.

让起始顶点为 v_1 。

| V | 可能性下一步做什么：移动到 V \ {v_1}之一，或停止。

接下来你有 | V | -1 可能性：移动到 V \ {v_1，v_2}之一 [其中v_2是选为第二个节点]或停止。

... [在这里正式证明它的感应]

在你有一个 n 节点的路径后，唯一的可能性：停止。

给你总计 n *（n-1）* ... * 1 = n！每个顶点可能的简单路径， n * n！图中所有可能的简单路径

let a starting vertex be v_1.
There are |V| possibilities what to do next: move to one of each V\{v_1}, or stop.
next you have |V|-1 possibilities: move to one of each V\{v_1,v_2} [where v_2 is the node chosen as second] or stop.
... [do induction to formally prove it here]
after you have a path of n nodes, there is one only possibility: stop.
giving you total of n*(n-1)*...*1 = n! possible simple paths for each vertex, and n*n! total possible simple paths in the graph

这篇关于全连通有向图中所有可能的非循环简单路径的数量是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！