挑战图同构（大雾）

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

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

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

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

引入

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

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

算法一

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

算法二

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

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

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

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

算法三

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

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

算法四

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

算法五

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

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

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

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

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

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

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

（这份代码实现上有一些小区别，但是大致思想如此）

碎碎念

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

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

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

日期： 2021-08-26

标签： 算法 图同构