热门问题
时间线
聊天
视角
最大割问题
来自维基百科,自由的百科全书
Remove ads
最大割问题(英语:Maximum Cut)是指,给定一张图,求一种分割方法,将所有顶点(Vertex)分割成两群,同时使得被切断的边(Edge)数量最大。该问题是一个NP完备问题。

此问题还有另一个变形的版本:每条边上有各自的权重,要使得被切断的边的权重之和最大。
多项式时间的算法
虽然最大割问题是 NP-hard 问题,但如果图本身满足一些条件之下,是存在多项式时间的算法的。
可以将图中所有边都变号(乘上-1),将最大割问题转成最小割问题。再使用Karger's algorithm求解
Hadlock在1975提出一个算法,可将最大割问题转化成邮递员问题求解。
近似算法
由于最大割的问题属于NP困难问题,为了确保其效率,Nguyen 等人提出了一套根据 Maximum Spanning Tree(MST)的算法[1]来处理,不过使用 MST 大多只能找到相对平均高的切割数,而非真正的最大切割数。
应用
定义在图上的资料,因为图的连结方法可以十分的复杂以及不规则,使得要处理这样的一种资料时,不像传统的 1-D 或 2-D 讯号的结构固定,必须根据其图的结构,进而分析其资料。一种方法是将任意的图转换为二分图[2],而后有人[3]提出了证明,如果可以在转换后保留越多的边(Edges),这二分图就与原先的图性质越相近。如果可以解决最大割问题,就能使得二分图与原始图性质变相近。
引用
外部链接
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads