[이산수학] (10) Tree & Spanning Tree

G에 cycle이 없는 경우 G를 acyclic이라 부른다.

사이클은 처음과 마지막 vertices가 같되 중간 vertices는 중복되지 않는 walk를 뜻한다.

만약 acyclic하고 connected인 그래프라면 G는 Tree다.

 

아래와 같은 경우 connected가 아니거나, acyclic이 아닌 경우이기 때문에 Tree가 아니다.

 

G가 connected graph일 때, 모든 G가 cut edge인 경우 G는 tree다. 

*cut edge : G-e 일 때 connected comp가 G일때보다 많아지면 e는 cut edge

 

pf) prop) e는 cut edge이다. iff e가 cycle에 포함되지 않는다면

=> : 만약 G가 tree라면, G는 acyclic이기 때문에 G에는 cycle이 없다. 

따라서 G의 모든 edge e에 대하여 e는 cycle에 속하지 않기 때문에 e는 cut edge다.

<= : G가 tree가 아니라고 가정해보자. G가 connected로 가정되었기 떄문에 G는 acyclic이 아니다. 

이 경우 모든 G의 edge가 cut edge인데 G에는 cycle이 있어 특정 edge는 cut edge가 아니게 되니 모순이 발생한다. 따라서 모든 edge가 cut edge인 경우 G는 Tree다.

 

어떠한 edge를 잡아서 G-e를 해도 # of connected comp of G-e는 G보다 많다. 

따라서 모든 edge가 cut edge이니 G는 Tree다.

 

Thm) G가 Tree라면 |E(G)| = |V(G)| - 1 이다.

pf) |V(G)|=1일때, |E(G)|=0이라 사실이다.

|V(G)| <= k까지 사실이라고 가정해보고, |V(G)|=k+1인 G가 있다고 가정해보자. G-e는 이 때 two connected comp가 되고 각각은 G1, G2다. G1은 connected고 acyclic, G2도 그러니까 둘다 Tree다. 

 

따라서 각각을 더한 것이 결국 |E(G)| = |V(G)| -1 이 되니까 G가 Tree라면 어떠한 vertices 갯수를 가졌든 상관없이 hold true다. 

 

그러나 Tree이면 이게 Hold True이지, 이 조건을 충족한다고 Tree는 아니다. 

 

모든 tree의 leaf는 degree 1의 vertex다.

 

Thm) 모든 Tree는 적어도 2개의 leaf를 가진 적어도 2개의 vertices를 가진다.

Remarks)

(i) vertex 1개의 graph는 leaf가 없다

(ii) vertices 5개가 일렬로 나열된 graph는 명백히 Tree다. 양끝에 leaf가 있기 때문이다.

 

pf) G가 최소 두개의 vertices를 가졌고 connected이기 때문에, d(u) >= 1 for u in V(G)이다.

sigma sum of d(u) = sigma sum of d(u)_d(u)=1 + sigma sum of d(u)_d(u)>=2 를 고려해보자.

 

Case1) 만약 G가 최대 1개의 leaf를 가졌다면, 

sigma sum of d(u) = 1+ 2(|V(G)|-1) = 2|V(G)|-1 = 2|E(G)| = 2(|V(G)|-1) 이기 때문에 모순이다.

Case2) 만약 leaf가 없다면,

sigma sum of d(u) >= 0 + 2|V(G)| = 2|E(G)| = 2(|v(G)|-1) 이기 때문에 모순이다. 

 

따라서 G는 적어도 2개 이상의 leaf를 가진, 2개 이상의 vertices로 구성되어야만 Tree이다. 

 

Spanning Tree는 Spanning subgraph와 마찬가지로, 

Edge는 부분집합, Vertices는 그대로인 Tree를 뜻한다.

 

Spanning Tree는 degree sequence로 구분할 수 있다.

 

Spannign Tree는 1) Spannign Subgraph & 2) Tree 여야한다.

 

Spanning Tree는 maximal connected spanning subgraph in G without cycle로 정의된다.

 

Thm) 모든 connected graph G는 spanning tree를 가진다. 

pf) connected graph G가 있을 떄, S={H | H is spanning subgraph of G and H is connected}라면 S는 공집합이 아니다. 

 

H는 connected이고, H에서 e를 골라 H-e를 취하면 G의 spannig subgraph다.

H-e가 not connected다. e는 H의 cut edge이고, H는 Tree이고, H는 G의 spanning tree가 된다. 

 

Cor) 만약 G가 connected라면 |E(G)| >= |V(G)| - 1 이다. 

pf) G가 connected이기 때문에 Spanning Tree H를 가진다. 

|E(G)| >= |E(H)| = |V(H)| - 1 이며, |E(G)|  = |E(H)| 라면 G=H이며 G는 Tree다. 

 

Cor) |E(G)| < |V(G)| -1 가 사실이라면, G는 connected가 아니다. 충분한 edge가 없기 떄문.