最大流问题最小割集,帮我解释下网络流( 二 )

连续最短路算法 + 线性规划对偶性优化的原始对偶算法(*)
传说中，没见过，据说复杂度是O(V^3)
NO3. 有上下届的最大流和最小流（通过添加点来进行转化）(*)
NO4. 相关图论算法
二分图最大匹配：加s和t构造最大流
专用算法：hungary算法 O(M*N)
二分图最佳匹配：加s和t构造最小费用最大流
专用算法：KM算法
朴素的实现方法,时间复杂度为O(n^4)
加上松弛函数O(n^3)
最小路径覆盖：
顶点数－二分图的最大匹配
s-t最小边割集：
最大流最小割定理：最小割等于最大流
普通最小边割集：
Stoer-Wagner Minimum Cut O(n^3)
二分图的最大独立集：
N - 二分图的最大匹配（POJ monthly）girls and boys
反证法证明
普通图的最大独立集是np问题。(*)
matlab中的翻译问题

文章插图
成grbase -寻找所有基地图; 成grcobase -寻找所有contrabases图; 成grcocyclebasis -寻找所有独立割集为连通; 成grcoledge -解决问题彩色图形边; 成grcolver -解决问题彩色图形顶点; 成grcomp -寻找所有部件图; 成grcyclebasis -寻找所有独立周期为连通; 成grdecord -解决约分解图的成章节相互存取顶点% (收盘南澳连通成分) ; 成grdistances找到彼此之间的距离任何顶点图; 成greccentricity --找到(加权)偏心各顶点, %半径,直径,中心节点和边缘节点; 成griseulerian --找到欧拉周期图; 成grmaxcomsu -解决最大完全sugraph的问题,因图; 成grmaxflows -解决最大流问题的图; 成grmaxmatch -解决的最大匹配问题,为图; 成grmaxstabset -解决的最大稳定集的问题,因图; 成grminabsedgeset -解决极小吸收集问题成图形边; 成grminabsverset -解决极小吸收集问题成图的顶点; 成grmincutset -解决最小割集的问题,因图; 成grminedgecover -解决最小边复盖问题,为图; 成grminspantree -解决最小生成树问题,为图; 成grminvercover -解决最小顶点复盖问题,为图; 成grpert -解决项目评价研究任务; 成grshortpath -解决最短路径问题,为图; 成grtravsale -解决对称旅行商问题; 成grvalidation辅助功能(数据核实) ;
关于网络流中最小割的意思?

文章插图
首先来解释割集
在一个有权图中，源点为Vs，汇点为Vt，从Vs到Vt有很多路径可以走，每条路径都包含若干条边对吧。这些边可能只属于一条路径，也可能同时出现在两条路径中。如果拿掉这张图中的一些边，就无法从Vs到达Vt，这些边的组合就叫做割集。
最小割的解释：
割集有很多，每一个割集中元素的权值之和成为割集容量。所有割集容量中，最小的那个割集就叫做最小割。
【最大流问题最小割集,帮我解释下网络流】^^