交付一份弦图识别与团结构证书 ​

弦图识别与团结构路线的终点是一份可以脱离搜索程序重新检查的记录。输入是一张简单无向图；输出既包括算法怎样选择顶点，也包括它为何能证明着色最优、团节点没有漏项、树上的同一顶点没有断开。

下载标准库算法与核验器及完整结果JSON。程序没有第三方依赖，普通运行与 python -O 都执行显式检查。运行会在脚本旁写出同名结果JSON；不能在只读目录里把写入失败误判为算法失败。

一、固定身份与精化接口 ​

顶点身份为整数0,…,n−1，每条无向边只在输入边表出现一次，两个端点不同。自环、重复边（含反向重复）和越界端点均属于格式错误；函数prepare_graph保留输入所决定的邻接顺序。输入顺序会影响并列选择，顶点和边的数学身份不变。

先在六元素块 [0,1,2,3,4,5] 上手算refine([4,1,4])，再算refine([2,1,5])，最后pop_first。预期块依次为 [4,1]；[0,2,3,5]、[1]；[4]；[2,5]；[0,3]，最后取出1。提交每次移动后的owner及块首尾检查，解释重复4为何只移动一次。

必须保留“新交块位于对应旧余块之前”这个位置关系。若把全体选中元素集中为一个总前块，即使最终元素集合相同，也已经破坏旧优先次序。

二、逐轮运行六点图 ​

固定n=6，边表依次为01、02、12、23、04、14、45。运行lexbfs(adj, record_trace=True)，提交每轮pick、before和after；这一开关会生成完整块快照，供小例子检查，不纳入核心线性界。

搜索序应为σ=[0,1,2,4,3,5]，反序π=[5,3,4,2,1,0]。选2后块为 [4]；[3]；[5]：4在第一轮就邻接0，标签的首项比3刚取得的标签大。因此本轮邻居3只能在旧低优先块内前移，不能越过4。

附件每条边恰触发一次活动端点移动，本例m=7，所以moved_elements必须为7。若报告14，请区分“扫描两份邻接记录”与“只有另一端未选时才移动”这两种计数。

三、核候选序与颜色上下界 ​

独立用verify_peo检查π，保存每点N⁺及其位置最早的p。点4、2的更晚邻居都为{0,1}，p却是1，因为它在π中先于0；按编号取0虽然在本例仍碰巧相邻，却没有实现证明中的接口。

按反π贪心着色，按顶点0,…,5列出颜色[0,1,2,0,2,0]。逐条核7条边两端异色，并交出三点团{0,1,2}。三色方案是上界，三点团是下界，两者相等才证明χ=3；只展示“程序用了三色”并不排除本来可以两色。

再列出全部极大团：{4,5}、{2,3}、{0,1,4}、{0,1,2}。其中两份大小2，两份大小3。报告要分别回答“最大团大小是多少”“一个最大团是什么”“全部极大团有哪些”，不能把三个问题混成一个列表。

候选袋Cᵥ={v}∪N⁺(v)最多n份。请指出为什么每个极大团必等于其最早顶点的候选袋，再解释严格子袋筛除为何不丢失极大团。小图用全部顶点子集枚举对照是独立核验，不是正式建树算法的一部分。

四、把极大团连成树，并验运行交 ​

按附件团序编号A={4,5}、B={2,3}、C={0,1,4}、D={0,1,2}。团树边为AC、CD、DB，交集依次{4}、{0,1}、{2}，总权4。全部袋大小之和减n也是2+2+3+3−6=4。

逐顶点提交出现节点：0、1出现于C/D；2出现于B/D；3只在B；4出现于A/C；5只在A。这些节点分别诱导连通子树。总权等于上界与逐顶点连通应相互验证，而非只核树有三条边。

结构迁移：删掉CD，改接CB，保留AC和BD。它仍是一棵四节点树，但权降为2，0、1的路径C—B—D穿过不含它们的B，运行交失败。若删掉较小极大团A、B，顶点3、5又完全丢失。记录这两个不同的错误，分别对应错误连边与不完整团族。

五、负结果必须指向原图 ​

对四圈01、12、23、30运行同一流程。搜索序为[0,1,3,2]，反序[2,3,1,0]在v=2处失败：更晚邻居3、1之间无边。因为LexBFS在弦图上的正确性已经证明，可以从这份搜索加违例判定非弦。

开启negative_certificate=True后，另保存诱导圈[0,1,2,3]。验证连续位置和末首之间都是边，其余位置都不是边。这个圈本身就是与排序无关的否证，不要求审核者信任搜索并列规则。

再做两种迁移。第一，三点路径0—1—2上随意排序[1,0,2]失败，但图仍为弦图；正确搜索反序通过。第二，给四圈加弦02后，[1,3,0,2]成为合法消去序，着色与最大团都升为3。修补后的结论属于新图，不能覆盖原图的非弦记录。

六、输入排列、断开分量和成本分层 ​

将六点图边表倒序、每条边端点交换，或统一重命名六个顶点。搜索序和某份团树可以改变；将名字映回后，弦性、最优颜色数和全部极大团必须不变。并列重放与数学答案不变性要分别验收。

另外输入空图、一个孤立顶点、一条边加孤立点。空图返回空排列、零颜色、空团表和空边表；单顶点形成一个单点极大团；不同分量之间用零交边连接团树，不因此制造任何共享顶点。不要把“没有正交集边”当作构造失败。

阶段	本附件采用的资源口径
无序边表校验与邻接表建立	哈希期望O(n+m)，保留输入邻接次序
LexBFS与PEO验证	已准备邻接表上，确定O(n+m)单位成本RAM工作
最优着色及一个最大团	给定PEO后O(n+m)
全部极大团与透明团树构造	布尔成员行去包含和稠密交图，O(n³)时间、O(n²)额外空间
全部搜索快照	另有最坏O(n²)时间与输出空间
可选诱导圈提取	枚举三元选择加BFS，保守O(n³(n+m))期望时间

recognize便捷接口在正例上还调用完整团树构造，因此不能把它整段标成线性。若只做弦性判定，应只调用lexbfs和verify_peo。计数器与下标按可容纳输入规模的机器字计算；Python大整数、哈希最坏行为和外部标签编码另计。

最终至少交出：一次独立精化手算、完整搜索及PEO检查、一份最优颜色/团双证书、全部极大团和正确团树、错误树的断开位置、一份诱导长圈以及上述结构迁移。反复打印同一个搜索序，不能替代这些不同的证明责任。