OCME中英數學知識與推導English

查找相關知識與題目 →

第 19426 題：色數

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

返回所在分頁 98

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

R0037-19426 · q-20261014-advance-20261106-r01-chromatic-number-0076

原題與已知條件

完整有限簡單圖、proper vertex coloring與exact最小性證書。操作=chromatic-minimum-boundary；資料={"n":6,"edges":[[0,1],[0,5],[1,2],[2,3],[3,4],[4,5]],"colors":[0,1,0,1,0,1],"k":3}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

  • G001 — 完整有限簡單圖、proper vertex coloring與exact最小性證書。操作=chromatic-minimum-boundary；資料={"n":6,"edges":[[0,1],[0,5],[1,2],[2,3],[3,4],[4,5]],"colors":[0,1,0,1,0,1],"k":3}。請依 exact_ordered_tuple_declared_by_interface 欄序回答。

定義與適用範圍

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

逐步推導

S001 · implies

操作前

source operation=chromatic-minimum-boundary;original snapshot and mathematics retained

操作後

explicit ordered source output fields=[k, candidate_k_palette_valid, chromatic_number, k_equals_chromatic_number, boundary]

條件：無

原題快照保留歷史介面標記；本頁直接列原始欄位順序，不需JavaScript或查外部表。欄位名字本身不自動是數學證據，No依各題的聲稱範圍解讀。

步驟識別與依賴

規則：source_ordered_interface_explicit_without_javascript · 依賴：G001

S002 · implies

操作前

ACTUAL complete finite carrier Fin(6);ALL original canonical simple undirected edges=[[0, 1], [0, 5], [1, 2], [2, 3], [3, 4], [4, 5]]

操作後

use full original vertex/edge data;exact search domain n<=9;empty carrier and isolated vertices RETAINED

條件：無

頂點與邊完整且索引原封不動；此題族含n=0，不能套前題n至少1或把孤立點刪掉。後面實際palette標籤不能被semantic改名取代。

步驟識別與依賴

規則：chromatic_complete_graph_not_semantic_color_relabeling · 依賴：G001, S001

S003 · implies

操作前

original edge index=0;actual endpoint vertices=[0, 1];ORIGINAL palette labels=[0, 1]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S002

S004 · implies

操作前

original edge index=1;actual endpoint vertices=[0, 5];ORIGINAL palette labels=[0, 1]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S003

S005 · implies

操作前

original edge index=2;actual endpoint vertices=[1, 2];ORIGINAL palette labels=[1, 0]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S004

S006 · implies

操作前

original edge index=3;actual endpoint vertices=[2, 3];ORIGINAL palette labels=[0, 1]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S005

S007 · implies

操作前

original edge index=4;actual endpoint vertices=[3, 4];ORIGINAL palette labels=[1, 0]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S006

S008 · implies

操作前

original edge index=5;actual endpoint vertices=[4, 5];ORIGINAL palette labels=[0, 1]

操作後

endpoint labels different=是

條件：無

逐完整原邊查不同色，數字標籤只表示顏色的同異，不是色數。某次著色失敗不自動表示不存在別的合法著色。

步驟識別與依賴

規則：chromatic_every_original_edge_properness · 依賴：G001, S007

S009 · calculation

操作前

chromatic distinct used label count := sum(1, 1)

操作後

chromatic distinct used label count = 2

條件：無

依原始角色與已核中間量精確代值，保留參數、樣本、目標與分母，不交換未授權的聲稱。

步驟識別與依賴

規則：exact_rational_arithmetic · 依賴：G001, S008

S010 · implies

操作前

ORIGINAL complete color array=[0, 1, 0, 1, 0, 1];ALL edge properness flags=[是, 是, 是, 是, 是, 是]

操作後

increasingly ordered DISTINCT used labels=[0, 1];distinct count=2;proper=是;not max_label+1

條件：無

色數量是distinct labels數，不是最大標籤加1；空陣列給0。proper coloring若有效只給一個上界，不因greedy或label小就證最小。

步驟識別與依賴

規則：chromatic_distinct_label_count_not_palette_range_or_minimum · 依賴：G001, S009

S011 · implies

操作前

requested ACTUAL palette[0,3);ORIGINAL labels=[0, 1, 0, 1, 0, 1];per-vertex label<k flags=[是, 是, 是, 是, 是, 是];proper=是

操作後

within requested palette=是;THIS candidate upper certificate=是;distinct used-label count=2 is a DIFFERENT test

條件：無

即使用色數量≤k，若原標籤超出[0,k)仍不能讓這個指定palette證書通過。semantic改名不能換掉原資料；失敗只否決此候選，不宣稱圖無k-coloring。

步驟識別與依賴

規則：chromatic_original_palette_range_not_semantic_renaming · 依賴：G001, S010

S012 · implies

操作前

ACTUAL graph Fin(6);try palette[0,1);original vertex order0..5

操作後

search ALL earlier lexicographic prefixes:vertex order fixed,each color tried increasingly;only an actual earlier-edge conflict may prune

條件：無

每個k依序完整搜尋，不把一次greedy失敗當不可著色；每層原vertex順序與遞增顏色決定來源第一個lex witness。實際邊衝突可剪枝，否則必繼續或完整回退。

步驟識別與依賴

規則：chromatic_complete_lex_search_not_greedy_optimality · 依賴：G001, S011

S013 · implies

操作前

palette=1;original vertex=0;assigned ORIGINAL prefix=[];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S012

S014 · implies

操作前

palette=1;original vertex=1;assigned ORIGINAL prefix=[0];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[0];admissible extension=否

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S013

S015 · implies

操作前

palette=1;original vertex=1;original fixed prefix=[0];ALL colors0..0 attempted

操作後

no valid completion of this prefix in this palette

條件：無

此vertex所有合法palette標籤都已試完，故固定prefix沒有完成解；從根節點的此結論才排除整個k palette。

步驟識別與依賴

規則：chromatic_full_palette_exhaustion_at_prefix · 依賴：G001, S014

S016 · implies

操作前

palette=1;original prefix=[];vertex=0;chosen color=0;ALL its later completions exhausted

操作後

restore this unassigned coordinate and try the next ascending color

條件：無

子樹完整失敗才回退，此支所有後續選色都已被實際衝突或其完整子樹排除，不是測一次就換色。

步驟識別與依賴

規則：chromatic_exhausted_branch_backtracking_not_one_bad_sample · 依賴：G001, S015

S017 · implies

操作前

palette=1;original vertex=0;original fixed prefix=[];ALL colors0..0 attempted

操作後

no valid completion of this prefix in this palette

條件：無

此vertex所有合法palette標籤都已試完，故固定prefix沒有完成解；從根節點的此結論才排除整個k palette。

步驟識別與依賴

規則：chromatic_full_palette_exhaustion_at_prefix · 依賴：G001, S016

S018 · implies

操作前

palette[0,1) searched from EMPTY root prefix with full branch exclusions

操作後

NO proper coloring exists in this palette;any smaller palette is a subset of it

條件：無

完整根樹耗盡才給真正lower證據；任意更少顏色可嵌入此palette，故也被排除，不依賴任一greedy路徑。

步驟識別與依賴

規則：chromatic_actual_lower_palette_exhaustion · 依賴：G001, S017

S019 · implies

操作前

ACTUAL graph Fin(6);try palette[0,2);original vertex order0..5

操作後

search ALL earlier lexicographic prefixes:vertex order fixed,each color tried increasingly;only an actual earlier-edge conflict may prune

條件：無

每個k依序完整搜尋，不把一次greedy失敗當不可著色；每層原vertex順序與遞增顏色決定來源第一個lex witness。實際邊衝突可剪枝，否則必繼續或完整回退。

步驟識別與依賴

規則：chromatic_complete_lex_search_not_greedy_optimality · 依賴：G001, S018

S020 · implies

操作前

palette=2;original vertex=0;assigned ORIGINAL prefix=[];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S019

S021 · implies

操作前

palette=2;original vertex=1;assigned ORIGINAL prefix=[0];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[0];admissible extension=否

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S020

S022 · implies

操作前

palette=2;original vertex=1;assigned ORIGINAL prefix=[0];try next ascending color=1

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S021

S023 · implies

操作前

palette=2;original vertex=2;assigned ORIGINAL prefix=[0, 1];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S022

S024 · implies

操作前

palette=2;original vertex=3;assigned ORIGINAL prefix=[0, 1, 0];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[2];admissible extension=否

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S023

S025 · implies

操作前

palette=2;original vertex=3;assigned ORIGINAL prefix=[0, 1, 0];try next ascending color=1

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S024

S026 · implies

操作前

palette=2;original vertex=4;assigned ORIGINAL prefix=[0, 1, 0, 1];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S025

S027 · implies

操作前

palette=2;original vertex=5;assigned ORIGINAL prefix=[0, 1, 0, 1, 0];try next ascending color=0

操作後

ALL earlier adjacent vertices already using this label=[0, 4];admissible extension=否

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S026

S028 · implies

操作前

palette=2;original vertex=5;assigned ORIGINAL prefix=[0, 1, 0, 1, 0];try next ascending color=1

操作後

ALL earlier adjacent vertices already using this label=[];admissible extension=是

條件：無

列出此prefix嘗試顏色的全部先前真鄰點衝突；有衝突整個擴充都不合法，無衝突則還須遞迴核完其餘頂點，不把局部通過當全解。

步驟識別與依賴

規則：chromatic_every_prefix_color_conflict_or_recursion · 依賴：G001, S027

S029 · implies

操作前

FIRST completed vertex-order increasing-color search witness=[0, 1, 0, 1, 0, 1];palette size=2;ALL smaller palettes exhausted

操作後

every ORIGINAL edge endpoints different;constructive chi<= 2 and exhaustive chi>= 2;chi=2;first LEX witness retained

條件：無

找到的完整著色逐原邊合法給上界，前面的完整失敗palette給下界；二者相等才是exact最小值。因DFS原順序，這是來源第一個lex witness，非任意同色數解。非空無邊時第一個k=1給全0，不需虛構0色搜尋。

步驟識別與依賴

規則：chromatic_constructive_upper_and_exhausted_lower_tie_order · 依賴：G001, S028

S030 · implies

操作前

requested k=3;THIS supplied candidate validity=是;SEPARATE exact chi=2;SEPARATE canonical optimum witness=[0, 1, 0, 1, 0, 1]

操作後

k equals chromatic number=否;comparison does NOT certify supplied colors;at-most-k and exact-k-minimum are separate

條件：無

k與真色數相等可能為Yes而給定colors仍不合法，或合法k palette只給chi≤k而等號False。這些欄位各答各的，不把一個成功flag複製到另一欄。

步驟識別與依賴

規則：chromatic_k_equals_chi_independent_of_supplied_candidate · 依賴：G001, S029

逐步反向核對

  • S030 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S029 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S028 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S027 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • S026 · premise_and_result_audit — 回到原始資料與本步條件核對，不把單向推論誤稱等價。
  • 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 — 以精確有理數重算 chromatic distinct used label count，不以小數近似替代。
  • 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 — 回到原始資料與本步條件核對，不把單向推論誤稱等價。

結論

(3, 是, 2, 否, k_colorable_means_at_most_k_and_greedy_not_optimality_proof)

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

本題覆核與來源綁定

覆核日期：2026-10-26

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

來源雜湊與覆核憑證
  • input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
  • original question SHA-256: de4ff9713787f1462907a8ed52c5b116df000d80c040ccdc64170f36aa700e0f
  • candidate record SHA-256: ea5543f25a707f1b698be1efcdebe846cf0b2bb453a9cc5331fa749f7f82523f
  • semantic review receipt SHA-256: 065507b602ceee60cf47a700d387a51940e0c6724c35a3336a7a7948a199ed80
  • question-first witness SHA-256: 7203f33b030792559673b0fee520a8c0e70903c4dd970b35293aa40852f333d6
  • Lean: NOT_RUN · human review: NOT_PERFORMED
同源完整 JSON