原題與已知條件
完整有限無向無loop簡單圖。操作=bipartite-isolated-boundary;資料={"n":6,"edges":[[0,1],[1,2],[2,3],[3,4]],"parts":[1,1,1,0,1,0],"vertex":5}。請依 [vertex,incident_edges,assigned_part,whole_partition_proper,boundary] 欄序回答。
G001 — 完整有限無向無loop簡單圖。操作=bipartite-isolated-boundary;資料={"n":6,"edges":[[0,1],[1,2],[2,3],[3,4]],"parts":[1,1,1,0,1,0],"vertex":5}。請依 [vertex,incident_edges,assigned_part,whole_partition_proper,boundary] 欄序回答。
逐步推導
S001 · implies
操作前
complete undirected vertex carrier Fin(6);original edges=[[0, 1], [1, 2], [2, 3], [3, 4]]
操作後
normalized sorted simple edges=[[0, 1], [1, 2], [2, 3], [3, 4]];all vertices including isolates=[0, 1, 2, 3, 4, 5]
條件:無
逐邊先排端點再把邊作字典序排序,反向重複仍是同一邊而須拒絕;loop亦拒絕。完整載體包括沒有邊的頂點,不能從邊表遺漏它們。
步驟識別與依賴
規則:graph_complete_simple_carrier_normalized_edge_order · 依賴:G001
S002 · implies
操作前
total original part labels=[1, 1, 1, 0, 1, 0];complete carrier Fin(6)
操作後
part0=[3, 5];part1=[0, 1, 2, 4];disjoint full cover=是
條件:無
0、1標記的兩個逆像自動互斥,且每個原頂點恰有一標記;空部在無邊圖可以,不漏孤立點。這只核分部,還須逐邊跨部。
步驟識別與依賴
規則:bipartition_total_inverse_image_parts · 依賴:G001, S001
S003 · implies
操作前
parts:normalized edge index=0;edge=[0, 1];endpoint labels=[1, 1]
操作後
different endpoints=否;same-label conflict=是
條件:無
只檢同一條實際邊的兩端;不相鄰頂點重用標記不算衝突,某一條跨部亦不代表其他邊都通過。
步驟識別與依賴
規則:graph_every_edge_endpoint_constraint · 依賴:G001, S002
S004 · implies
操作前
parts:normalized edge index=1;edge=[1, 2];endpoint labels=[1, 1]
操作後
different endpoints=否;same-label conflict=是
條件:無
只檢同一條實際邊的兩端;不相鄰頂點重用標記不算衝突,某一條跨部亦不代表其他邊都通過。
步驟識別與依賴
規則:graph_every_edge_endpoint_constraint · 依賴:G001, S003
S005 · implies
操作前
parts:normalized edge index=2;edge=[2, 3];endpoint labels=[1, 0]
操作後
different endpoints=是;same-label conflict=否
條件:無
只檢同一條實際邊的兩端;不相鄰頂點重用標記不算衝突,某一條跨部亦不代表其他邊都通過。
步驟識別與依賴
規則:graph_every_edge_endpoint_constraint · 依賴:G001, S004
S006 · implies
操作前
parts:normalized edge index=3;edge=[3, 4];endpoint labels=[0, 1]
操作後
different endpoints=是;same-label conflict=否
條件:無
只檢同一條實際邊的兩端;不相鄰頂點重用標記不算衝突,某一條跨部亦不代表其他邊都通過。
步驟識別與依賴
規則:graph_every_edge_endpoint_constraint · 依賴:G001, S005
S007 · implies
操作前
original vertex=5;all complete graph edges=[[0, 1], [1, 2], [2, 3], [3, 4]];assigned part=0
操作後
all incident edges=[];whole partition proper=否;isolate stays in exactly one part
條件:無
沒有incident邊才允許任選該孤立點的部;它仍屬完整載體且需恰有一標記。改它不影響邊約束,但也不修正其他邊的原有衝突。
步驟識別與依賴
規則:bipartite_isolated_vertex_not_omitted_or_whole_graph_fixed · 依賴:G001, S006