最大割問題

最大割問題(英語: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)

引用

  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]. 

外部連結