点割集、边割集、割点、桥、连通度、双连通分支.doc

《点割集、边割集、割点、桥、连通度、双连通分支.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对于一个无向图G：定义一：删除一个点v是指删除点v以及所有与点v关联的边。定义二：删除一条边e是指删除这条边，但是保留e的两个顶点。点割集：V是一些顶点的集合，如果删除V中的所有顶点之后，G不在连通，但是对于V的任何真子集V1，删除V1后G仍然连通，则称V是点割集。割点：如果点割集里只有一个顶点，那么这个顶点叫做割点。点连通度：最小的点割集的大小。边割集：E是一些边的集合，如果删除E里的所有边之后G不在连通，但是对于E的任何真子集E1,删除E1之后G仍然连通，则称E是边割集。桥：如果边割集里只有一条边，该

2、边称为桥。边连通度：最小的边割集的大小。双连通：如果一个图没有割点，那么这个图称为2-连通的，或者双连通的。一个图的极大双连通子图称为双连通分量。注意是极大而不是最大，即意味双连通子图不一定只有一个。