作业帮图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概念，只不过讲的比较少而已。回复二楼：割集就是边的集
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 00:45:32
图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概念，只不过讲的比较少而已。回复二楼：割集就是边的集
图论割集问题
图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~
回复一楼：有割集的概念，只不过讲的比较少而已。
回复二楼：割集就是边的集合，去掉所有这些边后原来的连通图变为两个分离的图，否则图还是连通的（只要该割集中有一条边未去除）。是做的一个小项目中要用到。
回复三楼：采用遍历算法是不是要求出所有可能的边的组合然后从图中去除这些边再对图进行遍历看是否得到两个分支？这样貌似效率不是很高啊！
图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概念，只不过讲的比较少而已。回复二楼：割集就是边的集
回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实现.当然在选取边和点时应考虑技巧性,这恐怕是个难题,否则会出现组合爆炸,就象货郎担问题一样,比如选择点可以首先考虑选取度数最大的点,选取边一定要选不在回路上的边.这需要你的智慧.
割集分为点割集和边割集,对一个图G=(V,E)来说如果存在一个结点集V的子集,从G中删除这些结点后,它的连通分图的个数增多,则称该子集为点割集,对一个连通图来说,删除这些结点后,连通图变为不连通.点割集一般不是唯一的,含有最小结点个数的点割集称为最小点割集,类似可定义边割集和最小边割集,仅含1个点的点割集称为割点,仅含1个边的边割集称为割边,割边也称为桥.
求一个连通简单图的割集的算法,我想可用遍历的算法,目前常用的是深度优先搜索或者广度优先搜索算法来做,这是图论中最基本的算法,这种算法可求出图的连通分图的个数,以此来判断某子集是否是割集.