[CSE 565] - 2019-10-07.pdf

notes-2019-10-07

 

 

undirected graph 에서  V1 = V and E <= E 이게 무슨 뜻이지?

 

아 Spanning Tree 의 정의구나 한번 뭔지 찾아보자

 

Spanning Tree는 그래프의 최소 연결 부분 그래프 이다.

 

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

 

Edge 개수가 Vertex 개수보다 1개 작을 때 Spanning Tree 이다. 

 

weight 가 젤 최소화되는 spanning tree를 얻는 것이다. 

 

Cut 이게 옛날에 퀄 준비할때도 뭔말인지 몰랐는데.. 

https://www.crocus.co.kr/755

 

가중치를 

 

Cut은 그냥 나눠서 Edge를 나누는거 같다. 

 

나누어서 나누어진 Edge 가 cut-edge를 뜻하는거 같다.

 

cut-property는 뭐지 

 

 다시 돌아가서

 

http://1ambda.github.io/algorithm/algorithm-part2-1/

 

 

spanning tree 라는게 vertices를 포함하는 것이군

 

 

하나의 set 에서 다른 셋으로 이어주는 edge 가 min weight 는 MST에 속한다는 것이다

 

무슨 x 소리일까

 

 

이해 됬다 이건 

 

 

근데 PPT를 봐도 모르겠네

Cut - Property

 

 

여기서 E1 은 첫번째 Edge 인가. 

 

E1 subset 이구 + e * 도 crossing weight of min weight 와 합쳐도 MST다

 

 

 

 

이거랑 비슷한거 같다. 이걸 먼저 봐야겠다. 

이거랑 비슷한거 같다. 이걸 먼저 봐야겠다. 

 

 

w(T1) wegiht 를 보면 w(e^*) 이 w(e1) 보다 더 작다 그래서 

 

T1 is a MST 이다.

 

 

T1 는 MST 인데 e1 이 e * 보다 더 작기 때문에 MST 이다.

 

E1 edge E1 는 E1 이 subset 이다 

 

E1 subset 이랑 e* 는 min of crossing edge 이다. 이걸 먼저 기억하자