k-core分解与退化序

删除安全性解释为什么可以反复剥离 ​

先固定k。若当前剩余图里v的度数小于k，那么任何仍包含在当前图中的k-core都不能包含v，因为继续缩小顶点集只会使它邻居更少。因此删掉v不会删错；重复直到没有这种顶点时，剩余集合本身满足最小度至少k，又包含每个可能的k-core，故恰是Cₖ。

这也证明删除次序无关：每次可以删任意一个当前低度顶点，最后仍得到同一个Cₖ。不同的是删除日志，不是k-core本身。只筛原度数会漏掉连锁反应，例如三点路径的原中心度数为2，但两个端点剥掉后，它不能留在2-core中。

一个删除序同时回答所有k ​

不为每个k重新运行。始终删除当前真实度数最小的顶点vₜ，记其度为dₜ，并维护前缀最大值

真实度数dₜ可能下降；核数Dₜ不会下降。为何前缀最大值是正确的？对固定k，在第一次出现dₜ≥k之前，所有被删顶点都不足k，依前段安全性不属于Cₖ。如果第一次出现，则当前最小度已经至少k，剩余图就是Cₖ。以后即使某点删到只剩一个邻居，它原来仍在这个k-core里，所以核数不能跟着降回1。若整轮没有dₜ≥k，则Cₖ为空。

于是Cₖ恰是核数至少k的顶点集，所有核数一次得到。退化度δ也等于maxₜdₜ：出现最大值的那份剩余图给出下界；任意非空诱导子图S中，取π里最早的顶点，它在S中的所有邻居此时都还没删，度数至多δ，给出上界。

核数不是一份残余度快照 ​

对四点完全图，删除度数依次为3、2、1、0，但四个点核数都为3。若直接写c(vₜ)=dₜ，会把后三点误标为2、1、0。某些线性核分解实现改用钳位键，仅在邻点键大于当前键时递减；它存的是不同不变量。[1，§§3–4] 本页保留真度数再取前缀最大值，使同一轨迹还可交给需要实际最小度的密度算法。

四种层次在同一张图中出现 ​

取四团A={0,1,2,3}，另取完全二部图B，左侧{4,5}、右侧{6,…,13}；再加叶边0–14和孤点15。全图16点、23边。先删15不损失边；再删14，0的度数从4降为3。二部部分右点当前度为2，比四团的度3小，因而先被剥离。

附件给出下面的真实轨迹，表内边数均在本次删除之前：

所以C₁={0,…,14}，C₂={0,…,13}，C₃=A，C₄为空。C₂不连通：四团和二部部分都能各自提供至少两个邻居，没有理由强行把它们合成一个连通块。

更晚邻居有界，不代表它们成团 ​

退化序只限制|N⁺(v)|≤δ。完美消去序理路弦图与完美消去序Chordal graph · Triangulated graph · Perfect elimination ordering · PEO证明无诱导长圈与完美消去序等价，线性验证候选序，并以着色和同规模团同时证明最优。还要求N⁺(v)两两相邻，强得多。四圈退化度为2，也有退化序，却没有完美消去序。不能用核分解替代弦图识别。

完全二部图K₃,₃的全部顶点核数为3，却没有任何三角形：三个顶点必有两个在同一侧，它们之间无边。相反，四团也有核数3，含四个三角形。核数描述持续的邻居支撑，不直接统计小团。

一次增加边可能让许多核数改变。长度至少3的路径中每点核数都是1；把两个端点连起来后形成环，每点核数都变成2。本页是静态全量算法，没有声称动态修改只需更新两个端点。

真度数的桶如何保持线性 ​

所有度数在0,…,n−1。建立head[d]指向度为d的顶点链表理路链表Linked list通过节点引用保存序列的存储结构；明确前驱、尾指针、节点身份与局部插删的复杂度条件。，每点保存prev、next；已知顶点位置后，可在常数时间从旧桶摘除并插入新桶。这里用两个方向的位置数组实现双链，不在线性表里搜索顶点。

初始化 degree[v]、各度数桶、alive[v]
D = 0；p = 0
重复n次：
    把p向上移动，直到head[p]非空
    从该桶取v；记录d=degree[v]
    D = max(D,d)；core[v]=D；把v标成已删除
    对每个仍存活的邻点u：
        从degree[u]桶摘除u
        degree[u]减1，插入新桶
        p = min(p,degree[u])

每条无向边恰在较早端点删除时使较晚端点度数减1，迁移总数为m；扫描邻接记录总数2m。寻找非空桶也没有隐藏的n²：删当前最小度d后，每个邻点至多减1，其新度至少d−1，因此每轮p最多向下退1，全部下退至多n。p始终在0,…,n−1，累计上移至多初末差加累计下退，也是O(n)。图准备、桶初始化、全部日志合计O(1+n+m)时间、O(1+n+m)空间。

附件从边表准备邻接表时，逐顶点用一份长度n的时间戳数组检查重复邻居，同样线性。它没有要求哈希平均常数访问，也没有偷偷按顶点对排序。固定字长标号和O(log(n+1))位计数按RAM口径计费。

不相信桶实现，也能检查核数 ​

一份证书只含π和整数标签c(v)。检查排列无重复、c沿π不降，并对每点核两项：

1. v至少有c(v)个邻点u满足c(u)≥c(v)
2. v至多有c(v)个在π中更晚的邻点

第一项证明每个集合{v:c(v)≥k}的最小度至少k，因此标签不会超过真实核数。反过来，假设某个标签≤k的点仍属于一个最小度至少k+1的子图。在这个子图取π中最早点v；标签不降使c(v)≤k，而其所有子图邻居都比它晚。第二项说它最多有k个这样的邻居，矛盾。故标签也不会低估，证书充分。

检查用位置数组及两次邻居计数，O(1+n+m)，不用重跑桶队列。只交“各Cₖ最小度够大”仅证下界，会接受遗漏合法顶点的过小核心；删除方向的上界同样需要。

同一排列可交给不同任务 ​

按π反向作贪心着色理路图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。，每点已有颜色的邻居至多δ个，因此δ+1色足够。这只是可行上界，K₃,₃实际只需两色。使用颜色时间戳，寻找最小空颜色至多检查当前邻色数加1，整体仍可线性。

三角形列举理路退化序三角形列举Degeneracy triangle listing · Triangle enumeration by degeneracy orientation · 稀疏图三角形枚举以退化序给简单图定向，用时间戳交集逐个列出原顶点三角形，证明无重复、O(n+mδ)成本及任意朝向的二次反例。沿π给边定向，让每点出度≤δ；最稠密子图算法理路最稠密子图的剥离与流证书Densest subgraph · Maximum density subgraph · Charikar peeling algorithm · 最密子图固定边数除以顶点数的密度，以真最小度剥离给2近似，再用严格流阈值和有理间隔求精确最优及可核验上界。则读取每个删除前缀的剩余边数和顶点数。两者依赖的是不同记录，不能把核数直接当每轮真实度数。完整三份输出见综合练习。