# 第 850 題：有向無環圖的拓撲排序 [返回所在分頁 5](https://ocme.evemisslab.com/zh-Hant/questions/page/5/) [← 逐題詳解目錄](https://ocme.evemisslab.com/zh-Hant/questions/) · [原題批次](https://ocme.evemisslab.com/zh-Hant/practice/batch-20261015-advance-20261116-r06-topological-ordering-dag-foundations/#q-20261015-advance-20261116-r06-topological-ordering-dag-0100) 本頁是已完成第二對話 AI 數理與中英語義覆核的教學詳解，只支持本題明示的模型與前提。沒有人工審查或新 Lean 證明，也不提升原題或 MKO 的 Canonical 真值狀態。 P1000-0850 · q-20261015-advance-20261116-r06-topological-ordering-dag-0100 ## 原題與已知條件 finite digraph、完整vertex permutation與all-edge order責任。操作=toposort-cycle-boundary；資料={"vertices":["v0","v1","v2","v3","v4","v5"],"edges":[["v0","v1"],["v1","v2"],["v2","v0"],["v0","v2"],["v0","v5"],["v1","v3"]]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。 - G001 — finite digraph、完整vertex permutation與all-edge order責任。操作=toposort-cycle-boundary；資料={"vertices":["v0","v1","v2","v3","v4","v5"],"edges":[["v0","v1"],["v1","v2"],["v2","v0"],["v0","v2"],["v0","v5"],["v1","v3"]]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。 ## 定義與適用範圍 Kahn 停住時另列逐邊核對的有向環；環上的嚴格位置不等式使拓撲次序不可能。 - [mko-topological-ordering-dag](https://ocme.evemisslab.com/zh-Hant/mko/mko-topological-ordering-dag/) ## 逐步推導 S001 · implies操作前 V=[v0, v1, v2, v3, v4, v5] 操作後 all directed edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v1, v3], [v2, v0]] 條件：無 這是完整指定的有限有向圖，不是圖論術語的完全圖。 步驟識別與依賴規則：full_directed_graph · 依賴：G001 S002 · implies操作前 remaining=[v0, v1, v2, v3, v4, v5]; active edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v1, v3], [v2, v0]] 操作後 indegrees=[[v0, 1], [v1, 1], [v2, 2], [v3, 1], [v4, 0], [v5, 1]]; sources=[v4] 條件：無 每次都以尚未移除的邊重新計算入度，不以原始入度硬套全部步驟。 步驟識別與依賴規則：remaining_indegree · 依賴：G001, S001 S003 · implies操作前 zero-indegree choices=[v4] 操作後 choose=v4; new prefix=[v4] 條件：無 按已宣告的字典序挑第一個零入度點，並移除它發出的邊。 步驟識別與依賴規則：lexicographic_kahn_choice · 依賴：G001, S002 S004 · implies操作前 remaining=[v0, v1, v2, v3, v5]; active edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v1, v3], [v2, v0]] 操作後 indegrees=[[v0, 1], [v1, 1], [v2, 2], [v3, 1], [v5, 1]]; sources=[] 條件：無 每次都以尚未移除的邊重新計算入度，不以原始入度硬套全部步驟。 步驟識別與依賴規則：remaining_indegree · 依賴：G001, S003 S005 · implies操作前 cycle candidate edge v0→v2 操作後 edge present: 是 條件：無 逐邊核對回到起點的有向閉路，不只憑Kahn停住的印象宣告。 步驟識別與依賴規則：cycle_edge_witness · 依賴：G001, S004 S006 · implies操作前 cycle candidate edge v2→v0 操作後 edge present: 是 條件：無 逐邊核對回到起點的有向閉路，不只憑Kahn停住的印象宣告。 步驟識別與依賴規則：cycle_edge_witness · 依賴：G001, S005 S007 · implies操作前 [v0, v2, v0] 操作後 pos(v0) < pos(v2) < pos(v0) is impossible 條件：無 若有拓撲次序，沿完整有向環的嚴格位置不等式會要求起點先於自己，矛盾。 步驟識別與依賴規則：strict_order_cycle_contradiction · 依賴：G001, S006 ## 逐步反向核對 - S007 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S006 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S005 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S004 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S003 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S002 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 - S001 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。 ## 結論 ([[[v0, v1, v2, v3, v4, v5], [v4], v4]], [v0, v1, v2, v3, v5], [v0, v2, v0], 是, 是, 否, directed_cycle_blocks_every_topological_order_while_multiple_orders_and_empty_edges_are_allowed) 上述完整代值與條件核對得到原題答案；欄位次序及真假標記保持原始合約。 ## 本題覆核與來源綁定 覆核日期：2026-10-26 原題、答案、步驟表達式、數值 AST 與既有歷史保持原樣；原來的候選狀態屬於來源歷史，不覆寫為形式化證明。 來源雜湊與覆核憑證 - input commit: 0f7be61e2c22317a4075561dc822c87d881a50db - original question SHA-256: 376ac061e3e66ba551b0c86e5d6632a384cfe8efd03c7e5242e663a4f22c7dfa - candidate record SHA-256: e085579ff0f49b9468c126049e100b699607a8f3e27f7506fbdf4e0143c53e5d - semantic review receipt SHA-256: 6c2c6d46aded7582a11ac41a8c0b3bdde2669a53bdb6e796eea2039994a02772 - question-first witness SHA-256: 77e43898df9efdbf8094ad81fe4ab91cf4b4bd82f481eb9b4699b73cb4da612b - Lean: NOT_RUN · human review: NOT_PERFORMED [同源完整 JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261015-advance-20261116-r06-topological-ordering-dag-0100.json)