最稠密子图的剥离与流证书

删低度点，记住最好的一刻 ​

若当前非空集合S有e条边、s个点，删除当前度为d的点后，剩余密度变成(e−d)/(s−1)。当s>1时，密度增加恰好等价于d<e/s。因而删除低度点是合理尝试，却不能只等到最后才看答案：最终单点没有边，密度必为0。

沿真实最小度剥离理路k-core分解与退化序k-core decomposition · Core decomposition · Coreness · Degeneracy ordering · Smallest-last ordering · 核分解与退化序用真剩余度的双链桶剥离求全部核数，证明退化度与有界后邻居序等价，并交可独立复查的上下证书。记录每份非空剩余图，选边数/顶点数最大的那份。只保存最佳前缀位置，结束后取排列的相应后缀，不每次复制整份剩余集合。删v时，剩余边数减去v的当前度，每条边恰好扣一次。

e=m；s=n；best尚未设置
每次删除之前：
    以交叉乘法比较e/s和当前最佳密度
    若更好，记住当前删除下标
    删除当前真实最小度点v
    e -= degree[v]；s -= 1
结束后返回最佳下标开始的排列后缀

每条边只给一个端点，产生全体上界 ​

把一条边交给删除较早的端点。每个点收到的边数恰是删除时真实度数，所以最多δ条，δ是这次剥离的最大删除度数。

任取非空S，每条内部边都交给S中的一个端点，故|E(S)|≤δ|S|，即ρ*≤δ。再看出现删除度数δ的那一步：当前所有点的度数都至少δ，握手恒等式给这份剩余图的密度至少δ/2。算法记住的最好密度只会更高，于是

该证明利用整条真实最小度轨迹，不把“删除看起来最差的点”误当成保留精确最优解的交换论证。[1，§3，Lemmas3–4] 并列最小度任意选择都成立。没有边时δ=ρ*=0，保证不必用除法表达。

最高核、最好剥离前缀与最优密度互不相同 ​

主图A={0,1,2,3}构成K₄，B的两侧为{4,5}及{6,…,13}，构成K₂,₈；另有叶边0–14和孤点15。共16点23边。

剥离先删15，再删14，此时剩余14点22边，密度11/7。继续删B中度为2的点，早期密度依次为20/13、18/12、16/11，都比11/7低。附件核全16份非空状态，最佳值确为11/7。最后留下的最高核A只有密度6/4=3/2。

但整个B有16条边、10个顶点，密度8/5，比11/7更高。它没有作为剥离后缀单独出现，因为它的度2顶点比A的度3顶点先被删。快速算法的实际保留比例是

这是该输入上的数值，普遍保证仍只有至少1/2。

无需相信枚举器，也能手算B最优。把每条边的一单位重量分给两个端点：K₄内部每边各分1/2；B的每边向左端分1/5、右端分4/5；叶边全分给14。于是A各点收到3/2，B左点收到8/5、右点也收到8/5，14收到1，15收到0。任何S的内部边重量全落在S中，所以|E(S)|≤(8/5)|S|。这给所有子图的上界8/5，而B达到它。

任意删点、钳位核键与固定k都需区别 ​

若不删当前最小度，出现最大删除度那一步的平均度未必至少该度数，2-近似证明便断掉。只知道某个排列的最大后邻居数小，也不能直接保证所有删除前缀达到了相应平均度下界。

线性核分解中，有些实现不再递减已经降到当前核层的键。这样的键适合求核数，但可能不等于当前真实度，不能用它扣剩余边数。四团真实删除度3、2、1、0若全当作核键3来扣，会把六条边错误扣成十二条。

若另要求恰好选k点，则不能使用本页任意非空S的流阈值。尤其密度阈值(k−1)/2此时问的就是是否存在k团：简单k点图最多有k(k−1)/2条边，达到才是完全图。这个额外基数约束不是在本算法返回后随便裁剪几个顶点就能满足的。

将严格密度改善翻译成一个割 ​

给λ=p/q≥0，p、q为整数、q>0。建立n+2个顶点的容量网络，源为s、汇为t：

• s→v容量q·deg_G(v)
• v→t容量2p
• 每条原无向边uv产生u→v、v→u两条原弧，各容量q

所有容量都非负；反平行的两条原弧各有自己的残量反向记录，不可混为一条。原弧总数2n+2m。对源侧{s}∪S，割容量为

第二步用总度2m，并把S的度数拆成两倍内部边数加跨边数。空集合S对应源割，容量B₀=2qm。因此

严格小于才是改善。若最小割等于B₀，由最大流最小割定理理路最大流最小割定理Max-flow min-cut theorem以净跨割恒等式和残量可达集证明最大流等于最小割，并给出独立可检查的最优性证书。，存在值为B₀的可行流；割恒等式遂说明全部非空S都有ρ(S)≤λ。λ恰等于最优值时，空集合总是一个最小割，某个非空最优集合也可给同值割。算法依据数值判定，不要求求解器在并列最小割中一定选非空者。

Goldberg的原网络使用容量m和m+2λ−deg(v)，给出基线mn及相同的密度差项。[2，§2] 上面采用度数源容量的变体，基线改为2m，再整体乘q；割恒等式已经独立证明，不能把两种网络的基线混用。

精确二分不靠浮点“差不多” ​

设m>0，所以n≥2。初始lo=0，hi=(n−1)/2，并保存见证W=V。简单图的边数上界保证ρ*≤hi，而ρ(W)>0。每轮以λ=(lo+hi)/2查询：

• 若最小割<B₀，令lo=λ，保存其非空源侧W
• 若最小割=B₀，令hi=λ，保留以前的见证

由两种查询的含义，始终保持

每个可能密度是a/b，a为整数、1≤b≤n。两个不同密度之差至少为1/n²，因为非零整数ad−bc的绝对值至少1。因此当hi−lo<1/n²时，ρ(W)与ρ*位于一个比最小间隔还窄的区间中，只能相等。这个停止条件同时给出集合，不能只把lo这个通常非可达密度的小数当成答案。[2，§3]

初始区间宽O(n)，每轮减半，故O(log(n+1))轮足够。最后用输出的ρ(W)再建一次网络，求出值B₀的流，作为独立的上界证书。二分在这里是单调阈值搜索理路二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。，严格/非严格判定方向和已保存见证共同决定了可提取的输出。

无边非空图直接取一个单点ρ=0；其所有容量为0，零流就是上界证书。空图单独返回无合法解，不进入有理密度比较。

主图的三个阈值可以逐项核算 ​

主图m=23。在λ=3/2时，q=2，源割基线92。取B那十个二部顶点，内部边16条，割值

所以它的密度严格高于3/2。在λ=31/20时，相同集合给920−640+620=900<920。在λ=8/5时，最小割和最大流都为230，已无严格改善。附件残量可达源侧此时只剩s；这不影响此前保存的B恰为最优解。

11次二分后，附件区间为

保留集合B的密度8/5位于其中；再加一次终态证书流，共12次流调用。实际停止由精确分数差决定，不是写死11轮。

证书复查与真实费用 ​

检查器从原图和候选S重新算ρ(S)，据此重新构造网络。随后逐原弧检查流量位于容量区间、逐内部顶点检查守恒，并要求源净流出为B₀。只要这份流可行，弱对偶就保证任何割容量至少B₀，进而所有子图密度≤ρ(S)。附件还核源侧合法及割与流等值，完整过程O(1+n+m)次精确算术。

快速剥离用桶求真最小度，并以交叉乘法比较e/s，整体O(1+n+m)时间和空间。保存最佳下标仅常数额外状态，最后才输出顶点集合。核数数组本身不能替代当前边数日志。

令一次网络最大流的时间为T_flow(N,A)，则精确算法总时间为

附件使用增广路方法理路Ford–Fulkerson 方法Ford–Fulkerson method沿残量网络中的增广路反复增加流量直至不存在增广路。中的BFS最短残量路规则，即Edmonds–Karp，其组合界O(N+NA²)给出一个明确多项式实现。可以换用其他正确最大流工具，不改变密度归约。每次求流从零开始，不假装自动复用前一阈值的残量状态。

二分阈值的分母是至多O(n³)的2幂倍数，分子、缩放容量和总流量也都至多n的固定次幂，故位长O(log(n+1))。这支持通常机器字RAM计数；大整数实现仍按实际加、乘、比较成本计。若换成任意实数边权，整数密度间隔证明立即失效，需要另定编码和停止合同。

核心工作区为O(1+n+m)。附件可选保存每轮源侧顶点清单，增加O(n log(n+1))条历史记录；关闭record_history可省掉它们。最终流证书占O(n+m)，不是把每轮全部网络都永久保存。小图的全子集枚举仅作独立对照，指数成本不计入以上算法界。完整输入、删除前缀及流记录见综合练习。