瞭解Nauty算法

Question

我想了解Nauty算法。 以下這篇文章：http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf
在這個算法中，根據頂點的度數和對應於其他組的相對程度來區分頂點（組動作）。通過這種方式，我們得到的羣體爲：

1379|2468|5
此步驟後，如本文提及的拆分完成 - 從這篇文章第7頁。 一個形象是：

我不能瞭解拆分是如何完成的從 1379|2468|5到1|9|37|68|24|5 爲什麼1和9去了不同的組，而37去了另一個組。

Answer 1

簡而言之，你是個性化頂點，然後'粉碎'結果分區的單元格，直到分區變得平等。

正如在第5節說：

已經達到 公平的分區，我們需要

這在定義9.所以我們選擇描述頂點之間引入人爲區分{ 1}，然後對結果分區進行細化直到它是公平的（參見定義6和下面的例子）。

由於1在{68}中有0個鄰居，而{24}中有1個鄰居，因此小區1- {1} - 將小區3 - {2468}分解爲兩個小區{68 | 24}。同樣，{379}由{24}分成{9 | 37}。