알고리즘 시험 준비 - [12/13 Files] - 2019-10-07

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 an MST 이다.

 

 

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

 

E1 edge E1 는 E1 이 subset 이다 

 

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

Prim Algorithm

 

 

crossing edge 의 최소를 찾기

 

 

V 는 Vertex 에서 S 가 뭘까? 그냥 Vertex Set을 뜻함

 

 

 

이거는 좀 찾아봐야겠다.

Kruskal 은 알겠다.

 

 

뭐 대충은 알겠다

 

 

 

다시 정리 

1. Crossing Edge 는 항상 MST 에 속한다.

• 증명 - 다른 crossing edge를 할 경우 결국 crossing edge 기존꺼가 더 작다고 해서 접근한다.

 

1. Prim은 Priority Queue 를 사용해서 min crossing edge를 찾는다.

2. Kruskal은 Cycle

https://progresivojs.tistory.com/7

 

 

 

https://progresivojs.tistory.com/3