# 第 203 題：有向無環圖的拓撲排序 [返回所在分頁 2](https://ocme.evemisslab.com/zh-Hant/questions/page/2/) [← 逐題詳解目錄](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-0003) 本頁是已完成第二對話 AI 數理與中英語義覆核的教學詳解，只支持本題明示的模型與前提。沒有人工審查或新 Lean 證明，也不提升原題或 MKO 的 Canonical 真值狀態。 P250-0203 · q-20261015-advance-20261116-r06-topological-ordering-dag-0003 ## 原題與已知條件 finite digraph、完整vertex permutation與all-edge order責任。操作=toposort-order-audit；資料={"vertices":["v0","v1","v2","v3","v4","v5"],"edges":[["v0","v1"],["v0","v2"]],"candidate":["v0","v1","v2","v3","v4","v5"]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。 - G001 — finite digraph、完整vertex permutation與all-edge order責任。操作=toposort-order-audit；資料={"vertices":["v0","v1","v2","v3","v4","v5"],"edges":[["v0","v1"],["v0","v2"]],"candidate":["v0","v1","v2","v3","v4","v5"]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。 ## 定義與適用範圍 有限有向圖；候選必須是完整頂點排列，且每條邊均滿足起點在終點之前。 - [mko-topological-ordering-dag](https://ocme.evemisslab.com/zh-Hant/mko/mko-topological-ordering-dag/) ## 逐步推導 S001 · implies操作前 V=[v0, v1, v2, v3, v4, v5]; candidate=[v0, v1, v2, v3, v4, v5] 操作後 length(candidate)=6, |V|=6 條件：無 拓撲次序必須是全部頂點恰出現一次的排列；先核對長度。 步驟識別與依賴規則：permutation_domain · 依賴：G001 S002 · implies操作前 count v0 in candidate 操作後 count(v0)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S001 S003 · implies操作前 count v1 in candidate 操作後 count(v1)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S002 S004 · implies操作前 count v2 in candidate 操作後 count(v2)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S003 S005 · implies操作前 count v3 in candidate 操作後 count(v3)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S004 S006 · implies操作前 count v4 in candidate 操作後 count(v4)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S005 S007 · implies操作前 count v5 in candidate 操作後 count(v5)=1 條件：無 逐頂點核對出現次數，不漏頂點也不重複。 步驟識別與依賴規則：permutation_multiplicity · 依賴：G001, S006 S008 · implies操作前 edge v0→v1 操作後 pos(v0)=0; pos(v1)=1; 0<1: 是 條件：無 每條有向邊都要求起點出現在終點之前；位置從 0 開始。 步驟識別與依賴規則：directed_edge_order · 依賴：G001, S007 S009 · implies操作前 edge v0→v2 操作後 pos(v0)=0; pos(v2)=2; 0<2: 是 條件：無 每條有向邊都要求起點出現在終點之前；位置從 0 開始。 步驟識別與依賴規則：directed_edge_order · 依賴：G001, S008 S010 · implies操作前 permutation=是; every edge passes=是 操作後 valid topological order=是 條件：無 完整排列與逐邊限制必須同時成立；這正是本有限圖的拓撲次序定義。 步驟識別與依賴規則：definition_conjunction · 依賴：G001, S009 ## 逐步反向核對 - S010 · premise_and_result_audit — 候選次序失敗不代表圖必有環，可能只是給錯了排列。 - S009 · premise_and_result_audit — 一條邊通過不能代替全部邊通過。 - S008 · premise_and_result_audit — 一條邊通過不能代替全部邊通過。 - S007 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S006 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S005 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S004 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S003 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S002 · premise_and_result_audit — 完整排列要求每個次數都是 1，且沒有域外標籤。 - S001 · premise_and_result_audit — 只有底層集合相同還不夠，重複列出頂點仍可能違規。 ## 結論 ([v0, v1, v2, v3, v4, v5], [v0, v1, v2, v3, v4, v5], 是, [[[v0, v1], 0, 1, 是], [[v0, v2], 0, 2, 是]], 是, invalid_candidate_does_not_itself_prove_a_cycle) 本候選是否為有效拓撲次序：是。 ## 本題覆核與來源綁定 覆核日期：2026-10-24 原題、答案、步驟表達式、數值 AST 與既有歷史保持原樣；原來的候選狀態屬於來源歷史，不覆寫為形式化證明。 來源雜湊與覆核憑證 - input commit: 0f7be61e2c22317a4075561dc822c87d881a50db - original question SHA-256: 6761578cbe919287cbfed6db034ef5cd66ec10475bb8a6d42dd67e917739fb72 - candidate record SHA-256: 724665f1c74aa4bc3f9bfa3fb2809f13c2b9d4872fe1e1100a051259a504f67a - semantic review receipt SHA-256: 4727d1bd957a9b7f6cadb7972ddb5ab80a31f5259dc5394c1dff2b71944ed36b - question-first witness SHA-256: 51e18649133238ac992229f6e16542a5f3af53ca73b2262ab0524508ea937dee - Lean: NOT_RUN · human review: NOT_PERFORMED [同源完整 JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261015-advance-20261116-r06-topological-ordering-dag-0003.json)