Tree isomorphism 트리 동형사상

서론

그래프에서의 동형사상을 찾는 문제는 NP이다. 다만, 트리에서의 동형사상은 다항시간에 판정할 수 있다.

이번 포스팅에서는 두 rooted 트리에서의 동형사상을 찾는 알고리즘인 AHU Algorithm [Aho, Hopcroft and Ullman]과 unrooted tree의 동형사상을 찾는 방법을 다룰 것이다.

 

1. 동형인지 여부를 판정할 트리가 rooted tree 일 때 - AHU algorithm

  AHU algorithm에서는 트리를 몇 개의 튜플로 해싱하여 두 트리가 같은지 비교한다. 이때, depth 별로 tuple을 하나씩 형성해주어야 한다. 이 tuple을 이루는 항은 AHU algorithm에서는 각 depth별 vertex의 degree들이다. 또, tuple은 항상 정렬된 상태로 만들어 주어야한다. 또, tuple을 이루는 항이 꼭 degree일 필요는 없다. 각 vertex의 자식들을 포함하는 subtree의 vertices의 수를 이용해도 상관 없으며, 자식 수를 이용해도 된다. *물론, 자식 수를 이용하는 것은 degree를 이용하는 것과 동치이다.

 

  tuple을 형성했다면, 비교하는 것은 쉽다. Depth 별로 tuple이 같은지만 확인하면 된다.

2. 일반적인 트리

일반적인 트리에서 rooted tree에서의 방법을 그대로 이용하기 위해 두 트리가 동형이라면 같은 정점일 하나의 정점을 root로 잡아 줌으로서 rooted tree로 만들어줄 수 있다. 

 

2.1 Centroid

Tree에서 centroid란, 제거되었을 때 생기는 포레스트(forest)의 subtree를 이루는 정점의 수가 기존의 절반 이하가 되도록 하는 정점을 말한다. 또한, tree에서 centroid는 항상 존재한다.

 

Lemma 2.1.1    Centroid가 유일하지 않을 때 centroids는 인접한다.

proof) 먼저, centroids 가 서로 인접하지 않을 때를 생각해보자. 서로 다른 centroids 를 잇는 경로사이에 centroid가 아닌 정점이 하나 있다고 생각해 보자. 하나의 centroid로 분할 했을 때 아무런 모순이 생기지 않는다면, 다른 centroid로 분할했을 때는 모순이 생기지 않았던 centroid가 포함되는 subtree의 정점의 수가 원래 트리의 정점의 수의 절반을 넘게 되므로 모순이다.

 

Lemma 2.1.2    Centroid는 하나의 트리에 최대 2개 존재한다.

proof) Centroid가 3개 이상이라고 가정하자. 모든 centroid는 서로 인접해야 한다. 그렇다면, centroid끼리 이루는 트리의 subgraph는 완전그래프라고 생각할 수 있다. 이때, \(K_3\)부터는 사이클이 생기므로 트리가 아니다. 따라서, 트리에서는 centroid가 최대 2개 까지 존재할 수 있다.

 

2.2 Casework

Case 1) Centroid가 유일하다.

Centroid를 해당 트리의 root로 잡아줌으로서 rooted tree로 만들어 준다.

 

Case 2) Centroid가 유일하지 않다.

centroid는 두 개 존재한다면, 인접한 두 centroid 사이에 다른 정점을 하나 추가하고 원래의 두 centroid와 이어준다. 새로 추가한 이 정점은 새로 생긴 트리의 유일한 centroid가 되며, 동형사상을 찾을 두 그래프가 동형이라면, 각 그래프에서 이 과정을 실행해도 동형이다.

*물론 새로운 vertex를 추가하는 것이 합리적이지 못할 수 있다. 그럴때는 두 개의 centroid에 대해 각각 root로 잡아서 1.의 방법으로 tree를 hashing하면 된다.

 

root를 잡았다면, 1. 의 방법을 이용하여 동형을 판정할 수 있다.

 

3. 시간복잡도 분석

3.1. 1.의 시간복잡도

1.에서, 먼저 root에 대해 depth를 구해주어야 한다. 이 과정은 DFS나 BFS를 통해 진행되며, 이 과정은 \(\Theta(|V|+|E|)\)만에 완료할 수 있다. depth에 따라 튜플을 형성할 때, 모든 정점에 대해 해당 정점의 depth에 따른 튜플에 push back 해주면 되므로 \(\Theta(|V|)\)만큼의 연산이 필요하며, 정렬된 상태로 만들기 위해서 depth마다 정렬을 해야한다. depth가 \(D\)인 정점의 집합을 \(V_d\)라 했을 때, 각 depth 마다 \(\Theta(|V_d| \log(|V_d|))\)의 연산이 필요하다. 이는 트리의 총 높이에 따라 시간복잡도의 상한과 하한이 달라질 수 있음을 의미한다.

 

3.1.1 하한

1. 에서는 depth에 따라 정렬해주는 과정이 필요하므로, \(|V_d|\)가 작을수록 연산의 횟수가 적게 필요하다. 그러므로 최적의 경우는 트리에 곁가지가 없는 경우이다. 즉, 트리의 총 높이가 \(|V|\)와 같은 경우를 의미한다. 이때는 각 depth에 대하여 정점이 하나씩만 존재한다. 따라서 1.의 점근적인 시간복잡도는 \(\Omega(|V|)\)이다.

 

3.1.2 상한

3.1.1 에서 설명한 내용을 바탕으로 생각하면, \(|V_d|\)가 클수록 연산의 횟수가 많아진다는 것을 생각할 수 있다. 그렇다면 최악의 경우 트리는 루트와 다른 모든 정점이 인접하는 형태가 될 것이다. 이때 트리의 높이는 2이다. 1.의 점근적 시간복잡도는 \(O(|V| \log(|V|)\)이다.

 

3.2. 2.의 시간복잡도

Centroid를 찾는 과정은 트리에서의 Dynamic Programming을 통해 \(\Theta(|V|)\)에 수행할 수 있다. 이때, centroid가 유일하지 않을 때 새로운 centroid를 지정해주는 것은 \(O(1)\)만에 가능하다.

 

3.3. 전체 시간복잡도

일반적인 트리를 rooted tree로 만들어주는 과정이 \(Theta(|V|)\)만에 수행되며, rooted tree에서 동형 판정이 \(\Omega(|V|)\), \(O(|V| \log(|V|)\)에 수행된다. 따라서 전체 점근적인 시간복잡도는 두 과정의 시간복잡도를 더한것과 같으며, \(\Omega(|V|)\), \(O(|V| \log(|V|)\)이다.

 

4. 다른 트리 해싱 방법

  이 챕터에서는 Knuth tuple에 대해 설명한다. Knuth tuple을 트리를 하나의 string으로 hashing하는 방법이다. 아래 그림을 보면 괄호 안에 0이 들어가 있는 것을 확인할 수 있다. 이때, 여는 괄호를 1, 닫는 괄호를 0으로 만들어줄 수 있으며, 괄호 안의 0은 무시해도 좋다. 그러면 tree를 bit string으로 hashing 할 수 있다.

Knuth Tuple.;  Huynh Thai Hoc

마치며

이번 글에는 수식이나 그림 없이 글로 풀어서 설명해 두었다. 이해가 힘들거나, 수식으로 엄밀하게 정의된 것을 확인하고 싶다면, 아래의 슬라이드들을 확인하라.

https://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf

 

이 포스팅에서 설명한 방법을 C++로 구현해두었다. 필요하다면 참고하라.

https://github.com/P4rkingZ0eN/Well_Known/blob/main/TreeIsomorphism.cpp