그래프 - 신장트리(Spanning tree)??

네 안녕하심까~ 테슬라입니다.
자, 모두 개학 시즌이시죠? 새로운 마음으로 시작해볼까요?

오늘은 신장트리(Spanning tree)에 대해서 써볼까 합니다.

음 신장트리란 무엇인가?
임의의 그래프 G에 대한 부분그래프중에서 모든 정점과 연결된 부분 그래프를 말합니다.
부분그래프는 저번에 설명한 것과 같이 어떠한 그래프 G의 정점과 간선을 이용하여 만들수 있는 그래프를 말합니다.
집합에서 부분집합을 떠올리시면 되는것이지요.
단, 연결은 최소한으로 합니다. 괜시리 필요없이 간선을 사용 할 필요가 없다는 것이지요.

아무튼 이러한 부분그래프 중에서 이을 수 있는 모든 정점을 이으셔서 하나의 그래프를 만드시는 것이지요.
예를 들어볼까요?
 

자 요런 그래프가 있다고 하지요.

자 요런것들은 신장트리라고 할수 있을까요?
네, 당연히 가능합니다. 모든 정점들을 연결했으니까요.

그럼 아래것들은 어떨까요?

아쉽게도 둘 다 불가능 합니다.
왼쪽의 경우 최소의 간선을 이용하지 않았지요? ①, ③, ④ 부분에서 하나의 간선을 제거 할 수 있지요.
오른쪽의 경우는 ②, ④를 잇는 간선이 기본 그래프에 존재하지 않았기 때문에 존재하지 않는 간선을 사용할 수 없는것이지요.

음 그럼 잠시 생각해볼까요?
전에 포스팅했던 깊이우선과 너비우선 검색방식을 생각해봐요.
음 모두 최소의 간선을 이용해 모든 정점을 방문하려고했지요?
결국 각각을 깊이우선 신장트리, 너비우선 신장트리라고도 부르기도 하지요.
때문에 이 둘을 생각해보시면 신장트리가 좀 더 이해하기 쉬우실거에요.


에 오늘은 여기까지 입니다.
다음 포스팅은 아마도 최소신장트리가 되겠지요?
오타나 잘못된 부분은 지적해주심 감사하겠습니다~