# 最大匹配

最大匹配是在完整有限圖全部合法matching中邊數最大者；可有多個且不必perfect。

mko-maximum-matching · definition · v0.10.0



## 數學敘述

本輪對小型完整有限簡單圖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。





## 已採用的推導導讀

[三邊圖的全部八個matching候選](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-maximum-matching-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [圖匹配](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph-matching/) — 合法matching定義。
- [最佳化問題](https://ocme.evemisslab.com/zh-Hant/mko/mko-optimization-problem/) — 全域最大基數。





## 驗證界線

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

not_formalized

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





## 下一個義務

加入Hall定理與matching algorithms。





## 同源結構化資料

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

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