Nauty 알고리즘 이해

Question

Nauty 알고리즘을 이해하려고합니다.
이 알고리즘에서 정점은 그 정도와 다른 그룹에 해당하는 그룹의 상대적 차수 (그룹 동작)를 기준으로 구분됩니다. 이러한 방법으로 우리는 그룹으로 얻을 :이 문서에서 언급 한 바와 같이이 단계 후

1379|2468|5
, 분할이 완료 - 페이지 7. 한 이미지를이 문서에서 것은 :

내가 드릴 수 없습니다 1 및 9이 다른 그룹에 가서 37 다른 그룹에 가서 왜 분할이 1|9|37|68|24|5 에 1379|2468|5에서 수행되는 방법을 이해합니다.

Answer 1

간략히 말하면, 은 정점을 개별화 한 다음 파티션이 공평하게 될 때까지 결과 파티션의 셀을 '산산조'시킵니다. 이 섹션 5에서 말하듯

는 :

가 공정한 파티션에 도달하는 데, 우리는이 정의 그래서 우리가 선택한 9에서 설명

정점 사이에 인공 구분을 도입 할 필요가 { 1}을 셀 {1379}에서 제거한 다음 결과 파티션을 공평하게 될 때까지 정제합니다 (정의 6 및 그 아래 예제 참조).

따라서 셀 {1}은 {68}에 0 개의 이웃과 {24}에 1 개의 이웃을 갖는 1 개의 셀 {68 | 24}로 셀 3 - {2468}을 파괴합니다. 유사하게, {379}는 {24}에 의해 {9 | 37}로 분할됩니다.