# 生成樹

生成樹是包含父圖全部頂點的連通無圈子圖。

mko-spanning-tree · definition · v0.10.0



## 數學敘述

完整有限connected simple parent graph與選邊子圖。核選邊存在、全頂點、connected/acyclic；connected+n−1 edges或acyclic+n−1 edges可作exact certificate，n−1 alone不足。保留single vertex；不作weighted/MST claim。





## 代表公式（精確 TeX）

T(G)





## 成立條件


- 完整有限無向無loop簡單父圖。
- 選邊以parent edge indices。





## 符號作用域


- T — 生成樹
- G — 父圖





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

包含全部parent vertices。

選邊subgraph為tree。

n−1 alone不足；single vertex合法；不宣稱minimum。

只數n−1邊就叫tree，或把spanning tree當MST。





## 已採用的推導導讀

[方形父圖內的spanning tree](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-spanning-tree-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [非空有限樹：連通、無環與唯一道路](https://ocme.evemisslab.com/zh-Hant/mko/mko-tree/) — connected acyclic。
- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 父圖與subgraph。
- [連通分量](https://ocme.evemisslab.com/zh-Hant/mko/mko-connected-component/) — parent connectedness。





## 驗證界線

只處理完整有限unweighted graph。

not_formalized

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





## 下一個義務

加入minimum spanning tree。





## 同源結構化資料

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

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