OCME中英數學知識與推導English

查找相關知識與題目 →

第 12489 題：圖同構

本頁導覽
  1. 原題與已知條件
  2. 定義與適用範圍
  3. 逐步推導
  4. 逐步反向核對
  5. 結論
  6. 本題覆核與來源綁定

返回所在分頁 63

← 逐題詳解目錄 · 原題批次

R0023-12489 · q-20261013-advance-20261026-r06-graph-isomorphism-0064

原題與已知條件

完整有限簡單圖與明示頂點映射。操作=graphiso-qualification；資料={"n":6,"left_edges":[[0,1],[1,2],[2,3],[3,4],[4,5]],"right_edges":[[0,1],[1,4],[2,4],[2,5],[3,5]],"mapping":[0,1,4,2,5,3]}。請依 [n,mapping,bijective,bad_pairs,isomorphism] 欄序回答。

  • G001 — 完整有限簡單圖與明示頂點映射。操作=graphiso-qualification；資料={"n":6,"left_edges":[[0,1],[1,2],[2,3],[3,4],[4,5]],"right_edges":[[0,1],[1,4],[2,4],[2,5],[3,5]],"mapping":[0,1,4,2,5,3]}。請依 [n,mapping,bijective,bad_pairs,isomorphism] 欄序回答。

定義與適用範圍

沿用原題明示的論域、假設與來源 MKO 定義。本題已完成第二對話數理與中英語義覆核，並由原始參數逐題獨立重算模型、答案與每個算術步驟；原題仍為 candidate。

逐步推導

S001 · implies

操作前

source graph:carrier Fin(6);raw undirected edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]

操作後

canonical simple edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]];loops and repeated undirected edges absent

條件：無

每條邊端點正規化小者在前再排序；反向重複仍是重複，不自行刪掉非法紀錄；保留所有孤立頂點。

步驟識別與依賴

規則：complete_simple_graph_canonical_edges · 依賴：G001

S002 · implies

操作前

target graph:carrier Fin(6);raw undirected edges=[[0, 1], [1, 4], [2, 4], [2, 5], [3, 5]]

操作後

canonical simple edges=[[0, 1], [1, 4], [2, 4], [2, 5], [3, 5]];loops and repeated undirected edges absent

條件：無

每條邊端點正規化小者在前再排序；反向重複仍是重複，不自行刪掉非法紀錄；保留所有孤立頂點。

步驟識別與依賴

規則：complete_simple_graph_canonical_edges · 依賴：G001, S001

S003 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=0

操作後

source fiber=[0];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S002

S004 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=1

操作後

source fiber=[1];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S003

S005 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=2

操作後

source fiber=[3];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S004

S006 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=3

操作後

source fiber=[5];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S005

S007 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=4

操作後

source fiber=[2];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S006

S008 · implies

操作前

complete mapping=[0, 1, 4, 2, 5, 3];target label=5

操作後

source fiber=[4];exactly one=是

條件：無

同樣有限大小的完整總映射，要每個目標標籤恰有一個原像才雙射，不把合型當雙射。

步驟識別與依賴

規則：finite_vertex_map_each_target_fiber · 依賴：G001, S007

S009 · implies

操作前

n=6;all target fibers=[[0], [1], [3], [5], [2], [4]]

操作後

bijective=是;empty carrier uses unique empty map

條件：無

空載體唯一空映射雙射是合法邊界；此步只核映射責任，沒有核任何鄰接性。

步驟識別與依賴

規則：whole_bijection_including_empty_carrier · 依賴：G001, S008

S010 · implies

操作前

source unordered pair=[0, 1];mapped pair=[0, 1]

操作後

source adjacent=是;target adjacent=是;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S009

S011 · implies

操作前

source unordered pair=[0, 2];mapped pair=[0, 4]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S010

S012 · implies

操作前

source unordered pair=[0, 3];mapped pair=[0, 2]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S011

S013 · implies

操作前

source unordered pair=[0, 4];mapped pair=[0, 5]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S012

S014 · implies

操作前

source unordered pair=[0, 5];mapped pair=[0, 3]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S013

S015 · implies

操作前

source unordered pair=[1, 2];mapped pair=[1, 4]

操作後

source adjacent=是;target adjacent=是;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S014

S016 · implies

操作前

source unordered pair=[1, 3];mapped pair=[1, 2]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S015

S017 · implies

操作前

source unordered pair=[1, 4];mapped pair=[1, 5]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S016

S018 · implies

操作前

source unordered pair=[1, 5];mapped pair=[1, 3]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S017

S019 · implies

操作前

source unordered pair=[2, 3];mapped pair=[4, 2]

操作後

source adjacent=是;target adjacent=是;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S018

S020 · implies

操作前

source unordered pair=[2, 4];mapped pair=[4, 5]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S019

S021 · implies

操作前

source unordered pair=[2, 5];mapped pair=[4, 3]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S020

S022 · implies

操作前

source unordered pair=[3, 4];mapped pair=[2, 5]

操作後

source adjacent=是;target adjacent=是;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S021

S023 · implies

操作前

source unordered pair=[3, 5];mapped pair=[2, 3]

操作後

source adjacent=否;target adjacent=否;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S022

S024 · implies

操作前

source unordered pair=[4, 5];mapped pair=[5, 3]

操作後

source adjacent=是;target adjacent=是;iff=是

條件：無

每個無序來源對都比兩側真假，包含來源非邊；映射碰撞時目標對角不會是簡單圖邊。即使雙射失敗仍保留完整鄰接失敗清單。

步驟識別與依賴

規則：graph_every_edge_and_nonedge_iff · 依賴：G001, S023

S025 · implies

操作前

mapping bijective=是;all bad adjacency pairs=[]

操作後

adjacency iff=是;specified map isomorphism=是

條件：無

雙射與完整鄰接iff是不同責任；不讓只有其中一條就變成同構。此處只驗明示映射，不是搜尋所有映射。

步驟識別與依賴

規則：graph_bijection_and_adjacency_separate_conjunction · 依賴：G001, S024

逐步反向核對

  • S025 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S024 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S023 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S022 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S021 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S020 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S019 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S018 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S017 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S016 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S015 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S014 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S013 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S012 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • 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 — 回到原始資料與本步條件核對，不把單向推論誤稱等價。

結論

(6, [0, 1, 4, 2, 5, 3], 是, [], 是)

依上列完整代值及條件核對得到原題答案；原題編號、格式與狀態保持不變。

本題覆核與來源綁定

覆核日期：2026-10-26

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

來源雜湊與覆核憑證
  • input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
  • original question SHA-256: caf16512c342231394abaae99565a2aa4e587f202f52bab68902cd9c8322cfba
  • candidate record SHA-256: 5ecd43c52da7849e69d1589456c59d7398b996affb4bd101841e40d8f6f78791
  • semantic review receipt SHA-256: f783e81f44ff0faa13dbf948657e9187244a59a809ebdf96f22cca24966649ff
  • question-first witness SHA-256: 49a50ed0550be55124d6562260c2ccf4fa6d3f316d7ad9d0d32174400e362e18
  • Lean: NOT_RUN · human review: NOT_PERFORMED
同源完整 JSON