最大割问题
最大割问题（英语：Maximum Cut）是指，给定一张图，求一种分割方法，将所有顶点（Vertex）分割成两群，同时使得被切断的边（Edge）数量最大。该问题是一个NP完备问题。
此问题还有另一个变形的版本：每条边上有各自的权重，要使得被切断的边的权重之和最大。
多项式时间的算法
[编辑]虽然最大割问题是 NP-hard 问题，但如果图本身满足一些条件之下，是存在多项式时间的算法的。
图没有正边时（权重都是负的）
[编辑]可以将图中所有边都变号（乘上-1），将最大割问题转成最小割问题。再使用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）
[编辑]引用
[编辑]- ^ 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）.
- ^ Downsampling graphs using spectral theory. [2016-07-01].
- ^ Local two-channel critically sampled filter-banks on graphs. [2016-07-01].