确定一个图是半连接或不 [英] Determine if a graph is semi-connected or not

问题描述

一个有向图G =（V，E），据说是半连接的话，对于所有对顶点U，V的V中，我们具有u - > V或V-> U的路径。 给出一个有效的算法来确定摹是否是半连接

A directed graph G = (V, E) is said to be semi-connected if, for all pairs of vertices u, v in V we have u -> v or v-> u path. Give an efficient algorithm to determine whether or not G is semi-connected

推荐答案

平凡 0（V ^ 3）解决方案可能是使用的弗洛伊德warshal 都对所有的最短路径，但这是一个矫枉过正（以时间复杂度）。

Trivial O(V^3) solution could be to use floyd warshal all-to-all shortest path, but that's an overkill (in terms of time complexity).

可以在完成O（V + E）。

声明：

一个DAG是半连接的拓扑排序，每个我，也有边（六，六+ 1）

A DAG is semi connected in a topological sort, for each i, there there is an edge (vi,vi+1)

证明：

考虑到与拓扑排序 V1，V2，...，VN A DAG：

Given a DAG with topological sort v1,v2,...,vn:

如果没有边缘（六，六+ 1）一些我，那么也没有路径（VI + 1，六）（因为它是一个拓扑排序的DAG），和图表没有半连接。

If there is no edge (vi,vi+1) for some i, then there is also no path (vi+1,vi) (because it's a topological sort of a DAG), and the graph is not semi connected.

如果为每个我有边（六，六+ 1），然后为每个 I，J （ivi-＆GT; 6 + 1→...-＆GT; VJ-1→，VJ，和图形是半连接

If for every i there is an edge (vi,vi+1), then for each i,j (ivi->vi+1->...->vj-1->vj, and the graph is semi connected.

由此我们可以得到的算法：

From this we can get the algorithm:

1. 找到最大的SCC图中的
2. 构建SCC图G'=（U，E'），使得 U 是一组的SCC的。 E'= {（V1，V2）|有V1在V1和V2的V2使得（V1，V2）是E）
3. 请拓扑排序的G'
4. 检查每一个我，还有边六，VI + 1。

1. Find Maximal SCCs in the graph
2. Build the SCC graph G'=(U,E') such that U is a set of SCCs. E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Do topological sort on G'
4. Check if for every i, there is edge Vi,Vi+1.

正确性证明：

如果该图是半连接，为一对（V1，V2），使得有一条小路 V1-＆GT; .. .-＆GT; V2 - 让V1，V2是他们的SCC。有从V1的路径至V2，从而也从V1到V2，因为在V1和V2的所有节点而强烈地连接

If the graph is semi connected, for a pair (v1,v2), such that there is a path v1->...->v2 - Let V1, V2 be their SCCs. There is a path from V1 to V2, and thus also from v1 to v2, since all nodes in V1 and V2 are strongly connected.

如果该算法产生真正的，比任何两个给定节点V1，V2 - 在SCC V1和V2。有从V1的路径至V2（不损失一般性的情况），因此也从V1到V2

If the algorithm yielded true, than for any two given nodes v1, v2 - are in SCC V1 and V2. There is a path from V1 to V2 (without loss of generality), and thus also from v1 to v2.

作为一个侧面说明，也是每一个半连接图有一个根（顶点研究，导致所有顶点）：

As a side note, also every semi-connected graph has a root (vertex r that leads to all vertices):

证明：
假设没有根。定义＃（V）= | {U |有从V路径到u} | （即具有的路径v 来他们的节点数量）。
选择 A ，使得＃（A）=最大值{＃（五）|对于所有V} 。
A 不是根，所以有一些节点 U ，有没有从<$ C $ PATH C> A 给它。由于图表半连接，这意味着有一条小路 U-＆GT; ...-＆gt;在。但是，这意味着＃（U）＆GT; =＃（一）+ 1 （到达距离所有节点，也U <$ C C $>）。
矛盾的极大性＃（一），因此有一个根。

Proof:
Assume there is no root. Define #(v) = |{u | there is a path from v to u}| (number of nodes that has a path from v to them).
Choose a such that #(a) = max{#(v) | for all v}.
a is not a root, so there is some node u that has no path from a to it. Since graph is semi connected, it means there is a path u->...->a. But that means #(u) >= #(a) + 1 (all nodes reachable from a and also u).
Contradiction to maximality of #(a), thus there is a root.

这篇关于确定一个图是半连接或不的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！