稀疏割

在圖論與近似演算法中，稀疏割問題（）要求將圖的頂點集分成兩部分，使跨越分割的邊相對於兩側「體積」（）的比例最小。此問題同時要求分割既稀疏（跨割邊少）又均衡（兩側大小相近），是譜圖論、擴展圖與圖分割中的核心問題。