【离散数学】点割集（割点集）与边割集详解
·
1. 点割集又叫割点集
2. 定义：
设无向图 G=<V,E>为连通图，
若有点集v1⊂V,
使图G删除了v1的所有结点后（将结点与其关联的边都删除）得到的子图是不连通的，
而删除了v1的任何真子集后所得到的子图仍然是连通图，
则称v1为G的一个点割集。
若某一个结点构成一个点割集，则称该结点为割点。
3. 点数最少的割点集的点数用k（G）表示
4. 边割集的定义：
边割集：E是一些边的集合，
如果删除E里的所有边之后G不在连通，
但是对于E的任何真子集E1,
删除E1之后G仍然连通，则称E是边割集。
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
24
0- 0
已为社区贡献2条内容
所有评论(0)