PENERAPAN TEORI GRAF UNTUK MENYELESAIKAN MASALAH MINIMUM SPANNING TREE (MST) MENGGUNAKAN ALGORITMA KRUSKAL

Rizki, Swaditya ( Universitas Muhammadiyah Metro)

AKSIOMA: Jurnal Program Studi Pendidikan Matematika
Vol 1, No 2 (2012): JULI-DESEMBER (2012)

One of useful graph theory to solve the real problems is Minimum Spanning Tree (MST). MST is network optimization problems that can be applied in many fields such as transportations problems and communication network design (Gruber and Raidl, 2005). MST begins from tree namely a connected graph has no circuits. From the graph, there is a sub-graph that has all the vertex or spanning tree. If that graph has the weight/cost, then the spanning tree that has the smallest weight/cost is called Minimum Spanning Tree. Basic algorithm used to determine the MST is Kruskal’s algorithm. This algorithm is known as one of the best algorithms for the optimization problems, especially for MST. In this paper is developed a source code program to determine MST using Kruskal’s algorithm and then implemented on several data representing a complete graph.