한 사이클 내에서 최대 가중치 간선을 제거하기 위한 최소 신장트리 알고리즘 (Minimum Spanning Tree Algorithm for Deletion of Maximum Weight Edge within a Cycle)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 14권 / 2호 / 35 ~ 42페이지
· 저자명 : 최명복, 한태용, 이상운

초록

본 논문은 최소신장트리를 쉽고 빠르게 구하는 방법을 제안하였다. 제안된 알고리즘은 먼저, 그래프의 가중치 간선의 수를 축소시키는 방법으로 그래프를 단순화 시켰다. 간선 수를 축소시키는 방법으로는 그래프 정점의 결합가가 3 이상인 경우, 최대 가중치 간선을 제거하는 방법을 적용하였다. 다음으로, 그래프를 단순화 시킨 축소된 모집단 간선들을 대상으로 사이클이 발생하는 부분을 확인하여 사이클 발생 간선들 중에서 최대 가중치를 갖는 간선을 삭제하는 방법을 적용하였다. 다양한 9개 그래프에 대해 제안된 사이클 최대 가중치 간선 제거 알고리즘을 적용한 결과 그래프의 사이클 개수만큼만 수행하여 MST를 쉽게 구하는 장점을 보였다. 모집단 축소 기법을 적용한 결과, 9개 그래프의 사이클 개수를 66%로 감소시키는 결과를 얻었으며, 최소 2개에서 최대 8개의 사이클에서의 최대 가중치 간선만 삭제하면 MST를 얻는 효과를 얻었다.

영어초록

This paper suggests a method that obtains the minimum spanning tree (MST) far more easily and rapidly than the present ones. The suggested algorithm, firstly, simplifies a graph by means of reducing the number of edges of the graph. To achieve this, it applies a method of eliminating the maximum weight edge if the valency of vertices of the graph is equal to or more than 3. As a result of this step, we can obtain the reduced edge population. Next, it applies a method in which the maximum weight edge is eliminated within the cycle. On applying the suggested population minimizing and maximum weight edge deletion algorithms to 9 various graphs, as many as the number of cycles of the graph is executed and MST is easily obtained. It turns out to lessen 66% of the number of cycles and obtain the MST in at least 2 and at most 8 cycles by only deleting the maximum weight edges.

참고자료

· 없음