检查图表是否为单连通

Question

我将CLRS第三版ch.22练习22.3-13中的算法简介中的单连通图定义称为A directed graph G = (V,E) is singly connected if G contains at most one simple path from u to v for all vertices u, v belongs to V。我注意到，图中的圈并不一定意味着图不是单连接的，因为涉及圈的路径不被视为简单路径。有向图中的一个简单圈可以由一组对应的边唯一地表示。让我们考虑一个满足以下两个性质的有向图：

(1)它在其DFS森林中只有树和背边，以及(2)表示图中每个简单循环的所有集合都是不相交的(即它们不共享任何边)。现在我的问题是:每个满足上述两个条件的有向图一定是单连通图吗？或者仅仅条件1就足以使图是单连通的?我找不到任何反例。

Answer 1

我发现了一个反例。假设这个有向图G有5个节点(0，1，2，3，4)和6个边(0,1)，(1,2)，(2,0)，(2,3)，(3,4)，(4,0)。如果我们在集合(3，4)中的任何节点上启动DFS，我们将只有树和后边。显然，它满足条件1但不满足条件2，并且它不是单连通图，因为从节点1到0有两条简单的路径( 1->2->3->4->0和1->2->0 )。令人惊讶的是，如果我们从任何其他节点(即从0，1，2)启动DFS，它的DFS林将包含至少一个前向边。图中表示简单圈的边集是{ (0,1)，(1,2)，(2,0)}和{(0,1)，(1,2)，(2,3)，(3,4)，(4,0)}，它们共享边(0，1)和(1,2)。通过从两个集合(即，从0，1，2)之间的公共边内的任何节点中选择初始节点而获得的DFS森林导致至少一个前向边，而通过从任何剩余节点(即，从3，4)中选择初始节点，则在其DFS林中只产生树和后向边。证明了条件1不是有向图是单连通的充分条件。