# 頂點覆蓋

有限simple undirected graph的頂點子集C若與每條edge至少一端相交，則C為vertex cover。

mko-vertex-cover · definition · v0.10.0



## 數學敘述

graph須明示有限unique vertices與loop-free、duplicate-free unordered edges。cover audit遍歷全部edges；一條兩端皆不在C的edge即為反例。empty-edge graph的empty set是cover；isolated vertices不必加入；任何cover的superset仍為cover。inclusion-minimal表示刪任何一點都不再cover，minimum表示全體covers中cardinality最小，兩者不可混同。本節點不混用edge cover、independent set或directed cover，也不自動求minimum size。





## 代表公式（精確 TeX）

V(G,C)=1





## 成立條件


- edges canonical成排序unordered pairs；candidate subset unique且屬vertex set。
- minimum boundary只在小型完整finite graph exhaustive枚舉全部subsets。





## 符號作用域


- V — 頂點覆蓋述詞
- G — 有限簡單圖
- C — 候選頂點子集





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

全部edges逐一核至少一端被選。

uncovered edge是完整反例witness。

empty/isolated/superset與minimal/minimum boundaries分開。

只覆蓋大多數edges，或把inclusion-minimal當minimum。





## 已採用的推導導讀

[星形圖的cover與刪點證書](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-vertex-cover-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — finite simple graph。
- [子集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-subset/) — candidate vertex subset。
- [量詞與明示論域](https://ocme.evemisslab.com/zh-Hant/mko/mko-quantifier/) — all-edge責任。





## 驗證界線

本輪只判定vertex covers與小型boundary；minimum vertex cover留待後續節點。

not_formalized

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





## 下一個義務

加入最小頂點覆蓋。





## 同源結構化資料

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

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