最小頂點覆蓋

最小頂點覆蓋是對於給定圖，頂點數最少的頂點覆蓋。圖 的最小頂點覆蓋的大小被稱為頂點覆蓋數，記為 。

每個最小頂點覆蓋都是極小頂點覆蓋（即，不是任何其他覆蓋的真子集的頂點覆蓋），但反之不一定成立。

找到一般圖的最小頂點覆蓋是一個 NP 完全問題。然而，對於二分圖，柯尼希-埃格瓦里定理允許在多項式時間內找到最小頂點覆蓋。

圖的最小頂點覆蓋可以使用 Wolfram 語言計算，使用FindVertexCover[g]。目前沒有 Wolfram 語言函式來計算所有最小頂點覆蓋。

最小頂點覆蓋對應於最大獨立頂點集的補集。