Persoalan Degree Constrained Minimum Spanning Tree

Abstract

The degree constrained minimum spanning tree (DCMST) on undirected weighted connected graph G(V,E) is a problem to fins a spanning tree T in G with whose total edge length is minimal and the degree of each vertex vi in T at most a given value bi where dT (vi) bi. For solving this problem, we modified kruskal algorithm, an edge received in T, if an edge did not produce any cycle with preceding edge in T and a both endpoints should not exceed some given maximum degrees that dT (vj) bj and dT (vk) bk.

Dalam menyelesaikan persoalan degree constrained minimum spanning tree pada graph G(V,E) berbobot terhubung tak berarah merupakan permasalahan untuk menemukan spanning tree T di G dengan total panjang edge yang minimum dan degree dari setiap verteks vi di T dibatasi oleh bi dimana dT (vi) bi. Untuk menyelesaikan permasalahan degree constrained minimum spanning tree dilakukan dengan memodifikasi algoritma kruskal, dimana sebuah edge diterima di T, jika edge tidak membentuk cycle pada edge terdahulu yang berada di T dan verteks-verteks ujungnya memenuhi batas maksimum degree yang diberikan, yaitu dT (vj) bj dan dT (vk) bk.