有向無環圖的拓撲排序

數學敘述

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唯一。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 有限有向圖 — graph model。
• 實數大小與順序 — ordering。
• 算法正確性 — Kahn invariant。
• 數學歸納法 — iterative source removal一般證明。

驗證界線

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

not_formalized

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

下一個義務

加入partial-order linear extensions。

同源結構化資料

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