判断一个图是否是半连通图 [英] Determine if a graph is semi-connected or not

问题描述

如果对于 V 中的所有顶点对 u, v 我们有 u -> v 或 v-> u 路径，则称有向图 G = (V, E) 是半连通的.给出判断G是否半连通的有效算法

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

推荐答案

Trivial O(V^3) 解决方案可能是使用 floyd 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在拓扑排序中是半连通的，对于每个i，都有一条边(vi,vi+1)

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

证明:

给定一个拓扑排序的 DAG v1,v2,...,vn:

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

如果某些i没有边(vi,v(i+1))，那么也没有路径(v(i+1),vi)(因为它是 DAG 的拓扑排序)，并且图不是半连通的.

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

如果对于每个 i 都有一条边 (vi,vi+1)，那么对于每个 i,j (i <j) 存在路径vi->vi+1->...->vj-1->vj，图为半连通图.

If for every i there is an edge (vi,vi+1), then for each i,j (i < j) there is a path vi->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. 检查是否对于每个 i，都有边 Vi,V(i+1).

正确性证明:

如果图是半连通图，对于一对(v1,v2)，使得存在路径v1->...->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, then for any two given nodes v1, v2 - we know they 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.

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

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

证明:
假设没有root.定义 #(v) = |{u |有一条从 v 到 u}| 的路径(从 v 到它们的路径的节点数).
选择a使得#(a) = max{#(v) |对于所有 v}.
a 不是根，所以有一些节点 u 没有从 a 到它的路径.由于图是半连通的，这意味着存在路径u->...->a.但这意味着 #(u) >= #(a) + 1(所有节点都可以从 a 和 u 到达).
与#(a)的极大值矛盾，故有根.

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屋！