1. 点割集又叫割点集
2. 定义:
设无向图 G=<V,E>为连通图,
若有点集v1⊂V,
使图G删除了v1的所有结点后(将结点与其关联的边都删除)得到的子图是不连通的,
而删除了v1的任何真子集后所得到的子图仍然是连通图,
则称v1为G的一个点割集。
若某一个结点构成一个点割集,则称该结点为割点。
3. 点数最少的割点集的点数用k(G)表示
4. 边割集的定义:
边割集:E是一些边的集合,
如果删除E里的所有边之后G不在连通,
但是对于E的任何真子集E1,文章来源:https://www.toymoban.com/news/detail-547937.html
删除E1之后G仍然连通,则称E是边割集。文章来源地址https://www.toymoban.com/news/detail-547937.html
到了这里,关于【离散数学】点割集(割点集)与边割集详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!