单连通图？
-
null
更新：最多1个简单路径。
共有1个答案
如果满足以下两个条件之一，则图不是单连通的：
>
在同一个组件中，当您执行DFS时，您会得到一条从一个顶点到另一个已经完成搜索的顶点的道路（当它被标记为黑色时）
当一个节点从另一个组件指向>=2个顶点时，如果这2个顶点有连接，那么它就不是单独连接的。但这需要你保持深度优先的森林。
-
根据CLRS第3版的定义，单连通有向图是指每对顶点(u，v)至多有一条唯一的路从u->v来的图。现在我读过的大多数答案都说，我们从图中的每个顶点运行DFS，如果在任何情况下我们找到一条交叉边或一条前向边，那么图就不是单连通的。我可以理解前向边的概念，但是在这个图上运行这个algo 1-->2<--3将给出一个结果：它不是单连通的，而这个图是单连通的。我们有一个从3->2或1->2的交叉边，这取决于
-
我把《算法导论》第3版第22行22.3-13中单连通图的定义引用为。我注意到图中的圈并不一定意味着图不是单连通的，因为包含圈的路径不被认为是简单路径。有向图中的一个简单圈可以由相应的边集唯一地表示。让我们考虑一个满足以下两个性质的有向图: (1)它的DFS林中只有树边和后边，(2)图中表示每个简单圈的集合都是不相交的（即它们不共享任何边）。现在我的问题是：满足以上两个条件的有向图一定是单连通图吗？
-
主要内容：重连通图的实际应用,判断重连通图的方法在无向图中，如果任意两个顶点之间含有不止一条通路，这个图就被称为 重连通图。在重连通图中，在删除某个顶点及该顶点相关的边后，图中各顶点之间的连通性也不会被破坏。 在一个无向图中，如果删除某个顶点及其相关联的边后，原来的图被分割为两个及以上的连通分量，则称该顶点为无向图中的一个 关节点（或者 “割点”）。 图 1 连通图 图 1 是连通图但不是重连通图，图中有4个关节点，分别是：A、B、D 和
-
我有一个强连通图。我想移除一个边并检查是否仍然保持强连接。因为我将N=图中节点的总数取为10，并且我感兴趣的大多数图都有25条以上的边，所以很难检查一次使用一条，去掉边。 如何解决这个问题？多谢了。
-
当我看《算法概论3》时，遇到下面这个问题。 22.3-13*有向图G是单连通的，如果u->v暗示G对所有顶点v至多包含一条从u到v的简单路。给出了一个判定有向图是否单连通的有效算法。 但我对这种情况表示怀疑。举个例子，如果图的所有边（A->D,D->E,E->A,B->C,C->A)，DFS从A开始，因此C->A是交叉边，但我认为这个图是单连通的。对不起，我无法上传图片，因为StackOverfl