# 最小頂點覆蓋

有限simple graph中，cardinality在全部vertex covers裡最小的候選是minimum vertex cover。

mko-minimum-vertex-cover · definition · v0.10.0



## 數學敘述

對bounded finite simple undirected graph完整枚舉全部vertex subsets，逐一做all-edge cover audit，得到minimum cardinality與全部minimizers。給定nonminimum cover時須明示更小cover witness；inclusion-minimal只表示刪任一點即失去cover，不等於minimum。empty graph、multiple minima與minimal-but-not-minimum均保留。不得混同maximal、edge cover、independent set，也不使用König theorem或weighted/directed variants。





## 代表公式（精確 TeX）

V(G,C)=k





## 成立條件


- vertices finite unique，edges為loop-free duplicate-free unordered pairs。
- 頂點數有界以完整枚舉全部subsets。





## 符號作用域


- V — 最小頂點覆蓋算子
- G — 有限簡單圖
- C — 頂點覆蓋
- k — 最小覆蓋基數





## 直觀、定義與常見誤解

所有subsets完整資格核對。

minimum size與全部minimizers同時輸出。

nonminimum與minimal-not-minimum給明示反例。

把inclusion-minimal或maximal誤作minimum。





## 已採用的推導導讀

[P3全部八子集求minimum cover](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-minimum-vertex-cover-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [頂點覆蓋](https://ocme.evemisslab.com/zh-Hant/mko/mko-vertex-cover/) — cover qualification。
- [最佳化問題](https://ocme.evemisslab.com/zh-Hant/mko/mko-optimization-problem/) — minimum語義。
- [集合基數比較](https://ocme.evemisslab.com/zh-Hant/mko/mko-cardinality-comparison/) — cover size比較。





## 驗證界線

只處理小型有限simple graph的exact enumeration；不宣稱多項式時間或近似比。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入vertex-cover decision problem與approximation boundaries。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/minimum-vertex-cover.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-minimum-vertex-cover/index.md)