그래프 이론 편집하기 (부분)

== 트리와의 관계 ==
트리는 그래프의 한 종류이므로 '''그래프 이론'''의 일부로 간주된다. 하지만 그래프 이론에서는 일반적인 '''그래프(Graph)'''를 연구하는 반면, '''트리(Tree)'''는 그래프의 특별한 형태로서 별도의 연구 주제로 다뤄지기도 한다.

=== 트리가 그래프 이론에서 별도로 다뤄지는 이유 ===
트리는 그래프의 특수한 형태이지만, 그 자체로 중요한 성질을 가지기 때문에 그래프 이론과 별도로 연구되는 경우가 많다. 주요 차이점은 다음과 같다.

# '''순환이 없음'''
#* 트리는 '''사이클이 없는 연결 그래프'''이다.
#* 모든 정점이 연결되어 있으며, 정확히 V-1개의 간선을 가진다 (V는 정점의 개수).
# '''유형에 따른 차이'''
#* 일반적인 그래프는 방향성과 가중치를 가질 수도 있지만, 트리는 보통 무방향이고 가중치가 없다고 가정하는 경우가 많다.
#* 그러나 [[이진 트리|이진 트리(Binary Tree)]]나 [[이진 탐색 트리|이진 탐색 트리(BST)]] 같은 구조는 특정한 규칙을 따르며, 컴퓨터 과학에서 별도로 연구된다.
# '''트리의 응용'''
#* 트리는 그래프보다 특정 문제에서 더 효율적인 구조를 제공한다.
#* [[최소 신장 트리|최소 신장 트리(MST, Minimum Spanning Tree)]]는 그래프에서 트리를 찾는 문제로, 크루스칼과 프림 알고리즘을 사용하여 해결한다.
#* 데이터 구조로서의 트리(예: AVL 트리, B-트리)는 데이터베이스, 파일 시스템, 인덱싱 등의 응용에서 사용된다.

=== 그래프 이론에서 트리를 포함할 때와 제외할 때 ===

* '''포함할 때'''
** 트리를 '''연결 무향 비순환 그래프'''(Connected Acyclic Undirected Graph)로 정의하고, 그래프 이론 내에서 연구할 수 있다.
** 스패닝 트리(Spanning Tree), 최소 신장 트리(MST), 루트가 있는 트리(Rooted Tree) 등은 그래프 이론과 밀접한 관련이 있다.
* '''제외할 때'''
** 이진 트리, AVL 트리, B-트리처럼 <nowiki>'''</nowiki>데이터 구조로서의 트리<nowiki>'''</nowiki>를 연구하는 경우, 그래프 이론보다는 별도의 트리 이론(Tree Theory)으로 분리된다.
** 트리가 가지는 특정한 성질(예: 노드 삽입, 삭제, 회전 등)을 중심으로 연구할 때는 그래프보다는 데이터 구조에 가깝다.