退化序三角形列举

让每个三角形只认一个最早点 ​

任意三角形在π中有唯一顺序u≺v≺w。它的三条辅助方向必为u→v、u→w、v→w，所以只需要在u处寻找这样的两步路u→v→w，并检查u→w。

将u的出邻居做标记之后，最后一项检查就是问“w现在有没有u的标记”。不用查询完整邻接矩阵，也不用把每份邻居交集排序。邻接表理路图的表示Graph representation · Adjacency-list and adjacency-matrix representations依据图的类型与所需操作选择邻接表、邻接矩阵或边集表示的方法。让程序只扫描存在的出边。

为每条无向边建立一个从早到晚的出边记录
mark全部初始化为-1
for u 按π顺序：
    for w in N⁺(u)：mark[w]=u
    for v in N⁺(u)：
        for w in N⁺(v)：
            if mark[w]==u：输出{u,v,w}

每个顶点u只处理一次，原标号u因此可作为时间戳。旧轮标记可以留着；测试必须是mark[w]==u，不能仅判断mark[w]不是空。这样既避免每轮清空n格数组，也不会把旧邻居误认成当前邻居。

为什么既不漏报，也不重报 ​

一次输出来自u→v、v→w和当前对w的标记；标记又来自u→w，所以三条原边都真实存在，且u≺v≺w使三点互异。

反过来，取任意三角形并按π写成u≺v≺w。处理u时w已被标记，扫描u→v时必扫描v→w，于是输出它。唯一性也在这里：别的起点不可能比三点中的最早点更早地走过同一组三点；固定最早点后，中间点必须是v，不能反过来从w走回v。简单图没有重复出边，故该循环组合只出现一次。

附件将三点原标号排序成三元组作为输出表示，排序三个元素是常数工作。它不按三元组对整份清单再排序；显示顺序由输入邻接次序和π决定。验证“无重复”应按原顶点集合比较，不能把辅助排列中的位置当成原ID。

四团中的四次输出 ​

在16点综合例中，退化序的四团尾段是0≺3≺2≺1，相关出邻居为

处理0时标记1、2、3。经0→2→1输出{0,1,2}；经0→3再到1和2，输出{0,1,3}、{0,2,3}。处理3时经3→2→1输出{1,2,3}。表中集合的显示顺序不是沿π重新编号。

整个图还有一个K₂,₈、一个叶子和一个孤点，都不贡献三角形。附件实际扫描27个两步候选，输出四个集合；mδ=23×3=69只是上界，不该写成实际循环数。

度数很大的星形仍可很便宜 ​

取9点星形，中心原ID为4，叶子为0,1,2,3,5,6,7,8。如果直接按原ID从小到大定向，四个低ID叶子都指向4，4又指向四个高ID叶子。算法将检查4×4=16条两步路，全部失败。推广为中心两边各h个叶子，候选数h²，而m=2h、δ=1。

用真正的退化序，叶子先删，直到最后一条边；每点至多一条出边。9点附件只检查7条两步路，仍输出空集。两种排列都能保证输出正确，但只有经过证明的出度界支持O(mδ)费用，不能把“某个排列”当成退化序。

三种看起来相似的任务 ​

• K₃,₃的核数全为3，三角形仍为0。核层次给枚举成本参数，不替代具体边检查
• 只求三角形数量可以边输出边累加，但要求完整原顶点清单时，z份输出费用不能省略
• 若允许平行边，同一顶点三元集合可能对应多种边身份组合。当前接口拒绝重边，不把边重数乘积算作多个三角形

最坏情形最优连接理路最坏情形最优连接Worst-case optimal joins · WCOJ从AGM熵界到一般NPRR锚关系递归，完整核算三角形和四三元表实例的枚举与索引成本。把三角形写成三张关系的连接，按表大小做重轻分解。这里三条关系来自同一无向图，利用它的退化度，并按原顶点集合输出一次。一般三表的元组身份和属性域不自动形成这种图，不能无条件套用退化序。

每次扫描由一条边支付 ​

标记工作为∑ᵤ|N⁺(u)|=m。最内层扫描次数精确为

这是按外层出边u→v记账，不是假设一个出邻居表只扫描一次：N⁺(v)可能被多个前驱扫描，但每次至多δ项，前驱边总数只有m。每份输出来自一次成功扫描，所以z≤W，输出费用已包含在O(n+mδ)中；若改为更长结构的显式输出，需重新计输出长度。

准备位置数组、定向边表和mark只需O(1+n+m)。有边时δ≥1，m被mδ吸收；无边时仍保留读n个顶点及初始化的费用。本算法不需要常数时间哈希成员查询；标号和位置可直接索引数组。

从δ得到通常的稀疏图界 ​

若δ>0，某个非空诱导子图最小度至少δ。它至少有δ+1个顶点，握手恒等式给

故δ≤√(2m)，一般情况下时间也为O(1+n+m^{3/2})。当δ有固定上界时则为线性，即使原图最大度非常大。星形正好展示“最大度大”与“没有高最小度子图”可以同时成立。

原Chiba–Nishizeki算法以森林覆盖数arboricity分析稀疏图小子图列举。[1，§§2–3] 本页选退化序作为可直接交付和验证的结构参数，并在上面独立完成它的费用证明；无需先求最少森林划分，也不声称这是所有图上最优的三角形算法。

综合练习同时要求核证书、原ID清单与实际扫描数，再更换顶点标签。重标号可以改变并列删除和输出次序，却不能改变经逆映射还原的三角形集合。