图的规范化

在图论（数学的一个分支）中，图的规范化是指寻找给定图G的规范形式的问题。规范形式是指与G同构的标记图Canon(G)，这样每个与G同构的图都具有与G相同的规范形式。因此，从图的规范化问题的解决方案中，我们也可以解决图的同构问题：为了测试两个图G和H是否同构，计算它们的规范形式Canon(G)和Canon(H)，并测试这两个规范形式是否相同。图的典范形式是一个完整的图不变量的例子：每两个同构图都有相同的典范形式，每两个非同构图都有不同的典范形式。反过来说，图的每个完整不变式都可以用来构造一个典型形式。一个有n个顶点的图的顶点集可以用1到n的整数来识别，用这样的识别方法，一个图的典型形式也可以被描述为其顶点的排列。图的典范形式也被称为典范标记，图的典范化有时也被称为图的典范化。

显然，图的规范化问题在计算上至少和图的同构问题一样难。事实上，图的同构性甚至对图的规范化是AC0可还原的。然而，这两个问题是否是多项式时间等价的，仍然是一个开放的问题。虽然图同构的（确定性）多项式算法的存在仍然是计算复杂性理论中的一个开放性问题，1977年LászlóBabai报告说，以至少1-exp(-O(n))的概率，一个简单的顶点分类算法只需经过两个细化步骤就能产生一个从所有n顶点图的集合中均匀随机选择的图的规范化标签。小的修改和增加的深度优先搜索步骤在线性预期时间内产生了这种均匀选择的随机图的规范标签。这一结果揭示了为什么许多报道的图同构算法在实践中表现良好的事实。这是概率复杂性理论的一个重要突破，它以手稿的形式广为人知，而且在一个研讨会上报告后很久，它仍然被作为未发表的手稿引用。一个常见的典型形式是同构类内的lexicographically最小图，它是具有lexicographically最小邻接矩阵的类的图，被视为一个线性字符串。然而，lexicographically最小图的计算是NP-hard。对于树，Read（1972）提出了一个简洁的多项式规范化算法，需要O（n）的空间。

首先，用字符串01标记每个顶点。迭代地对每个非叶x从x的标签中去掉前面的0和后面的1；然后将x的标签和所有相邻叶的标签按词法顺序排序。将这些排序后的标签连接起来，再加上前导0和后导1，使其成为x的新标签，并删除相邻的叶子。如果还剩下两个顶点，就把它们的标签按词法顺序连接起来。图的规范化的应用图的规范化是许多图的同构算法的本质。xxx的工具之一是Nauty。图规范化的一个常见应用是在图形数据挖掘中，特别是在化学数据库应用中。一些化学物质的标识符，如SMILES和InChI在其计算中使用规范化步骤，这基本上是代表分子的图的规范化。这些标识符旨在提供一种标准的（有时是人类可读的）方式来编码分子信息，并方便在数据库和网络上搜索这些信息。