最小割英文

最小割（Minimum Cut）在圖論中是指在一個有向圖或無向圖中找到一個割的最小容量，其中割是指圖中的邊的一個子集，通過這些邊的刪除可以將圖中的一個頂點集與另一個頂點集分離。最小割問題在許多最佳化問題和算法中都有套用，例如在網路流問題和最短路徑問題中。