# 有向無環圖的拓撲排序

有限有向圖存在topological ordering恰當其無directed cycle。

mko-topological-ordering-dag · theorem · v0.10.0



## 數學敘述

candidate ordering須是全部vertices的permutation，逐edge驗pos(u)<pos(v)。小型graph完整枚舉所有valid orders；Kahn程序每步選lexicographically first zero-indegree source、刪除並記錄invariant。若無source但尚有vertices，輸出explicit directed cycle witness。multiple orders與empty-edge保留；invalid candidate不等於graph有cycle，亦不與topological-space混同。





## 代表公式（精確 TeX）

O(G,p)=b





## 成立條件


- finite unique vertices與loop-free duplicate-free directed edges。
- 完整permutation/cycle enumeration限bounded graph。





## 符號作用域


- O — 候選拓撲次序有效性判定
- G — 有限有向圖
- p — 頂點排列
- b — 候選次序有效性的布林值





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

candidate permutation與all-edge audit。

完整列舉與Kahn trace互相交叉核對。

cycle witness保護iff反向。

記號對齊候選：b 判定指定排列 p 是否尊重 G 的每一條有向邊，不直接表示 G 無圈。有限圖無圈等價於存在某個有效拓撲排列，是另外含存在量詞的圖性質；無效候選不代表圖有圈。

一個invalid order就判graph cyclic，或默認topological order唯一。





## 已採用的推導導讀

[三頂點DAG的全部排列與Kahn trace](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-topological-ordering-dag-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限有向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-finite-directed-graph/) — graph model。
- [實數大小與順序](https://ocme.evemisslab.com/zh-Hant/mko/mko-order-relation/) — ordering。
- [算法正確性](https://ocme.evemisslab.com/zh-Hant/mko/mko-algorithm-correctness/) — Kahn invariant。
- [數學歸納法](https://ocme.evemisslab.com/zh-Hant/mko/mko-mathematical-induction/) — iterative source removal一般證明。





## 驗證界線

finite enumeration只證指定graph；一般iff需induction。

not_formalized

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





## 下一個義務

加入partial-order linear extensions。





## 同源結構化資料

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

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