对于一个项目，我正在编写一个与 networkx 一起使用的 python 程序来创建一个 NAUTY 风格的同构检查程序。我的程序基于对 Nauty 的介绍，可在此处找到，其工作原理如下：
取两张图 G 和 H，并根据节点的度数为节点着色。运行颜色细化算法，该算法根据颜色类中每个节点的邻居来细化图的着色。这对 (G', H') 成为我的搜索树的“根”，我将在其上使用 DFS 算法。接下来，我个性化 G' 中的一个节点，该节点属于具有多个元素的最小颜色类，并使用分支方法生成新的树对 (G'', H''), (G'' , H'''), ... (G'', H^(k)) (k 取决于颜色类的大小，例如如果在 g 中为颜色类 red: [1,2,3]是 G 中的红色节点，[5,6,7] 是 H 中的红色节点，那么我必须为 1:5、1:6、1:7 对的搜索树创建一个分支，然后打开稍后在我的搜索树中访问的新分支）。还有问题！我的树变得太大、太快——这是因为我没有使用上述链接的“节点不变量和修剪”部分中描述的节点不变量。
有人可以解释一些我可以使用的节点不变量的例子吗？在 StackExchange 上，我发现这里没有多大帮助。我假设并使用我的节点颜色是节点不变量的事实，但对于强规则图，这并不总是给我带来太多。有任何想法吗？