本练习是稀疏图结构与密度路线的终点。你将为同一个原图交三份可复查输出：每点核数和删除排列、无重复的原顶点三角形、一个最稠密非空集合及最大流上界。核数最大、含三角形最多和边数/顶点数最高，可能落在不同的部分。

输入与可执行附件 ​

原顶点是0,…,15。A={0,1,2,3}构成四团；B为两侧{4,5}和{6,…,13}之间的完全二部图；另加边0–14，保留孤点15。总计16点、23边。边是无序顶点对；重复记录即使调换端点也要拒绝。

• 标准库执行器
• 实际完整输出

下载后运行：

python algorithms-sparse-graph-certificates-check.py > result.json
python -O algorithms-sparse-graph-certificates-check.py > optimized.json

程序只向标准输出写JSON；所有核验采用显式检查，关闭Python断言优化不会跳过它们。图准备、桶剥离、枚举、流求解和证书检查都在同一文件，另有明确标注的指数时间小图对照器。后者用于检验这份输入，不参与所声明的多项式或线性界。

第一份：删除日志不是核数数组 ​

按真最小度剥离理路k-core分解与退化序k-core decomposition · Core decomposition · Coreness · Degeneracy ordering · Smallest-last ordering · 核分解与退化序用真剩余度的双链桶剥离求全部核数，证明退化度与有界后邻居序等价，并交可独立复查的上下证书。执行，桶首的确定规则产生排列

15,14,6,7,8,9,10,11,5,13,4,12,0,3,2,1

先手算前三步。删15时度0、仍有23条边；删14时度1，把边数减到22；此后6的度2，删除后剩20边。桶指针可以向下退，所以后面的真实度数不必递增。

完整核数按原ID排序为

3,3,3,3,2,2,2,2,2,2,2,2,2,2,1,0

解释顶点12尤其重要。轮到它时度数已经降到0，但此前删除度的最大值是2，它仍属于原图的2-core。四团尾段的真实删除度是3、2、1、0，四点核数却全为3。

不重跑桶，直接查证书的两面：每点至少有c(v)个核标签不小于自己的邻居；按输出排列，每点至多有c(v)个更晚邻居。再核标签沿排列不降。前一面防止夸大核，后一面防止漏掉可保留的点。把四团标签全改成0，只检查“标签集合最小度够大”会漏掉错误，删除上界则立即拒绝。

提交日志时，还应记录每步删除前的顶点数、边数和当前度。真实度总和是23，每条边只在较早端删除时扣一次；不能用核数求和代替。附件实际桶上移5格、下移5格、邻点度更新23次。

第二份：原身份的四个三角形 ​

用上述排列给边从早到晚定向，执行时间戳三角形列举理路退化序三角形列举Degeneracy triangle listing · Triangle enumeration by degeneracy orientation · 稀疏图三角形枚举以退化序给简单图定向，用时间戳交集逐个列出原顶点三角形，证明无重复、O(n+mδ)成本及任意朝向的二次反例。。四团尾段为0≺3≺2≺1，因此0的出邻居是{1,2,3}，3的是{1,2}，2的是{1}。

原顶点集合清单必须恰为

{0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}

处理0时用原ID 0作标记；扫描0→2→1，以及0→3→1、0→3→2，产生前三个集合。处理3时再得到最后一个。标记只检验是否等于当前起点，旧轮标记无需逐格清空。

全图扫描27条两步候选；23×3=69是保证上界，不是实际计数。完整结果仍用原顶点名，即使排列位置不同也不能把0≺3≺2≺1改写成顶点0、1、2、3之后忘记逆映射。

额外检验9点星形：中心ID为4。原ID顺序产生16条失败两步路，而退化序产生7条；两个结果都没有三角形，时间保证不同。换成K₃,₃时，全部核数为3而输出仍为空。这两项分别检验“正确排列”与“有界出度”、核层次与团结构的区别。

第三份：近似集合与精确上界 ​

密度理路最稠密子图的剥离与流证书Densest subgraph · Maximum density subgraph · Charikar peeling algorithm · 最密子图固定边数除以顶点数的密度，以真最小度剥离给2近似，再用严格流阈值和有理间隔求精确最优及可核验上界。固定为内部边数除以顶点数。主图三种集合的结果如下：

最佳剥离值与精确值的比是55/56。单个输入接近最优，不会加强所有图至少保留1/2的证明。B未在剥离轨迹中单独留下，因为它的度2顶点早于四团的度3顶点被删。

先用割算式核三个阈值 ​

对λ=p/q，建立s→v容量q·deg(v)、v→t容量2p，以及每条无向边的两个容量q原弧。空集合的源割基线为B₀=2qm。源侧集合S对应割值

在λ=3/2时，B给割值92−64+60=88，低于基线92，证明还有严格改善；在31/20时，割值900低于920。到8/5时，最小割值是230，恰等于基线。残量源可达集合这时只含s，因此返回的原图侧为空；保留先前找到的B，才有非空最优输出。

11轮精确二分后，区间是1635/1024至6555/4096，宽15/4096<1/16²。候选密度的分母至多16，两个不同候选相距至少1/16²，所以保存的8/5已经必须最优。最后再求一次阈值8/5的流，共12次调用。

不看搜索历史，直接验230单位的流 ​

附件在最终网络使用s=16、t=17，所有s→v弧恰好饱和。顶点0收到20单位；1、2、3各收到15；4、5各收到40；6,…,13各收到10；14收到5；15收到0，总计230。

除去s、t，下面列出全部非零内部流。其余原弧流为0，每条内部弧容量均为5。

于是0向t送16；1、2、3各以15+1送16；4、5各以40−24送16；每个右侧点以10+6送16；14以5+1送6。每条v→t容量是16，守恒和容量都成立。该可行流的值230与空侧割同值，证明所有非空子图密度至多8/5；B恰好达到它。

复查器从候选顶点集合重新计算密度和网络，不能直接相信JSON里宣称的阈值、容量或最优标记。改动一条流量，可能破坏容量、守恒或总值中的任何一项，均应被拒绝。

迁移：加一条桥，三个输出如何响应 ​

现在仅加入边0–4，让A与B连通。先预测，再运行附件的bridge结果。新边没有共同邻点，所以三角形清单仍为原四个；所有核数也保持不变。但A∪B的边数增加到23，密度23/14，严格超过B的8/5。

附件的精确输出现在是{0,…,13}，值23/14；剥离也在删15、14后达到它。这次最高核仍为A，却不再能从“不同连通块各自最优”推导答案，因为多了一条跨块边。检查最终流上界，才能确认23/14确实是全局最优，而非只比以前更好的候选。

再任取顶点双射重标号，并逆序输入边。桶并列处理和输出次序可以改变；将三角形和核标签逆映射后应完全相同，精确密度也不变。快速剥离的具体并列轨迹允许改变，统一保证仍是至少1/2。

最后交三个边界：空图返回NO_NONEMPTY_SET；非空无边图选单点、值0且零流为证；自环或重复无向边在入口拒绝。用这些情况区分“没有合法集合”“合法但目标为零”和“不符合图合同”。

提交与成本清单 ​

交付原边表、原ID排列、每点核数、真实删除度日志、无重复三角形、实际候选计数、近似/精确集合、最终流证书，以及桥边和重标号后的复核记录。不能只交三行最终数值。

核分解及核证书检查为O(1+n+m)。三角形工作为O(1+n+mδ)，保存z个结果另占O(z)。精确密度调用O(log(n+1))次最大流；本执行器用BFS增广路，每次有独立网络和残量记录，绝不把流求解计作常数。关闭record_history可不保存各轮源侧清单，但最终证书仍须保留。所有分数、容量和比较都是精确整数运算。