在n个顶点,e条边的无向图中,连通分量最少为多少个？

来源：蜘蛛抓取(WebSpider) 时间：2022-09-11 10:49 标签： 无向图有n个顶点e条边

[版权声明] 本站所有资料由用户提供并上传，若内容存在侵权，请联系邮箱。资料中的图片、字体、音乐等需版权方额外授权，请谨慎使用。网站中党政主题相关内容(国旗、国徽、党徽)仅限个人学习分享使用，禁止广告使用和商用。

图 8.5 割边集与边连通度 割边同样也有另外一种定义方式：在一个无向连通图 G 中，当删去 G 中的某条边 e 后，可将 图分割成 2 个或 2 个以上的连通分量，则称边 e 为割边，或者称为桥。例如图 8.4(a)所示的无向 连通图中，边(v1, v5)、(v4, v6)、(v8, v9)和(v8, v10)都是割边。 2. 边双连通图与边双连通分量 边双连通图：如果一个无向连通图 G 没有割边，或者说边连通度 λ(G)>1，则称 G 为边双连 通图。 为什么称为边双连通图呢？因为在这种图中任何一对顶点之间至少存在 2 条无公共边的路径 （允许有公共内部顶点），在删去某条边后，也不会破坏图的连通性。例如，图 8.5(a)中，顶点 v8 和 v4之间存在 2 条无公共边的路径：(v8, v5, v6, v3, v4)和(v8, v9, v6, v7, v4)，这两条路径有一个公共内 部顶点（当然这两个顶点之间还存在其他路径）。 图 8.6 连通图和它的割边、边双连通分量 边双连通分量：一个连通图 G 如果不是边双连通图，那么它可以包括几个边双连通分量。一 个连通图的边双连通分量是该图的极大重连通子图，在边双连通分量中不存在割边。在连通图中， 把割边删除，则连通图变成了多个连通分量，每个连通分量就是一个边双连通分量。例如，图 8.6(a) 所示的连通无向图存在两条割边，(4,10)和(6,10)，把这两条割边删除后，得到 3 个边双连通分量，

我要回帖

更多关于 无向图有n个顶点e条边 的文章

 

随机推荐