了解 Nauty 算法
Understanding Nauty algorithm
我正在尝试了解 Nauty 算法。
关注本文：http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf
在这个算法中，顶点是根据它们的度和一个组与其他组对应的相对度（group action）来区分的。通过这种方式，我们得到的组为：
1379|2468|5
完成此步骤后，将按照本文第 7 页中所述进行拆分。
本文中的一张图片是：
我无法理解拆分是如何完成的
1379|2468|5 到 1|9|37|68|24|5
为什么 1 和 9 去了不同的组，而 37 去了另一个组。
简而言之，您正在 个体化 个顶点，然后 'shattering' 生成分区的像元，直到分区变得公平。
如第 5 节所述：
Having reached an
equitable partition, we need to introduce artificial distinctions between vertices
这在定义 9 中有所描述。因此我们从单元格 {1379} 中选择了 {1}，然后优化生成的分区直到它是公平的（参见定义 6 和下面的示例）。
因此，单元格 1 - {1} - 将单元格 3 - {2468} - 打碎成两个单元格 {68|24}，因为 1 在 {68} 中有 0 个邻居，在 {24} 中有一个。同样，{379} 被 {24} 拆分为 {9|37}。
我正在尝试了解 Nauty 算法。
关注本文：http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf
在这个算法中，顶点是根据它们的度和一个组与其他组对应的相对度（group action）来区分的。通过这种方式，我们得到的组为：
1379|2468|5
完成此步骤后，将按照本文第 7 页中所述进行拆分。
本文中的一张图片是：
我无法理解拆分是如何完成的
1379|2468|5 到 1|9|37|68|24|5
为什么 1 和 9 去了不同的组，而 37 去了另一个组。
简而言之，您正在 个体化 个顶点，然后 'shattering' 生成分区的像元，直到分区变得公平。
如第 5 节所述：
Having reached an equitable partition, we need to introduce artificial distinctions between vertices
这在定义 9 中有所描述。因此我们从单元格 {1379} 中选择了 {1}，然后优化生成的分区直到它是公平的（参见定义 6 和下面的示例）。
因此，单元格 1 - {1} - 将单元格 3 - {2468} - 打碎成两个单元格 {68|24}，因为 1 在 {68} 中有 0 个邻居，在 {24} 中有一个。同样，{379} 被 {24} 拆分为 {9|37}。