问题描述
限时送ChatGPT账号..如果对于 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:
在图中找出最大 SCC.构建 SCC 图 G'=(U,E') 使得U
是一组 SCC.E'= { (V1,V2) |V1 中有 v1,V2 中有 v2,使得 (v1,v2) 在 E 中 }
.对 G' 进行拓扑排序.检查是否对于每个 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屋!
更多推荐
[db:关键词]
发布评论