xxx 图同构问题（Weisfeiler-Lehman算法）

题目描述
图同构问题是指判断两个给定的图是否在结构上完全相同，即是否存在一个顶点的一一映射，使得两个图的边关系完全一致。这是一个经典的未解问题（尚未确定属于P还是NP完全），但实践中常用启发式算法进行判断。Weisfeiler-Lehman（WL）算法是一种有效的图同构测试方法，尤其适用于某些类型的图。

解题过程

1. 问题理解

   • 输入：两个无向图 \(G_1 = (V_1, E_1)\) 和 \(G_2 = (V_2, E_2)\)。
   • 目标：判断 \(G_1\) 和 \(G_2\) 是否同构。
   • 难点：直接枚举所有顶点映射的复杂度为阶乘级，不可行。

2. WL算法核心思想

   • 通过迭代地给每个顶点分配一个"颜色"（标签），颜色反映顶点及其邻域的拓扑结构。
   • 每轮迭代中，根据当前颜色和邻居颜色集合更新顶点的颜色。
   • 如果两图在迭代过程中颜色分布不同，则它们不同构；若颜色分布稳定后一致，则可能同构（需进一步验证）。

3. 算法步骤
   步骤1：初始化颜色

   • 为每个顶点分配初始颜色（如顶点的度数）。
   • 示例：若顶点度数为2，则颜色标签为"2"。

   步骤2：迭代颜色细化

   • 对每个顶点，收集其所有邻居的当前颜色，排序后与自身颜色组合成新标签（如哈希字符串）。
   • 将新标签映射为一个新的颜色编码（例如，用哈希函数压缩为整数）。
   • 重复此过程，直到颜色分布不再变化（即连续两轮的颜色分配完全一致）。

   步骤3：比较颜色分布

   • 检查两图每轮迭代后的颜色分布（各颜色的顶点数量）。
   • 若某轮分布不同，算法终止并返回"不同构"。
   • 若分布稳定后一致，则返回"可能同构"（WL算法不能完全保证同构，但对多数图有效）。

4. 实例演示
   考虑两个图：

   • 图1：三角形（三个顶点两两相连）。
   • 图2：三个顶点的链（仅两条边）。
   • 初始颜色：图1所有顶点颜色为"2"（度数均为2），图2两端顶点颜色为"1"，中间顶点颜色为"2"。
   • 第一轮迭代后，图1顶点的新颜色均相同（邻居颜色集合均为{2,2}），而图2两端顶点颜色相同（邻居颜色集合为{2}），中间顶点颜色不同（邻居颜色集合为{1,1}）。
   • 颜色分布不同，算法判断两图不同构。

5. 算法局限性与优化

   • WL算法对某些图（如高度对称的强正则图）可能失效。
   • 可通过增加高阶WL算法（考虑邻居对或子图）提升判别能力，但计算成本更高。

总结
WL算法通过迭代颜色细化捕捉图的局部结构，是图同构问题的实用启发式方法，适用于预处理或快速排除不同构图的情况。