신장트리

![Pasted image 20240302170524.png](/img/user/첨부파일/Pasted image 20240302170524.png)
![Pasted image 20240324233009.png](/img/user/첨부파일/Pasted image 20240324233009.png)그래프 내의 모든 정점을 포함하는 트리
하나의 그래프에 많은 신장 트리가 존재할 수 있다

Spanning Tree = 신장 트리 = 스패닝 트리
Spanning Tree는 그래프의 최소 연결 부분 그래프이다
최소 연결 = 간선의 수가 가장 적다

n개의 정점이 있다면 n-1개의 간선을 가진다

그래프의 최소 연결 부분 그래프로 사이클이 존재하지 않는다