MATH STORIES

수학백과사전에서 칼럼까지
수학사랑에서 알려드리는 수학과 관련한 이야기들

Home

수학사랑 이야기

생성수형도/minimal spanning tree

작성자 : 수학사랑|조회수 : 4115

연결된 그래프에서 변을 삭제하여 얻어진 수형도가 생성수형도이다. 생성수형도는 minimal spanning tree를 번역한 것으로 한자로는 生成樹型圖라고 쓴다.

minimal spanning tree → 生成樹型圖 → 생성수형도

minimal에는 '최소의'라는 뜻이 있고, spanning에는 '다리를 놓는, 양끝을 연결하는'이라는 뜻이 있다. 주어진 어떤 그래프의 임의의 두 꼭지점 a, b에 대해 a에서 b로 가는 경로가 존재하는 수형도가 되도록 변을 삭제해 가면, 원래의 그래프에서 최소의 변이 남기에 minimal spanning tree라고 한 것이다. minimal spanning tree를 번역하면서 일상어인 '生成'을 차용하여 '生成樹型圖'라고 한 것이다. 生成은 '사물이 생겨남'을 의미한다. 변을 삭제하여 얻은 수형도로부터 원래의 주어진 그래프가 생성되었다고 보기에 '생성수형도'라고 하는 것으로 보인다.


우편번호 검색 close