最小頂點覆蓋

數學敘述

對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。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 頂點覆蓋 — cover qualification。
• 最佳化問題 — minimum語義。
• 集合基數比較 — cover size比較。

驗證界線

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

not_formalized

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

下一個義務

加入vertex-cover decision problem與approximation boundaries。

同源結構化資料

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