最大割問題（英語：Maximum Cut ）是 NP完备 问题。給定一張圖，求一種分割方法，將所有頂點 （Vertex ）分割成两群，同时使得被切斷的邊（Edge ）數量最大。
此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。
多項式時間的演算法 雖然最大割問題是 NP-hard 問題，但如果圖本身滿足一些條件之下，是存在多項式時間的演算法的。
圖沒有正邊時（權重都是負的） 可以將圖中所有邊都變號（乘上-1），將最大割問題轉成最小割問題 Karger's algorithm
圖是平面圖（planar graphs）時 Hadlock在1975提出一個演算法，可將最大割問題轉化成郵遞員問題 求解。
近似演算法 由於 max cut 的問題屬 於 NP-hard 問題，為了確保其效率，Nguyen 等人提出了一套根據 Maximum Spanning Tree (MST)的演算法[1]
應用 壓縮圖訊號（Compress Graph Signals） 定義在圖 （Graph ）上的資料，因為圖的連結方法可以十分的複雜以及不規則，使得要處理這樣的一種資料時，不像傳統的 1-D 或 2-D 訊號的結構固定，必須根據其圖的結構，進而分析其資料。一種方法是將任意的圖轉換為二分圖（Bipartite Graph）[2] [3]
通孔最小化問題（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 ] .
外部連結 Quadratic 0–1 Optimization （页面存档备份，存于互联网档案馆 ）
最大割問題, 英語, maximum, np完备, 问题, 給定一張圖, 求一種分割方法, 將所有頂點, vertex, 分割成两群, 同时使得被切斷的邊, edge, 數量最大, maximum, 此問題還有另一個變形的版本, 每條邊上有各自的權重, 要使得被切斷的邊的權重之和最大, 目录, 多項式時間的演算法, 圖沒有正邊時, 權重都是負的, 圖是平面圖, planar, graphs, 近似演算法, 應用, 壓縮圖訊號, compress, graph, signals, 通孔最小化問題, minimizat. 最大割問題 英語 Maximum Cut 是 NP完备 问题 給定一張圖 求一種分割方法 將所有頂點 Vertex 分割成两群 同时使得被切斷的邊 Edge 數量最大 A maximum cut 此問題還有另一個變形的版本 每條邊上有各自的權重 要使得被切斷的邊的權重之和最大 目录 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 编辑引用 编辑 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 外部連結 编辑Quadratic 0 1 Optimization 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 最大割問題 amp oldid 69280703, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。