最大匹配

數學敘述

本輪對小型完整有限簡單圖exhaustively枚舉全部edge subsets並篩matching，給exact maximum size與witnesses。每個候選先驗matching；maximal不等於maximum，多個maximum可共存。

代表公式（精確 TeX）

X(G)

成立條件

• 完整有限無向無loop簡單圖，edge count受合約上限。
• 全域結論依完整2^|E| enumeration或等價global upper bound。

符號作用域

• X — 最大匹配
• G — 有限簡單圖

直觀、定義與常見誤解

先核matching合法。

maximum由全域比較／upper bound。

maximal、perfect、unique皆分開。

把不能再加邊的maximal當maximum，或把maximum自動當perfect/unique。

已採用的推導導讀

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

前置知識

• 圖匹配 — 合法matching定義。
• 最佳化問題 — 全域最大基數。

驗證界線

只處理edge count有界的完整有限圖。

not_formalized

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

下一個義務

加入Hall定理與matching algorithms。

同源結構化資料

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