逐步推導
S001 · implies
操作前
source roles = [vcover-minimal-vs-minimum-boundary]
操作後
derived = [[candidate, deletion_rows, inclusion_minimal, minimum_size, minimum, minimality_tests_agree, certificate]]
條件:無
本頁列完整來源欄序,不需JavaScript;LP三種mode雖同為6欄,角色仍由原mode選,不由答案形狀猜。
步驟識別與依賴
規則:source_ordered_fields_without_JS · 依賴:G001
S002 · implies
操作前
source roles = [[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7], [c0, l0_8], [c0, l0_9]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7], [c0, l0_8], [c0, l0_9]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
條件:無
carrier非空且至多12,edge端點依JS UTF16<排,再按來源English canonical排序;loop或反向重複edge拒絕,不把圖改成有向或edge cover。
步驟識別與依賴
規則:Vcover_complete_simple_undirected_graph_UTF16_then_English_order · 依賴:G001, S001
S003 · implies
操作前
source roles = [0, [c0, l0_0], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S002
S004 · implies
操作前
source roles = [1, [c0, l0_1], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S003
S005 · implies
操作前
source roles = [2, [c0, l0_2], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S004
S006 · implies
操作前
source roles = [3, [c0, l0_3], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S005
S007 · implies
操作前
source roles = [4, [c0, l0_4], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S006
S008 · implies
操作前
source roles = [5, [c0, l0_5], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S007
S009 · implies
操作前
source roles = [6, [c0, l0_6], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S008
S010 · implies
操作前
source roles = [7, [c0, l0_7], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S009
S011 · implies
操作前
source roles = [8, [c0, l0_8], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S010
S012 · implies
操作前
source roles = [9, [c0, l0_9], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[否, 是], 是]
條件:無
這條edge至少一個endpoint被選才covered,逐完整edge表核對,不用頂點數猜測。
步驟識別與依賴
規則:Vcover_EVERY_edge_selected_endpoint_disjunction · 依賴:G001, S011
S013 · implies
操作前
source roles = [[[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]]]
操作後
derived = [是, null, []]
條件:無
全邊合取,首uncovered edge保來源canonical次序;沒有則null,不用False代null。isolated點沒有責任edge,故可選可不選。
步驟識別與依賴
規則:Vcover_COMPLETE_edge_conjunction_FIRST_uncovered_or_NULL · 依賴:G001, S012
S014 · implies
操作前
source roles = [l0_0, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 否], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S013
S015 · implies
操作前
source roles = [l0_1, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 否], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S014
S016 · implies
操作前
source roles = [l0_2, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 否], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S015
S017 · implies
操作前
source roles = [l0_3, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 否], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S016
S018 · implies
操作前
source roles = [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 否], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S017
S019 · implies
操作前
source roles = [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 否], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S018
S020 · implies
操作前
source roles = [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 否], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S019
S021 · implies
操作前
source roles = [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_8, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 否], [[c0, l0_8], 是], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S020
S022 · implies
操作前
source roles = [l0_8, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_9], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 否], [[c0, l0_9], 是]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S021
S023 · implies
操作前
source roles = [l0_9, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9]]
操作後
derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8], [[[c0, l0_0], 是], [[c0, l0_1], 是], [[c0, l0_2], 是], [[c0, l0_3], 是], [[c0, l0_4], 是], [[c0, l0_5], 是], [[c0, l0_6], 是], [[c0, l0_7], 是], [[c0, l0_8], 是], [[c0, l0_9], 否]], 否]
條件:無
每次只刪這一點並重新核全部edges,不能把別次刪除結果拿來沿用。
步驟識別與依賴
規則:Vcover_EACH_single_vertex_deletion_complete_edge_test · 依賴:G001, S022
S024 · implies
操作前
source roles = [[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7], [c0, l0_8], [c0, l0_9]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[l0_0, [l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_1, [l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_2, [l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_3, [l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7, l0_8, l0_9], 否], [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7, l0_8, l0_9], 否], [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_8, l0_9], 否], [l0_8, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_9], 否], [l0_9, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8], 否]]]
操作後
derived = [2048, [0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 11, 1], [1, [c0]], 是, 1, 否, 否]
條件:無
對全部2^n subsets按大小計cover個數;較小size個數全0給下界,實際witness給達到。因cover對superset單調,若任一proper subset是cover,必有一次single deletion仍cover,故逐刪測試恰驗inclusion-minimal;不等於minimum。最後只比較兩旗標,兩者False也可相等。
步驟識別與依賴
規則:Vcover_ALL_subsets_cardinality_counts_minimum_witness_and_GENERAL_minimality · 依賴:G001, S023
結論
([l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], [[l0_0, [l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_1, [l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_2, [l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_3, [l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7, l0_8, l0_9], 否], [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7, l0_8, l0_9], 否], [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7, l0_8, l0_9], 否], [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_8, l0_9], 否], [l0_8, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_9], 否], [l0_9, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7, l0_8], 否]], 是, 1, 否, 否, inclusion_minimal_means_no_single_deletion_while_minimum_compares_all_covers)
依上列完整代值及條件核對得到原題答案;原題編號、格式與狀態保持不變。