计算机科学

首页 > 计算机科学

最大割问题

2018-08-27 10:45:40     所属分类:组合优化
A maximum cut.

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

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

目录

  • 1 多项式时间的算法
    • 1.1 图没有正边时(权重都是负的)
    • 1.2 图是平面图(planar graphs)时
  • 2 近似算法
  • 3 应用
    • 3.1 压缩图讯号(Compress Graph Signals)
    • 3.2 通孔最小化问题(Via Minimization Problem)
    • 3.3 理论物理学(Theoretical Physics)
    • 3.4 二次最佳化(Optimization)
  • 4 引用
  • 5 外部链接

多项式时间的算法

虽然最大割问题是 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]. 
  2. ^ Downsampling graphs using spectral theory. [2016-07-01]. 
  3. ^ Local two-channel critically sampled filter-banks on graphs. [2016-07-01]. 

外部链接

  • Quadratic 0–1 Optimization

相关推荐