第 218 題：有向無環圖的拓撲排序

原題與已知條件

finite digraph、完整vertex permutation與all-edge order責任。操作=toposort-order-audit；資料={"vertices":["v0","v1","v2","v3","v4","v5"],"edges":[["v0","v2"],["v0","v5"]],"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","v2"],["v0","v5"]],"candidate":["v0","v1","v2","v3","v4","v5"]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

定義與適用範圍

有限有向圖；候選必須是完整頂點排列，且每條邊均滿足起點在終點之前。

• mko-topological-ordering-dag

逐步推導

V=[v0, v1, v2, v3, v4, v5]; candidate=[v0, v1, v2, v3, v4, v5]

length(candidate)=6, |V|=6

count v0 in candidate

count(v0)=1

count v1 in candidate

count(v1)=1

count v2 in candidate

count(v2)=1

count v3 in candidate

count(v3)=1

count v4 in candidate

count(v4)=1

count v5 in candidate

count(v5)=1

edge v0→v2

pos(v0)=0; pos(v2)=2; 0<2: 是

edge v0→v5

pos(v0)=0; pos(v5)=5; 0<5: 是

permutation=是; every edge passes=是

valid topological order=是

逐步反向核對

• 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, v2], 0, 2, 是], [[v0, v5], 0, 5, 是]], 是, invalid_candidate_does_not_itself_prove_a_cycle)

本候選是否為有效拓撲次序：是。

本題覆核與來源綁定

覆核日期：2026-10-24

原題、答案、步驟表達式、數值 AST 與既有歷史保持原樣；原來的候選狀態屬於來源歷史，不覆寫為形式化證明。