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

原題與已知條件

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"]]}。請依 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"]]}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

定義與適用範圍

Kahn 停住時另列逐邊核對的有向環；環上的嚴格位置不等式使拓撲次序不可能。

• mko-topological-ordering-dag

逐步推導

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

all directed edges=[[v0, v1], [v0, v2], [v1, v2], [v2, v0]]

remaining=[v0, v1, v2, v3, v4, v5]; active edges=[[v0, v1], [v0, v2], [v1, v2], [v2, v0]]

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v3, 0], [v4, 0], [v5, 0]]; sources=[v3, v4, v5]

zero-indegree choices=[v3, v4, v5]

choose=v3; new prefix=[v3]

remaining=[v0, v1, v2, v4, v5]; active edges=[[v0, v1], [v0, v2], [v1, v2], [v2, v0]]

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v4, 0], [v5, 0]]; sources=[v4, v5]

zero-indegree choices=[v4, v5]

choose=v4; new prefix=[v3, v4]

remaining=[v0, v1, v2, v5]; active edges=[[v0, v1], [v0, v2], [v1, v2], [v2, v0]]

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v5, 0]]; sources=[v5]

zero-indegree choices=[v5]

choose=v5; new prefix=[v3, v4, v5]

remaining=[v0, v1, v2]; active edges=[[v0, v1], [v0, v2], [v1, v2], [v2, v0]]

indegrees=[[v0, 1], [v1, 1], [v2, 2]]; sources=[]

cycle candidate edge v0→v2

edge present: 是

cycle candidate edge v2→v0

edge present: 是

[v0, v2, v0]

pos(v0) < pos(v2) < pos(v0) is impossible

逐步反向核對

• S011 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。
• S010 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。
• S009 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。
• S008 · premise_and_result_audit — 核對完整頂點與邊；一個失敗次序不等於有環，全部合法分支不能漏列。
• 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], [v3, v4, v5], v3], [[v0, v1, v2, v4, v5], [v4, v5], v4], [[v0, v1, v2, v5], [v5], v5]], [v0, v1, v2], [v0, v2, v0], 是, 是, 否, directed_cycle_blocks_every_topological_order_while_multiple_orders_and_empty_edges_are_allowed)

上述完整代值與條件核對得到原題答案；欄位次序及真假標記保持原始合約。

本題覆核與來源綁定

覆核日期：2026-10-26

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