帮助了解子图的术语
是否有一个术语来描述只有一个强连通子图的图? (我什至不确定我在这里是否正确使用了强连接)。
例如。 {AB,BC} 只有一个子图,而 {AB,BC,DE} 有两个子图。
请注意,我没有考虑图 {AB,BC} 具有三个子图:{AB,BC} 和 {AB} 和 {BC}。
如果需要,请区分无向和有向。
Is there a term to describe a graph who has only one subgraph that is strongly connected? (I'm not even sure I'm using strongly connected correctly here).
eg. {AB,BC} has only one subgraph and {AB,BC,DE} has two.
Note that I'm not considering that the graph {AB,BC} has three subgraphs: {AB,BC} and {AB} and {BC}.
please distinguish between undirected and directed if need be.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
我认为你的意思是一个连接图,替代方案是一个
forest断开连接的图。来自http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 --
如果图中每对不同的顶点都可以通过某个路径连接,则该图称为连通图。如果将有向图的所有有向边替换为无向边生成连通(无向)图,则有向图称为弱连通。如果对于每对顶点 u,v 包含从 u 到 v 的有向路径或从 v 到 u 的有向路径,则它是连通的。如果对于每对顶点 u,v 包含从 u 到 v 的有向路径和从 v 到 u 的有向路径,则它是强连通的或强的。强分量是最大强连通子图。
I think you mean a connected graph, the alternative being a
forestdisconnected graph.From http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 --
A graph is called connected if every pair of distinct vertices in the graph can be connected through some path. A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is connected if it contains a directed path from u to v or a directed path from v to u for every pair of vertices u,v. It is strongly connected or strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u,v. The strong components are the maximal strongly connected subgraphs.