https://tcatmon.com/w/index.php?action=history&feed=atom&title=%EC%83%9D%EC%84%B1%EB%82%98%EB%AC%B4 2026-06-29T02:16:52Z 이 문서의 편집 역사 MediaWiki 1.28.0 https://tcatmon.com/w/index.php?title=%EC%83%9D%EC%84%B1%EB%82%98%EB%AC%B4&diff=535051&oldid=prev 2017-02-06T15:34:31Z

<p></p> <p><b>새 문서</b></p><div> * --상위 문서: [[나무]]--<br /> [include(틀:토막글)][[분류:토막글/수학]]<br /> [목차]<br /> == 개요 ==<br /> Spanning Tree<br /> <br /> --나무 반달인 줄 알았다면 오산이다.--<br /> <br /> 그래프에서 모든 꼭지점(노드)를 포함하는 [[트리]] 이다. 한 그래프는 여러 생성 나무를 가질 수 있지만 반드시 모두 연결되어 있어야 한다. 연결 되어 있지 않다면 생성 숲(Spanning Forest)이 되어 버린다. <br /> <br /> 네트워크, 통신망, 관계 시설등을 계산하는데 매우 유용한 개념이다. 최소 비용으로 통신망을 잇는 문제를 푸는데 쓰이거나 한다. 이중에서 특히 최소값을 가지는 최소 비용 생성 나무는 영어로 Minimum Spanning Tree라고 말하며. [[크러스컬 알고리즘]]이나 [[프림 알고리즘]]으로 찾을수 있다.<br /> <br /> 사실 [[다익스트라 알고리즘]]도 뜯어보면 내부적으로 생성나무를 일단 만들어서 쓴다.</div>

Maintenance script