그래프의 트리 (Tree (Graph Theory))

한 줄 정의: 사이클(순환하는 경로)이 없이 모든 정점이 연결되어 있는 그래프로, 정점이 n개이면 간선은 정확히 n-1개다.

쉽게 풀면

트리는 나뭇가지처럼 뻗어나가되 어디에서도 다시 원래 지점으로 돌아오는 순환 경로가 없는 그래프다. 가계도나 컴퓨터의 파일 폴더 구조를 떠올리면 이해하기 쉽다. 모든 정점이 서로 연결되어 있으면서도 불필요한 연결(사이클)이 전혀 없는, 가장 '효율적으로 연결된' 구조라고 볼 수 있다.

왜 중요한가

트리는 사이클이 없는 가장 단순한 연결 구조라는 특성 덕분에 자료구조, 알고리즘 설계, 네트워크 최적화, 계층적 분류 체계 등 컴퓨터공학과 응용수학 전반에서 기본 도구로 쓰입니다. 계산 복잡도가 낮으면서도 계층 관계나 최소 비용 연결과 같은 문제를 다루기 쉬운 구조이기 때문에, 더 복잡한 그래프 문제를 트리로 근사하거나 트리 성질을 활용해 증명하는 연구가 많습니다.

논문에서는 이렇게 쓰입니다

"최소 신장 트리 알고리즘을 이용해 네트워크 전체를 연결하는 최소 비용의 트리를 구성하였다."

네트워크 설계, 데이터 구조, 계층적 분류 등 다양한 문제에서 트리 구조가 핵심적으로 활용된다.

"결정 트리 모형은 각 분기 노드에서 특징 변수를 기준으로 데이터를 분할하며, 트리의 깊이가 깊어질수록 과적합 위험이 커지는 것으로 나타났다."

머신러닝 분야에서 데이터를 분류할 때 트리 구조를 사용하며, 그 구조적 특성이 모형의 성능에도 영향을 미친다는 점을 다룬 예문이다.

"계통수(phylogenetic tree)는 종 간의 진화적 유연관계를 트리 구조로 나타낸 것으로, 가지의 길이는 유전적 거리를 반영한다."

생물학에서도 트리 구조가 활용되며, 이 경우 그래프 이론의 트리 개념이 진화적 계통 관계를 표현하는 도구로 쓰인다.

조금 더 깊게 보면

트리는 그 자체로도 여러 하위 개념을 가지는데, 특정 정점을 뿌리로 지정한 트리를 '루트 트리(rooted tree)'라 하고, 그렇지 않은 트리를 '언루트 트리'라 구분합니다. 논문에서 신장 트리(spanning tree)를 다룰 때는 원래 그래프의 모든 정점을 포함하면서 사이클 없이 연결하는 부분 그래프를 의미하며, 그중 간선의 가중치 합이 최소인 것을 최소 신장 트리라 부릅니다. 이러한 트리를 구하는 대표적인 알고리즘으로 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 두 방법 모두 그리디(탐욕적) 접근을 기반으로 합니다.

주의할 점

트리는 반드시 사이클이 없어야 하며, 사이클이 하나라도 존재하면 더 이상 트리로 분류되지 않는다.