알고리즘 | 트리에 대해서 (feat. 트리와 그래프의 차이)

컴퓨터 공학, CS는 기술면접에서 코딩테스트를 하는 게 아니고 공부를 얼마나 정확하게, 성실하게 했느냐를 많이 물어보는 것 같다. (*학부생 기준) 

이건 취업과 대학원 입시 면접 둘 다 해당하는 이야기라서 따로 기록을 해 보았다. 

---

 

Tree의 정의 

“A tree is an undirected graph that is connected and acyclic.”

• G가 n개의 노드를 포함하는 undirected 그래프일 때, 아래의 문장을 만족
  1. G is connected
  2. G doesn’t contain a cycle
  3. G has n-1 edges.

트리는 그래프의 부분 집합으로, 1) conntected, 2) acyclic, 3) undirected, 4) n node and n-1 edges 를 가지는 그래프입니다.

 

트리의 성질

→ 무향그래프가 트리일 때, 무작위 한 쌍의 노드 간에는 unique path 하나만 존재한다.
*두 노드사이에 경로가 하나라도 더 생성되면 cycle이 생기게 된다. 그러면 트리 조건 위배임.

→ 임의 연결된 undirected graph가 |E| = |V|-1을 만족하면 트리이다.
*Graph가 acyclic임을 보여주면 된다. 혹은 사이클에서 간선 제거하는 방법으로도 쉽게 증명가능

트리와 그래프의 차이가 뭐야! 라고 물어봤을 때, 우리는 자료구조 때 배우는 directed rooted tree를 말하기 십상이다. 그렇게 대답하면 오답임(부분정답). KAIST 면접 때 나왔음

 

Rooted tree

하나의 노드가 루트로 지정된 트리를 나타낸다. 루트의 엣지들은 루트를 가르키거나 루트에서 멀어지는 방향으로 향하는 ‘자연스러운' 방향을 할당할 수 있는데, 이 경우에는 directed rooted tree가 된다.

directed rooted tree는 자료구조에서 배우는 컴퓨터 과학의 핵심 데이터구조이다. 그래서 트리를 이거로 생각하게 되는데, 정확히는 틀리다.

directed rooted tree에서 root, parent, child의 관계가 존재한다

(cf. 루트가 없으면 free tree임)