mcfx's blog

题解、Writeup、游记和碎碎念

挑战图同构(大雾)

这篇文章原发布在 https://mcfxmcfx.blog.uoj.ac/blog/7279

前几天在 EI 群看到 EtaoinWu 在 UOJ 搞了一道编码题 #679. 无标号图编码,感觉很有意思,于是就来做了做。

根据 OEIS,不同的图个数约为 2n(n1)/2n!\frac{2^{n(n-1)/2}}{n!},而这个结果也非常的精确。写一下代码可以发现,在 n=70n=70 时,这个估计和实际值的差距已经不超过实际值的 101610^{-16}

n=100n=100 时,2n(n1)/2n!1.17624425\frac{2^{n(n-1)/2}}{n!}\approx 1.176\cdot 2^{4425}。根据信息熵,能编码的 01 串长度最多只能是 4425,而此时分数为 170。

引入

首先考虑把点定一个顺序。一种简单的方法是,把 0K10\sim K-1 连成独立集,然后 i+Ki+K 往前面 jj 连边当且仅当 gig_i 的第 jj 位是 1,其中 gi[0,2K)g_i\in[0,2^K)。 令 fi=j[gj=i]f_i=\sum_j [g_j=i],我们需要保证 fi0,1f_i\in {0,1},并且改变 0K10\sim K-1 的顺序会使得 ff 不同(这样才能还原出 0K10\sim K-1 的顺序)。假设 ff 是在程序中预先写死的。 解码时可以先找到独立集,然后根据后面点的连边情况还原整个序列。假设 K=7K=7,7 个点形成独立集的概率非常低,而 ff 也满足的概率就更低了。

这个做法一共使用了 762+793=672bits\frac{7\cdot 6}2+7\cdot 93=672\text{bits} 来区分顺序,剩下还有 93922=4278bits\frac{93\cdot 92}2=4278\text{bits} 可以存储实际序列。

算法一

77 实际上也太大了。77 元独立集本身就占用了许多边,而很多数只需要 6bits 确定,不需要 7bits。我们可以让 K=5K=5,然后令 fi=j[gj=i]f_i=\sum_j [g_j=i],并且移除 fi0,1f_i\in {0,1} 的限制。可以让 ff 中存在一个 fi=1f_i=1,一个 fi=2f_i=2,并且所有 fi8f_i\le 8fi=1f_i=1 的点标号可以唯一确定。设他为 xx,我们可以用是否向 xx 连边区分出 fi=2f_i=2 的点。接下来所有点都可以用和这三个点的连边情况来区分了。胡乱实现一个可以得到 93 分

算法二

这种排序方法仍然浪费了大量 bit。他的本质是,用 nn 个 bit,可以把大小为 nn 的集合分为两个集合。当 nn 较大时,这种方法的浪费不大(如 2log10+20log202.5bits2\log 10+20-\log 20\approx 2.5\text{bits}),但是 nn 小的时候会造成非常大的浪费(如 n=2n=2 需要 2bits,然而实际信息量只有 1bit)。

假设我们按照前面的方法确定了几个点的标号(把这几个点叫做 BB,最前面 KK 个叫做 AA),接下来问题的就是,如何更快地把剩下的集合排序。对于 fif_i 对应的集合,可以强制要求里面每个点到 BB 的连边情况都不同,那么它花掉了 Bfibits|B|\cdot|f_i|\text{bits},但是可以贡献 log(2Bfi)bits\log\binom{2^{|B|}}{f_i}\text{bits}。经过计算可以发现,当 BB 较大时,净损失几乎就是 logfi!\log f_i!,也就是几乎没有额外开销。实现上,可以在标程里抄一个 BinomTable

在此基础上,还有一些优化。把每个集合贡献的 log(2Bfi)bits\log\binom{2^{|B|}}{f_i}\text{bits} 乘起来,作为一个高精度整数考虑,可以多赚回来一些 bit。把 KK 换成 4,可以节省一些 bit。

这些优化全部应用上可以得到 138 分

算法三

刚才的优化始终没有绕开必须有 fi=1f_i=1fi=2f_i=2 作为 BB 的种子这个条件。为了绕开,我们可以要求 BB 的内部是一个不对称图(asymmetric graph),这样就可以直接在内部确定编号。

假设 B=8|B|=88 个点的不对称图有 3696 个。这样净开销就只有 872log(36968!)=0.85bits\frac{8\cdot 7}2-\log\left(3696\cdot 8!\right)=0.85\text{bits},非常节省。应用这个可以得到 143 分

算法四

前面的过程一直假设 ff 是固定的,而这也损失了大量的信息。如果把 ff 变成动态的,ff 本身也可以编码大量信息。我当时的实现可以得到 158 分。(但是这代码有个 bug,一直到 170 分的提交才发现并修复,所以应该还可以再得更高一点的分)

算法五

在算法四的基础上,经过调参可以发现,如果放宽了 ff 的范围,那么一个图可能会有多种解码方式。假设在这些方式中选择 hash 值最小的。

经过多次调参,发现可以让算法四将 100 个点的图和长为 4427 的 01 序列建立联系,并且约有 30% 的序列编码再解码可以得到自身(实际上上界是 1.176/4=0.2941.176/4=0.294,也就是说几乎每个图都可以编码了)。

于是我们可以考虑这个新问题:有一个 F:[0,24427)0,1F:[0,2^{4427})\to{0,1},约 30% 的 F(x)F(x) 是 1,并且是随机分布的,需要找一个 G:[0,24425)[0,24427)G:[0,2^{4425})\to [0,2^{4427}),以及 G1G^{-1},使得 F(G(x))=1F(G(x))=1

假设我们建了一棵 4425bits 的 trie 树,每个叶节点有 040\sim 4yy 满足 F(y)F(y) 为 1,有一个需要求 GG 的值 xx。每个节点内部先尽量把 xxyy 匹配,然后匹配不完的再往父亲丢。

这个 trie 树当然不用实际建出,可以从叶子开始往上一层一层搜索,直到找到匹配位置。

显然最后所有的 xx 都能找到匹配,只是时间复杂度可能会爆,感性理解一下可以发现大概有 exp(i)\exp(-i) 的概率在 exp(i)\exp(i) 的时间内跑出来。

最后我的实现在题目要求的时限内错误率略高于 2%,多次提交可以得到理论上界 170 分

(这份代码实现上有一些小区别,但是大致思想如此)

碎碎念

看到这题时,我首先想到了之前看到的一道题,大概是把一个长为 100 的串编码到 100 个点的图中,但是他还限制了边数也不超过 100。那题可以用一条链来做,这给了我把点编号的启发。

这题到达了理论上界并不意味着图同构被解决了。假设有两个图 A,BA,B,其中 AA 是随机图,BB 要么和 AA 同构,要么是另一个随机图。那么将度数序列排序后比较可以有几乎为 1 的正确率。这题其实就类似这种情况。

这题的对偶版本——将图编码成 01 串,看起来也已经解决了(并且几乎达到了下界)。但是有个大问题:对于 01 串编码的情况,即使串本身不是随机的,也可以随机异或一些东西,把他变随机;但是给你一个精心构造的图,并不能把他变得随机。不过,这其实也并不是问题,因为要是 corner case 都能做,那就直接可以判定图同构了。

日期: 2021-08-26

标签: 算法 图同构