[WEEK04] 트리 동형 사상

트리 동형 사상

트리 동형 사상Tree Isomorphism이란 두 트리 T1​, T2가 노드의 값은 무시하고, 트리의 구조만 보고 동일한 구조를 가지고 있는지를 판단하는 문제이다.

즉, 노드 간 연결 방식(형태)만 같다면 동형이다!

 

예를 들어 아래 두 트리는 서로 동형이다.

Tree 1           Tree 2
   A                X
  / \              / \
 B   C            Y   Z

노드의 이름(A, B, C vs X, Y, Z)은 다르지만 구조가 같기 때문에 동형이다.

💡 핵심 아이디어

트리 동형사상을 판단하는 대표적인 방법 중 하나는 canonical form을 만드는 것이다. 서브트리를 정규화된 문자열로 변환한 후, 이 문자열이 동일한지 비교하면 된다.

1. 각 노드를 루트로 하는 서브트리를 문자열로 표현
2. 자식 서브트리 문자열들을 정렬
3. 이 정렬된 자식 문자열을 괄호로 감싸서 반환
4. 최종 루트의 문자열이 같다면 두 트리는 동형이다

Canonical form에 대한 설명은 여기를 참고하자.

💻 코드 구현

다음은 트리 동형사상을 판별하는 파이썬 코드이다. 트리는 인접 리스트(딕셔너리)로 표현했다.

defaultdict에 대한 설명은 여기를 참고하자.

from collections import defaultdict

def canonical_form(tree, node, parent):
    # 서브트리를 문자열로 정규화
    labels = []
    for child in tree[node]:
        if child != parent:
            labels.append(canonical_form(tree, child, node))
    labels.sort()
    return '(' + ''.join(labels) + ')'

def are_isomorphic(tree1, root1, tree2, root2):
    # 두 트리가 동형인지 판단
    return canonical_form(tree1, root1, None) == canonical_form(tree2, root2, None)

# 예제 트리
# Tree 1: 0-1, 0-2
tree1 = defaultdict(list)
tree1[0] = [1, 2]
tree1[1] = [0]
tree1[2] = [0]

# Tree 2: 5-6, 5-7
tree2 = defaultdict(list)
tree2[5] = [6, 7]
tree2[6] = [5]
tree2[7] = [5]

print("동형 여부:", are_isomorphic(tree1, 0, tree2, 5))  # True

---

Rooted Tree Isomorphism

루트가 정해져 있을 때, 루트를 기준으로 각 서브트리의 구조를 문자열로 정규화하면 된다.

알고리즘 요약

1. 리프 노드는 () 반환
2. 자식 서브트리들을 정규화된 문자열로 재귀 처리
3. 자식 문자열들을 정렬 후 '(' + 합친 문자열 + ')'로 감싼다
4. 루트의 결과가 같으면 두 트리는 동형

Unrooted Tree Isomorphism

루트가 고정되어 있지 않다면, 트리 전체에서 "루트 후보"를 찾고 모든 가능한 루트에서 비교해야 한다.

일반적으로 트리의 중심(center)을 루트로 사용하면 효율적으로 해결 가능!

트리 중심(Center) 구하기

1. 리프 노드를 반복적으로 제거
2. 노드가 1개 또는 2개 남을 때까지 반복
3. 남은 노드들이 트리의 중심 (1개 or 2개)

방법

• 두 트리의 중심(1~2개)을 모두 구한 후,
• 각 중심을 루트로 설정해 Rooted Tree Isomorphism 비교

from collections import defaultdict, deque

# Rooted Tree Isomorphism
def canonical_form(tree, node, parent):
    children_forms = []
    for child in tree[node]:
        if child != parent:
            children_forms.append(canonical_form(tree, child, node))
    children_forms.sort()
    return '(' + ''.join(children_forms) + ')'

def are_rooted_isomorphic(tree1, root1, tree2, root2):
    return canonical_form(tree1, root1, None) == canonical_form(tree2, root2, None)

# 트리 중심 구하기 (Unrooted Tree)
def find_tree_centers(tree):
    n = len(tree)
    degree = {node: len(neighbors) for node, neighbors in tree.items()}
    leaves = deque([node for node in tree if degree[node] <= 1])

    removed = 0
    while removed < n - 2:
        new_leaves = deque()
        for _ in range(len(leaves)):
            leaf = leaves.popleft()
            removed += 1
            for neighbor in tree[leaf]:
                degree[neighbor] -= 1
                if degree[neighbor] == 1:
                    new_leaves.append(neighbor)
        leaves = new_leaves
    return list(leaves)

def are_unrooted_isomorphic(tree1, tree2):
    centers1 = find_tree_centers(tree1)
    centers2 = find_tree_centers(tree2)

    for c1 in centers1:
        for c2 in centers2:
            if are_rooted_isomorphic(tree1, c1, tree2, c2):
                return True
    return False

# 예제 트리
tree1 = defaultdict(list)
tree1[0] = [1, 2]
tree1[1] = [0, 3]
tree1[2] = [0]
tree1[3] = [1]

tree2 = defaultdict(list)
tree2[10] = [11, 12]
tree2[11] = [10]
tree2[12] = [10, 13]
tree2[13] = [12]

print("Rooted Isomorphism:", are_rooted_isomorphic(tree1, 0, tree2, 10))  # False
print("Unrooted Isomorphism:", are_unrooted_isomorphic(tree1, tree2))     # True

---

참고자료

• Tree Isomorphism(트리 동형)

Tree Isomorphism(트리 동형)

• [Python] 트리 동형 (Tree Isomorphism)

[Python] 트리 동형 (Tree Isomorphism)

• Tree isomorphism 트리 동형사상

Tree isomorphism 트리 동형사상