【离散数学】点割集（割点集）与边割集详解
·
1. 点割集又叫割点集
2. 定义：
设无向图 G=<V,E>为连通图，
若有点集v1⊂V,
使图G删除了v1的所有结点后（将结点与其关联的边都删除）得到的子图是不连通的，
而删除了v1的任何真子集后所得到的子图仍然是连通图，
则称v1为G的一个点割集。
若某一个结点构成一个点割集，则称该结点为割点。
3. 点数最少的割点集的点数用k（G）表示
4. 边割集的定义：
边割集：E是一些边的集合，
如果删除E里的所有边之后G不在连通，
但是对于E的任何真子集E1,
删除E1之后G仍然连通，则称E是边割集。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
24
0- 0
已为社区贡献2条内容
所有评论(0)