심심하다
질문좀해라
알고리즘 질문받는다
ㅁㄴㅇㄹ(122.47)
2016-12-11 21:23
추천 1
댓글 34
다른 게시글
-
아 이력서 사진안찍었는대 내일 9시이전에 여는 사진관없겠지..? [1]dw1e213(221.141) | 16.12.11추천 0
-
오늘자 생활땔감 [14]커헠(msca8h) | 16.12.11추천 0
-
님덜 근데 자바말고 CPP나C#으로갈려고하는뎅 [5]MlRs✨(ilikechic) | 16.12.11추천 0
-
프갤을 보고 있으면 우리나라의 IT업계가 심히 걱정된다.. [4]ㄹ(119.64) | 16.12.11추천 0
-
근대 it분야만큼 착한사람들만있는 분야없지않냐??? [3]dw131(221.141) | 16.12.11추천 2
-
알고리즘 질문받는다 [2]ㅁㄴㅇㄹ(122.47) | 16.12.11추천 0
-
c언어 문법 다떼가는데 이제 뭐함?? [9]ewfwef(119.194) | 16.12.11추천 0
-
도움! [6]uncloud(uncloud) | 16.12.11추천 0
-
모니터를 하나 공짜로 받았는데.. [4]오빠코딩(175.223) | 16.12.11추천 0
-
프로그래밍을 몬 공부씩이나 ㅋㅋㅋㅋ [3]ㅋㅋㅋ(61.102) | 16.12.11추천 0
크루스컬이랑 프림 결과가 왜 MST에요?
우선 크루스칼부터
입력은 connected graph
크루스칼의 결과물을 T라고하면, 사이클이 생기는 edge를 추가 안했으니까 T는 acyclic하다. 그리고 모든 vertex가 T에 포함되므로 T는 스패닝 트리다
왜 최소져
(만약 v가 T에 포함되지 않으면 1. v에서 시작하는 edge가 없거나, 2. v에서 시작하는 모든 edge가 추가 될 시 cycle을 만들어야 한다. connected이므로 1은 false, 최소 하나의 edge는 cycle을 만들지 않으므로 2도 false)
그럼 이제 minimum임을 증명하면된다
보통 이런건 수학적 귀납법쓰면 되는데
T_opt를 한 MST라고 하고, Cost(A)를 트리A의 비용(가중치 합)이라고 하면
case1. T = T_opt일때
당연히 MST
case2. T != T_opt 일 때
그러면 T_opt의 edge중에 T에 포함 안되는게 있을거고, 그 중에 가장 cost가 낮은걸 e라고 하자
귀납법이 아닌거같은데
e가 T에 없다는건 e를 T에 넣으면 사이클이 생긴다는거고
음 아무튼 계속 보고있어요 저 이거 알아둬야해서
그러게
쓰다보니까 귀납법이 아니네
귀납법으로 해야겠다
--------------------------------------
edge를 cost 낮은순으로 정렬해서 추가하는데
i번째 edge까지 했을때 만들어진 그래프를 A_i라고하면
모든 i에 대해서, A_i에 i+1번째부터의 edge들만을 추가해서 MST를 만들 수 있다는걸 증명한다
1. i = 0일 때, 모든 edge 들 중 일부를 사용하면 당연히 MST를 만들 수 있으므로 TRUE
2. i = k일 때 위 가정이 성립한다고 하면
만약 A_k에 k+1번째 edge를 추가해서 사이클이 생기는 경우면 A_(k+1)=A_k이고, k번째 edge는 못쓰는거니까 TRUE
사이클이 안 생기는 경우는
잠깐 생각좀
글을 새로 파는게 나을듯
열심히하셔서 1따봉 드립니다
아까 위에서 하던걸 어차피 해야되네
정리해서 글로 새로 올림
http://gall.dcinside.com/board/view/?id=programming&no=664674