最大割问题

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

A maximum cut.

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

多项式时间的算法

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

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

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

图是平面图（planar graphs）时

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

近似算法

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

应用

压缩图讯号（Compress Graph Signals）

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

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

理论物理学（Theoretical Physics）

二次最佳化（Optimization）

引用

  1. ^ Ha Q. Nguyen and Minh N. Do, Fellow, IEEE. Downsampling of Signals on Graphs Via Maximum Spanning Trees (PDF). 2015-01-01 [2016-07-01]. （原始内容存档 (PDF)于2018-07-21）. 
  2. ^ Downsampling graphs using spectral theory. [2016-07-01]. 
  3. ^ Local two-channel critically sampled filter-banks on graphs. [2016-07-01]. 

外部链接