# 連通分量

有限無向簡單圖中，由存在路徑所定義的頂點等價類恰為連通分量。

mko-connected-component · definition · v0.10.0



## 數學敘述

在有限無向無loop簡單圖中，u與v連通若存在u到v的path；長度0 path保證反身性。此關係的等價類為互斥且覆蓋全部頂點的最大連通分量；孤立頂點形成單點分量。





## 代表公式（精確 TeX）

Q(G)





## 成立條件


- 頂點標籤0到n-1與完整無向簡單邊集合明示。
- 可達性由完整BFS／DFS核對；不切換到有向圖的weak或strong connectivity。





## 符號作用域


- Q — 連通分量分割
- G — 有限無向簡單圖





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

每個頂點透過長度0 path與自身連通。

BFS／DFS從起點得到其精確分量。

所有分量互斥並覆蓋頂點；孤立點不能遺漏。

忽略孤立頂點、把一條走訪順序當分量證書，或混用有向圖強／弱連通。





## 已採用的推導導讀

[連通分量：以完整 BFS 求出有限簡單圖的全部分量](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-connected-component-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [圖walk與simple path](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph-walk-simple-path/) — 連通性由存在path定義。
- [等價關係](https://ocme.evemisslab.com/zh-Hant/mko/mko-equivalence-relation/) — 可達性在無向圖上形成等價關係。
- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 完整頂點與邊集合提供搜尋空間。





## 驗證界線

只處理完整有限無向簡單圖；不外推有向、無限或動態圖。

not_formalized

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





## 下一個義務

加入分量縮約與圖演算法複雜度。





## 同源結構化資料

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

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