1

我对图论还很陌生，我对图的强连通分量有一个非常基本的疑问。它说如果两个节点之间都有路径，则两个或更多节点是强连接的。那么这个图是否有资格作为一个有循环的循环图？

4

1 回答 1

2

是的，强连通图是循环的。在这样的图中，任何两个顶点，比如说u和v是强连接的，所以存在一条由有向边组成的从u到和从到v的路径。如果路径和路径不相交，将它们连接起来，你就有了循环。如果它们共享边，则从路径开始并遵循路径，一旦您击中两条路径共享的第一条边，则开始遵循路径，直到返回。vuu->vv->uuu->vv->uu

于 2012-07-31T22:21:36.357 回答