图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概

来源：学生作业帮编辑：神马作文网作业帮分类：数学作业时间：2024/11/11 06:16:58

图论割集问题
图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~
回复一楼：有割集的概念，只不过讲的比较少而已。
回复二楼：割集就是边的集合，去掉所有这些边后原来的连通图变为两个分离的图，否则图还是连通的（只要该割集中有一条边未去除）。是做的一个小项目中要用到。
回复三楼：采用遍历算法是不是要求出所有可能的边的组合然后从图中去除这些边再对图进行遍历看是否得到两个分支？这样貌似效率不是很高啊！

回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实现.当然在选取边和点时应考虑技巧性,这恐怕是个难题,否则会出现组合爆炸,就象货郎担问题一样,比如选择点可以首先考虑选取度数最大的点,选取边一定要选不在回路上的边.这需要你的智慧.
割集分为点割集和边割集,对一个图G=(V,E)来说如果存在一个结点集V的子集,从G中删除这些结点后,它的连通分图的个数增多,则称该子集为点割集,对一个连通图来说,删除这些结点后,连通图变为不连通.点割集一般不是唯一的,含有最小结点个数的点割集称为最小点割集,类似可定义边割集和最小边割集,仅含1个点的点割集称为割点,仅含1个边的边割集称为割边,割边也称为桥.
求一个连通简单图的割集的算法,我想可用遍历的算法,目前常用的是深度优先搜索或者广度优先搜索算法来做,这是图论中最基本的算法,这种算法可求出图的连通分图的个数,以此来判断某子集是否是割集.

图论割集问题图论中割集与最小割集有什么区别,另外有没有可以求出一个连通简单图的全部割集的算法,急等~回复一楼：有割集的概将一张图二值化后,有很多连通区域,我想分别求出每一块连通区域的面积,不知道有什么好一点的算法求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分数字图像处理中欧拉数与连通分量的个数有什么区别物理的追及、相遇问题有什么自己总结的简单方法?另外有没有什么解题步骤? 有向图G的强连通分量是指-----,一个连通图的---是一个极小连通子图数据结构与算法：请使用Kruskal算法求出下图的最小生成树求此题思路可以没有答案另外问一个问题,已知物体的轨迹方程一定能求出它的运动方程吗?为已知一个图的连接矩阵,判断给定两个节点是否连通的算法思想数据结构与算法中对于“连通分量”的定义?结合具体图来说明 R2空间中,一个紧连通的子集的补集,最多有多少连通分支? 诺和灵N和R的区别前期注射胰岛素诺和灵N效果不是很理想,尤其是餐后血糖,可以换成诺和灵R吗?两者有什么区别?急等回复.