- 智能AI问答！更聪明、更完整、原创作！
- 一款基于GPT的超级AI机器人，可以回答问题、聊天、创作、写文案！
一个图的点连通度为1，那么它的边连通度是多少
发布于 2023-05-29 17:43:20
对于一个无向图，如果它的每一对顶点都是互相连通的，则我们称它为连通图（Connected Graph）。而对于一个连通图 G 而言，如果其中任意一个点被去掉后，G 变成不连通图，则它称为一个割点（Cut Vertex，或称 Articulation Point）。
如果一个无向图删除一个点之后不再连通，那么这个点就是一个割点。因此，一个无向图 G 的点连通度为 1，说明删除其中一个点后 G 就不再连通。
另外，我们知道边点连通度的定义是，在一个图中，如果删除其中某些边之后，图变得不连通，那么这些边的最小数目就是该图的边连通度。显然，点连通度与边连通度有着密切的关系。
因为一个点连通度是 1，则至少需要删除一个点才能使图不连通。我们考虑删除任意一个与该点相邻的边，此时该图变成了两个不相连的部分，因此该图的边连通度最小为 1。即这个图的边连通度为 1。
0 条评论
关于作者
