最大割問題
最大割問題（英語：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].