确定图形是否是半连接的

Question

如果对于V中的所有顶点对u,v,我们有u - > v或v-> u路径,则有向图G =(V,E)被认为是半连接的.提供一种有效的算法来确定G是否是半连接的

Answer 1

琐碎的O(V^3)解决方案可能是使用floyd warshal全部到最短的路径,但这是一种过度杀伤力(就时间复杂性而言).

它可以在O(V+E).

要求:

DAG以拓扑排序半连接,每个i都有边缘(vi,vi+1)

证明:

鉴于具有拓扑排序的DAG v1,v2,...,vn:

如果(vi,vi+1)某些边缘没有边缘i,则也没有路径(vi+1,vi)(因为它是DAG的拓扑类型),并且图形不是半连接的.

如果每个i都有边缘(vi,vi+1),那么对于每个i,j(i <j),存在路径vi->vi+1->...->vj-1->vj,并且图形是半连接的.

从这里我们可以得到算法:

1. 在图中查找最大SCC
2. 构建SCC图G'=(U,E'),这U是一组SCC.E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. 对G'进行拓扑排序
4. 检查每个i是否有边缘Vi,Vi + 1.

正确性证明:

如果图形是半连接的,对于一对(v1,v2),则存在路径v1->...->v2- 让V1,V2为它们的SCC.由于V1和V2中的所有节点都是强连接的,因此存在从V1到V2的路径,因此也从v1到v2.

如果算法产生了真,则对于任何两个给定节点v1,v2 - 我们知道它们在SCC V1和V2中.存在从V1到V2的路径(不失一般性),因此也从v1到v2.

作为旁注,每个半连接图也有一个根(r通向所有顶点的顶点):

证明:
假设没有根.定义#(v) = |{u | there is a path from v to u}|(具有v到它们的路径的节点数).
选择a这样#(a) = max{#(v) | for all v}.
a不是根,所以有一些节点u没有路径a到它.由于图形是半连接的,这意味着存在路径u->...->a.但这意味着#(u) >= #(a) + 1(所有节点都可以从a,也可以u).
矛盾到极大#(a),因此有一个根.