赋权链图

赋权链图(Weighted Chain Graph，wcg),是FataliS1024创造的图论记号。

定义

满足以下性质的有限图为一个wcg：

• 所有边都是有向边，都有一个正整数的权值
• 不一定连通，但是每个连通部分都有且只有一个顶点使得这个顶点的入度为0，这个顶点称作根
• 所有顶点的入度不是0就是1，即边的方向总是从根向外放射的
• 无环，无重边

对两个wcg A和B，称A“镶嵌于”B，当且仅当可以B通过有限次以下的操作变成A：

• 删掉任意一个度为1的顶点及它连接的边
• 删掉任意一条边
• 删掉任意一个度为2的顶点，并且把它连接的两个边的权值分别记作m和n，删去这两条边，把这个顶点原来连接的两个顶点连接起来，新边权值为min(m,n)，方向由近根点指向远根点

满足如下性质的wcg组成的序列的最大长度定义为wcg(n)：

• 序列的第k个wcg最多有k+1个顶点
• 序列的每一个wcg的边的权值最大为n+1
• 若x < y，则第x个wcg不能镶嵌于第y个wcg

分析

wcg函数的强度被预期为和BMS极限相同，但缺乏分析。

改版

ω-wcg

将wcg中，“每条边都有一个正整数权值”改成“每条边都有一个小于ω^ω的非0序数权值”

wcg(n)定义中的“权值最多为n”改为“权值最多为ω^n”

镶嵌规则中，“对于一个权值大于1的边，令其权值-1”改为“对于一个权值大于1的边，把它的权值变成一个更小的非0序数”

即得到ω-wcg

ε₀-wcg

满足以下性质的有限图为一个ε₀-wcg：

• 无环无重边，所有边都有向，且都必须有一个小于ε₀的序数权值，权值至少为1
• 不一定连通，但是每个连通部分都有且只有一个顶点使得这个顶点的入度为0，这个顶点称作根，其余所有顶点均至少有1的入度

对两个ε₀-wcg A和B，Δ是B的基本列常数，称A“镶嵌于”B或A小于B，同时也称B“容纳”或B大于A，当且仅当可以B通过有限次以下的操作变成A：

• 删掉任意一个度为1的顶点及它连接的所有边
• 对任意一个权值大于1的边，若它的权值是后继序数，则令其权值-1；若它的权值为极限序数，则将权值改为这个极限序数基本列第x项，其中x是任意一个不超过Δ的自然数
• 找到任意一个入度为1，出度至少为1的顶点，把它的前驱记作V，把它入边的权值记作Y；对于它的所有出边，把出边的权值记作m，出边的终点记作W，则把这条出边删除，并且添加一条边从V指向W，权值为min(Y,m)
• 找到任意一个出度为1，入度至少为1的顶点，把它的后继记作V，把它出边的权值记作Y；对于它的所有入边，把入边的权值记作m，入边的起点记作W，则把这条入边删除，并且添加一条边从W指向V，权值为min(Y,m)

定义ε₀以下的极限序数的基本列：

• ω[n]=n
• 对于β是极限序数，(α+β)[n]=α+β[n]，(αβ)[n]=αβ[n]，(α^β)[n]=α^β[n]

满足如下性质的ε₀-wcg组成的序列的最大长度定义为ε₀-wcg(n), N→N：

• 序列的第k个ε₀-wcg最多有k+1个顶点
• 序列的每一个ε₀-wcg的边的权值最大为ω^^n，其中ω^^0=1
• 若x < y，则第x个ε₀-wcg不小于第y个ε₀-wcg
• 第k个ε₀-wcg的基本列常数Δ为n+k

ε₀-wcg的强度被预期为ε₀行BMS。