什么是规范标签？

处理图同构问题的标准方法是将每个图映射到一个特定的字符串表示形式，称为其代码或规范标签。规范标签具有这样的属性：如果两个图是同构的，那么它们的代码应该相等。

此属性使我们能够通过分析图的规范标签来测试图同构性。构建图规范标签的第一步是为该图发现一个邻接矩阵描述。它显示了给定图的此类矩阵的一个实例。

一个图可以有多个邻接矩阵描述，因为有多种方法可以对邻接矩阵中的顶点进行排序。第一行和第一列与具有 3 条边的顶点 a 相关，第二行和第二列与具有 2 条边的另一个顶点 a 相关，依此类推。要推导出图的所有邻接矩阵描述，需要处理矩阵的所有可能的行排列。

示例 − 考虑以下矩阵

M = 1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16

可以使用以下置换矩阵将第一行（和列）与 M 的第三行进行转换 −

P13 =  0 0 1 0
      0 1 0 0
      1 0 0 0
      0 0 0 1

其中 P13 通过交换单位矩阵的第一行和第三行获得。它可以交换第一行和第三行（和列），置换矩阵与 M 相乘 −

M′ = P13T X M X P13= 11 10 9 12
                    7  6 5  8
                    3  2 1  4
                   15 14 13 16

第二步是为每个邻接矩阵确定字符串描述。因为邻接矩阵是对称的，所以根据矩阵的上三角部分生成字符串描述是有效的。

代码是通过以列方式连接上三角矩阵的条目获得的。最后一步是关联图的所有字符串描述，并选择具有最低（或最高）字典顺序值的那个。

之前的方法看起来代价高昂，因为它需要我们确定图的所有可能的邻接矩阵，并评估它们的每个字符串描述以发现规范标签。此外，对于每个包含 k 个顶点的图，都应该处理 kl 个排列。

已经开发出各种方法来降低此任务的复杂性，包括缓存先前计算的规范标签，并通过合并更多数据（包括顶点标签和顶点的度数）来减少确定规范标签所需的排列数。

更新于：2022年2月11日

396 次查看

启动您的职业生涯

完成课程获得认证

开始
广告