# 二分圖

有限無向簡單圖若全體頂點可分為兩個互斥部分且每條邊跨部，則為二分圖。

mko-bipartite-graph · definition · v0.10.0



## 數學敘述

核完整頂點cover、兩部互斥及全部邊跨部。失敗partition不證非二分；奇cycle可作否證。孤立頂點可置任一部，空部是否允許須明示。





## 代表公式（精確 TeX）

B(G)





## 成立條件


- 完整有限無向無loop簡單圖。
- 本輪允許無邊圖的一部為空；所有頂點仍須被cover。





## 符號作用域


- B — 二分圖
- G — 有限簡單圖





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

兩部互斥且聯集為V。

每條邊兩端不同部。

奇cycle是非二分證書；單一partition失敗不是。

漏掉孤立點、由一個失敗partition判非二分，或要求非相鄰點顏色不同。





## 已採用的推導導讀

[含孤立點的二分證書](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-bipartite-graph-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 完整頂點邊集合。
- [子集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-subset/) — 兩部為頂點子集。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — 二著色等價表示。





## 驗證界線

只處理有限無向簡單圖；不外推有向圖。

not_formalized

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





## 下一個義務

加入matching與二分圖定理。





## 同源結構化資料

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

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