最大割问题

最大割问题（英语：Maximum Cut）是指，给定一张图，求一种分割方法，将所有顶点（Vertex）分割成两群，同时使得被切断的边（Edge）数量最大。该问题是一个NP完备问题。

一个图的最大割

此问题还有另一个变形的版本：每条边上有各自的权重，要使得被切断的边的权重之和最大。

多项式时间的算法

虽然最大割问题是 NP-hard 问题，但如果图本身满足一些条件之下，是存在多项式时间的算法的。

图没有正边时（权重都是负的）

可以将图中所有边都变号（乘上-1），将最大割问题转成最小割问题。再使用Karger's algorithm（英语：Karger's_algorithm）求解

图是平面图（planar graphs）时

Hadlock在1975提出一个算法，可将最大割问题转化成邮递员问题求解。

近似算法

由于最大割的问题属于NP困难问题，为了确保其效率，Nguyen 等人提出了一套根据 Maximum Spanning Tree(MST)的算法^[1]来处理，不过使用 MST 大多只能找到相对平均高的切割数，而非真正的最大切割数。

应用

压缩图讯号（Compress Graph Signals）

定义在图上的资料，因为图的连结方法可以十分的复杂以及不规则，使得要处理这样的一种资料时，不像传统的 1-D 或 2-D 讯号的结构固定，必须根据其图的结构，进而分析其资料。一种方法是将任意的图转换为二分图^[2],而后有人^[3]提出了证明，如果可以在转换后保留越多的边（Edges），这二分图就与原先的图性质越相近。如果可以解决最大割问题，就能使得二分图与原始图性质变相近。

通孔最小化问题（Via Minimization Problem）

理论物理学（Theoretical Physics）

二次最佳化（Optimization）